백준 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

[백준/Python] 2023. 신기한 소수

2023. 신기한 소수 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 백트래킹 처음에는 에라토스테네스의 체를 사용하는 문제일 것이라고 생각했다. 가능한 수의 범위가 컸기 때문이다. (10**8) 하지만 사용 가능한 메모리가 4MB 뿐이라서, 가능한 범위만큼의 배열을 선언할 수는 없는 문제였다. 순차 탐색을 통해 소수를 판별하는 가장 빠른 방법 소수란, 1과 자기 자신 이외의 약수를 갖지 않는 수를 말한다. 약수의 개수를 구하는 것이 아니라, 단순 소수를 판별하는 경우에는 자기 제곱근(내림) 까지만..

• format_list_bulleted 개발 일지/알고리즘 문제풀이
• · 2021. 6. 2.
• textsms

[Algorithm] 백트래킹(Backtracking)

재귀 + 브루트포스 + "후보에서 탈락 시 해당 파트의 탐색 종료" 재귀 + 브루트포스가 DFS라면 (모든 조건을 다 탐색) 백트래킹은 모든 경우를 탐색하되 불가능한 후보임을 발견하면 해당 경우는 탐색을 종료한다. 시간 복잡도는 브루트포스와 동일하나 대부분의 경우에서 브루트포스보다 빠르게 동작한다. 후보에서 탈락 방문 중인 노드가 유망한지 체크하고, 유망하지 않다면 하위 트리를 가지치기한다. 종료 조건에 도달한 경우(마지막까지 유망한 경우의 수), 전역으로 선언된 결과값에 이를 반영한다. 구현 def check_node(node, target): global answer # 정답을 담을 변수는 함수 밖에서 관리 if not promising(node): # 방문 중인 노드가 유망하지 않다면 return ..

• format_list_bulleted 학습/Algorithm
• · 2021. 4. 6.
• textsms