'python' 태그의 글 목록

본문 바로가기

python

백준 12094 - 2048 (Hard) [파이썬] 풀이이전에 풀었던 2048 (Easy) 문제의 풀이 방법에서는 모든 경우의 수를 탐색하여 답을 도출했다면 2048 (Hard)는 10회의 이동으로 확장되었기 때문에 적절히 가지치기를 하여 시간을 줄여 답을 도출해야 합니다. 그럼, 어떤 경우를 가지치기해주어야 할까요? 블록들을 이동시켰는데 이전과 같은 모습일 경우단순하게 생각해봤을 때 가장 먼저 떠오르는 방법입니다. 어떤 한 경우에 대하여 상하좌우를 모두 구하기 때문에 상하좌우 중 같은 모양을 가진 경우가 발생하면 애초에 탐색할 필요가 없습니다. 중복된 경우를 탐색하기 때문입니다. 구한 최댓값이 이전에 구한 것보다 작을 것이라는 게 예상되는 경우이 경우는 저도 백준 질문 검색에서 얻어낸 해답입니다. 예를 들어 처음에 최대 10회 이동에 대해 탐색하였더.. 더보기

백준 12100 - 2048 (Easy) [파이썬] 풀이모든 경우의 수에 대해서 검사를 해봐야 어떤 경우에 가장 큰 수가 만들어지는지 알 수 있는 문제입니다.그래서, 풀이 방법은 ‘백트래킹’을 이용하여 모든 경우의 수를 검사하는 것입니다. 백트래킹 자체의 구현은 어렵지 않지만 각 수들을 move 하는 것에 시간이 좀 걸렸던 문제였습니다.위, 아래 이동은 row를 이동하면서 갱신해야하고왼쪽, 오른쪽 이동은 column을 이동하면서 갱신해야합니다. 각 칸에 대하여 선택된 칸 뒤에 남아있는 칸을 순서대로 검사하면서 남아있는 칸이 0이면 넘어가고, 0이 아니면 선택된 칸(0이 아니면)과 합치거나 혹은 선택된 칸(0이면)에 그 칸의 값을 이동시켰습니다. 선택된 칸과 남아있는 칸이 합쳐졌다면 다음 칸으로 넘어가서 같은 과정을 반복하면 되지만, 만약 선택된 칸이 0이.. 더보기

이전 1 다음

티스토리툴바