지난 이야기...
1463번: 1로 만들기를 풀었습니다. 해당 문제의 경우 BFS와 DP로 해결이 가능합니다.
https://www.acmicpc.net/problem/1463
BFS 정답 코드
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
visited = [0] * (n + 1)
def bfs():
q = deque()
q.append(n)
while q:
cur = q.popleft()
if cur == 1:
break
if cur % 3 == 0 and visited[cur // 3] == 0:
visited[cur // 3] = visited[cur] + 1
q.append(cur // 3)
if cur % 2 == 0 and visited[cur // 2] == 0:
visited[cur // 2] = visited[cur] + 1
q.append(cur // 2)
if visited[cur - 1] == 0:
visited[cur - 1] = visited[cur] + 1
q.append(cur - 1)
bfs()
print(visited[1])DP 정답 코드
import sys
input = sys.stdin.readline
n = int(input())
arr = [0] * (n + 1)
for i in range(2, n + 1):
arr[i] = arr[i - 1] + 1
if i % 2 == 0:
arr[i] = min(arr[i], arr[i // 2] + 1)
if i % 3 == 0:
arr[i] = min(arr[i], arr[i // 3] + 1)
print(arr[n])실행 시간
해당 문제의 실행 시간의 경우 BFS가 76ms, DP가 456ms로 상당히 차이나는 것을 확인할 수 있습니다. 그동안 DP가 보편적인 상황에서 더 효율적이라고 생각하고 주로 DP를 선택했는데, 어떻게 이런 결과가 나왔는지 알아보도록 하겠습니다.
수행 시간 분석
BFS는 visited 배열과 deque를 사용해 한 카운트에서 가능한 여러 경우의 수를 모두 검사합니다. 따라서 해당 문제처럼 한 카운트에서 모든 경우의 수를 검사하며, 목표 값에 가장 먼저 도달한 경우의 count가 정답이 됩니다.
DP는 문제를 작은 문제들로 분할한 다음, 이를 조합하면서 목표 값까지 도달하는 방식입니다. 해당 문제에서는 목표 값에 도달할 때까지 작은 문제들을 해결해 나가며, 모든 작업이 끝나면 목표 값의 인덱스에 해당하는 count가 정답이 됩니다.
수행 시간은 두 방식 모두 O(N) 으로 동일합니다. 하지만 DP의 수행 시간이 BFS보다 더 오래 걸린 것은 아래와 같은 이유라고 생각됩니다.
현재 코드에서는 BFS의 경우 Top-down 방식으로 목표 값 n에서 시작해 필요한 경로에 대해서만 탐색을 수행하지만, DP는 시작점에서 차근차근 목표 값까지 계산합니다. 이 과정에서 목표 값과 상관 없는 값까지 계산하는 불필요한 연산이 포함될 수 있으며, 이러한 탐색 방향에서의 차이가 시간적인 격차를 발생시킨 것으로 보입니다.
오늘의 이야기...
지난 이야기에 이어서 2579번: 계단 오르기를 풀었습니다. 비슷한 문제 유형이라 판단되어 어제의 경험을 바탕으로 BFS를 먼저 시도했습니다. 그리고 익숙해진 것 같으니 지금부터는 반말로 작성하도록 하겠다.
https://www.acmicpc.net/problem/2579
BFS
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
res = [0] * n
arr = []
for _ in range(n):
arr.append(int(input()))
q = deque()
q.append((0, False))
res[0] = arr[0]
while q:
idx, seq = q.popleft()
if not seq and idx + 1 < n:
res[idx + 1] = max(res[idx + 1], res[idx] + arr[idx + 1])
q.append((idx + 1, True))
if idx + 2 < n:
res[idx + 2] = max(res[idx + 2], res[idx] + arr[idx + 2])
q.append((idx + 2, False))
print(res[n - 1]) BFS로 코드를 구현하여 제출했다.
어째서...?
해당 코드를 제출하면 메모리 초과 오류가 발생한다. 왜일까? 아마 다음과 같은 이유로 생각된다.
각 단계에서 가능한 모든 경우의 수를 deque에 넣는 방식은 중복된 값도 포함되며, n의 값이 증가할수록 기하급수적으로 메모리를 잡아먹어 오류가 발생한 것으로 보인다. 즉, 1로 만들기와 다르게 생각해야 한다는 뜻이다.
아!!!!!!!!!!!!!!!
이 문제를 잘 읽어보면 규칙이 존재한다. 한 칸 혹은 두 칸을 점프할 수 있지만 세 칸 연속으로는 밟을 수 없다. 진짜 알고리즘 고수라면 여기에서 즉시 규칙이 존재한다 -> 점화식 유도가 가능하다 -> DP를 시도한다 물 흐르듯이 풀어냈겠지만 난 이 부분을 놓치고 말았던 것이다. 이제 규칙이 존재한다는 것을 알았으니 점화식을 유도해보자.
점화식 유도하기
계단의 한 지점에서 선택할 수 있는 경우의 수는 다음과 같다.
- 두 칸을 올라간다
- 한 칸을 올라간다
여기에서 세 칸 연속으로 밟을 수 없다는 규칙이 존재한다. 따라서 다음과 같이 수정한다.
- 두 칸을 올라간다
- 직전에 한 칸을 올라가지 않았다면 한 칸을 올라간다
하지만 이것만 봐서는 아직 풀이가 명확하게 떠오르지 않는다. 점화식을 유도해야 하는데, BFS로 풀이한 것처럼 직전에 한 칸 올라갔는지 판단하는 boolean 값을 이용하는 방법밖에 떠오르지 않는다.
사실 DP에 대한 개념이 부족한 상태에서 점화식을 유도하는 과정은 쉽지 않다. 규칙을 찾고 점화식을 유도해 풀어내라는 추상적인 설명은 알고리즘에 익숙하지 않은 초보자들이 겁을 먹게 만든다. 하지만 해당 포스팅을 통해 DP를 처음부터 쉽고 천천히 알아가는 시간을 갖도록 하겠다.
알고리즘을 포기한... 바보 같은 아들을 그래도 사랑하마...
DP의 본질
DP의 핵심은 이전 문제의 최적해를 믿고 사용한다는 것이다. dp[k]는 k번째 단계까지 도달하기 위한 모든 경우의 수를 고려한 최적해라 믿으며, 이것을 통해서 다음 단계에서 dp[k]의 값을 어떻게 구한지 몰라도 믿고 가져다 쓴다는 뜻이다.
즉, DP는 점화식을 통해 작은 문제를 설정하고 Bottom-up 혹은 Top-down 방식으로 이전에 구한 최적해로 현재의 문제를 해결하는 과정을 반복하며 목표에 도달하는 방식이라고 할 수 있겠다.
따라서 방금 전처럼 접근하면 우리가 원하는 점화식에 도달하기 힘들다. 이제 배운 내용을 바탕으로 가정을 약간 비틀어서 다시 점화식을 유도해보자.
다시 점화식 유도하기
현재 계단에서 다음 계단으로 나아가는 방식에서, 어떻게 현재의 계단에 도달했는지로 가정을 변경한다.
현재 계단 dp[k]는 다음과 같이 방식으로 도달할 수 있다.
- 한 칸을 올라와서
dp[k]에 도달했다- 두 칸을 올라와서
dp[k]에 도달했다
이렇게 하면 점화식을 유도하기 쉬운 형태로 정리된 것을 확인할 수 있다. 여기서 문제에서 주어진 세 칸을 연속으로 밟으면 안 된다는 규칙을 고려해보자.
현재 계단 dp[k]는 다음과 같이 방식으로 도달할 수 있다.
- 두 칸을 올라온 뒤 한 칸을 올라와서
dp[k]에 도달했다- 두 칸을 올라와서
dp[k]에 도달했다
왜 두 칸을 올라온 뒤 한 칸을 올라오는가?
한 칸을 올라온 뒤 두 칸을 올라오는 경우는 성립되지 않는다.
dp[i]에서 한 칸 올라온 뒤 두 칸을 올라오는 경우는 dp[i+1]에서 두 칸을 올라오는 경우와 동일하다. 두 방법 모두 마지막에 두 칸을 올라와서 현재 계단에 도달한다. 현재 계단에 도달하는 경우는 한 칸과 두 칸, 총 두가지여야 한다.
두 칸을 올라온 뒤 한 칸을 올라오는 이유
두 칸을 올라오는 이유는 연속된 세 칸을 밟을 수 없다는 규칙 때문이다. 이를 통해서 현재 계단에 한 칸으로 도달하면서도, 반복시 규칙을 위반하지 않도록 한다.
따라서 점화식은 다음과 같이 구할 수 있다.
현재 계단 총합 = max(2칸 아래의 총합 + 현재 계단의 값, 3칸 아래의 총합 + 1칸 아래의 값 + 현재 계단의 값)
이제 이를 바탕으로 코드를 구현해보자.
DP
import sys
input = sys.stdin.readline
n = int(input())
arr = [0] * (n + 1)
for i in range(1, n + 1):
arr[i] = int(input())
dp = [0] * (n + 1)
dp[1] = arr[1]
if n > 1:
dp[2] = arr[1] + arr[2]
for i in range(3, n + 1):
dp[i] = max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i])
print(dp[n])
이제 DP랑 사이좋게 지내야 한다~
