백준 2302번으로 보는 Backtracking과 DP의 목적 차이

2302. 극장 좌석 백준 2302번 문제인 극장 좌석을 풀기 위해, 처음에는 백트래킹 알고리즘을 이용했다. 오름차순으로 한 명씩 자리에 앉히고 다음 사람을 앉히기 위해 왼쪽, 자기자리, 오른쪽을 탐색을 반복하여 마지막 사람까지 자리에 앉으면 이것을 하나의 case로 보고 정답 값에 1을 더해주는 재귀 함수를 짜면 된다고 생각했기 때문이다. 그러나 시간 초과가 발생했다. 좌석의 수 N이 최대 40인데, 각 자리에는 왼쪽 사람, 자리 주인, 오른쪽 사람 총 세 명이 앉을 수 있으므로 시간 복잡도가 O(3^N)이다. 3^40은 조가 넘어가는 어마어마한 값이므로 당연히 안 된다. 결론적으로 이 문제는 Sub-Problem이 숨어 있는 DP 문제였다. VIP석이 Sub-Problem을 쪼개는 기준이었다. 이번 ..

• format_list_bulleted 알고리즘 문제풀이
• · 2022. 9. 14.
• textsms

[Algorithm] 다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍 (동적 계획법) 최적해를 구하기 위해 매우 많은 시공간이 필요한 경우 연산 결과를 저장하여 중복 연산을 방지함으로써 시공간 효율성을 높임 간단히 말하자면 한 문제를 무조건 한 번만 풀도록 결과를 저장해 사용한다는 것 언제 사용하는가 큰 문제를 작은 문제(큰 문제의 분할)로 나눌 수 있는 경우 작은 문제와 큰 문제의 해결 로직이 같아야 함 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일 해결 로직이 순수함수(동일 입력에 반드시 동일 출력이 보장)에 해당해야 함 어떻게 저장하는가 위 조건을 만족하는 문제들의 연산 결과들은 수열에 해당한다고 볼 수 있다. 수열은 규칙적으로 배열된 숫자들의 모임이기 때문에 배열(리스트)에 저장한다. 분할 정복 알고리즘과의 차이 분할 정복 알고리..

• format_list_bulleted Algorithm
• · 2021. 2. 23.
• textsms