2302. 극장 좌석
백준 2302번 문제인 극장 좌석을 풀기 위해, 처음에는 백트래킹 알고리즘을 이용했다.
오름차순으로 한 명씩 자리에 앉히고 다음 사람을 앉히기 위해 왼쪽, 자기자리, 오른쪽을 탐색을 반복하여 마지막 사람까지 자리에 앉으면 이것을 하나의 case로 보고 정답 값에 1을 더해주는 재귀 함수를 짜면 된다고 생각했기 때문이다.
그러나 시간 초과가 발생했다. 좌석의 수 N이 최대 40인데, 각 자리에는 왼쪽 사람, 자리 주인, 오른쪽 사람 총 세 명이 앉을 수 있으므로 시간 복잡도가 O(3^N)이다. 3^40은 조가 넘어가는 어마어마한 값이므로 당연히 안 된다.
결론적으로 이 문제는 Sub-Problem이 숨어 있는 DP 문제였다. VIP석이 Sub-Problem을 쪼개는 기준이었다. 이번 포스팅에서는 백트래킹 같기도 하고, DP 같기도 한 문제를 만났을 때 어떤 방식을 선택할 것인가를 확실히 정해 두기 위해 두 가지 알고리즘의 핵심을 정리해보았다.
언제 백트래킹 알고리즘을 쓰는가?
백트래킹 알고리즘은 Problem을 Sub-Problem으로 쪼갤 수 있으며, Sub-Problem을 해결해나가는 도중 이것이 정답이 될 수 있는지(정답 후보인지)가 판별 가능할 때 사용하면 좋다. 이 경우 Sub-Problem을 해결해나가다가 정답이 될 수 없는 후보에 대해서는 탐색을 중단함으로써 단순히 DFS 알고리즘으로 탐색하는 것보다 시간/메모리를 절약할 수 있다.
언제 DP 알고리즘을 쓰는가?
DP는 마찬가지로 Sub-Problem으로 쪼개지는 문제에서 반복되는 연산이 존재할 때 사용하면 좋다. DP의 핵심은 메모이제이션이다. 피보나치 수열과 같이, 연산에 대한 결과값을 얻기 위해 많은 리소스가 필요한 연산이 반복적으로 호출된다면 이에 대한 결과값을 미리 저장해둠으로써 시간을 절약하는 것이다.
극장 좌석 문제가 DP인 이유
극장 좌석 문제의 경우에도 VIP를 기준으로 좌석을 쪼갰을 때 여러 개의 연속된 일반 좌석이 생겨나고, 정답을 얻기 위해 연속된 일반 좌석 개수에 따른 착석 가능한 경우의 수를 구하는 연산이 반복된다.
따라서 이 문제는 Sub-Problem이 존재하고, 반복되는 연산이 있는 문제이기 때문에! DP로 접근하는 것이 효율적인 Problem인 것이다.