Dynamic Programming이 하는 일은? 도달경로의 경우의 수 찾기. 개구리점프 예시(1/3)
https://codility.com/media/train/15-DynamicProgramming.pdf
dynamic programming은 피보나치 수열처럼 재귀적으로 정의되는 문제를 효율적으로 푸는 방법입니다.
“재귀적으로 정의되는 문제를 효율적으로 푸는 알고리즘, DP” ** **“큰 문제를 작은 문제로 나눌 수 있고, 그 작은 문제들이 겹쳐서 반복 계산된다면 DP로 풀어내면 효율적이다.” ** **“DP란 부분 문제의 답을 저장하고 재활용하는 기법이다.” ** **“DP는 top-down DP:메모이제이션(memoization), bottom-up DP:DP테이블채우기(table filling) 두 가지가 있다.”
보통 떠올릴 수 있는 단순한 문제들은,
- 피보나치수열: n번째 값 찾기.
- 목표계단오르기: n칸까지 오르는 계단을 한 번에 1, 2, .. ,a 씩 올라서 다 오르는 경우의 수
- 목표돈모으기: n원의 돈을 100, 500 원 등으로 다 모으는 경우의 수
- 목표거리가기(개구리): n까지의 거리를 한번에 1, 2, …, a 씩 점프하는 개구리가 끝까지 도달하는 경우의 수
개구리 문제는 DP문제를 이해할 수 있는 좋은 예시입니다.
- 문제: 한 번에 S:list[s:int] = [a, b, c] 거리만큼 뛸 수 있는 개구리가 있다. 개구리가 총 거리 k 까지 도달하려면 어떤 점프를 어떤 순서로 몇 번 해서 가는 경우의 수가 있을까?
시작점으로부터 j거리의 위치에 개구리가 있다면, 그 개구리는 위 시그마 합 만큼의 경우의 수로 해당 위치에 도달했을 겁니다. 한번에 점프를 a, b, c 만큼 할 수 있으므로 개구리의 바로 이전 위치는 j-a, j-b, j-c 중 하나입니다.
- DP로 해결한다는건: DP테이블dp[j], (0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def frog(S, k):
# S: list of jump lengths (e.g., [1, 2, 3])
# k: target position (e.g., 7)
n = len(S)
# dp[j] = number of ways to reach position j
dp = [0] * (k + 1)
dp[0] = 1 # base case: 1 way to "stay" at start
# fill dp table
for pos in range(1, k + 1):
for jump in S:
if jump <= pos: # valid jump
dp[pos] += dp[pos - jump]
return dp[k]
개구리의 예시의 s( 아마 stride? ) 는 좀더 여러 문제에서 연상될 수 있도록 일반화되게 표현하면 skillset 으로 기억할 수 있지 않을까 합니다 개구리의 스킬셋 S.
점화식 문제를 풀 때 효율적이라는게 꼭 필요한가? 라는 의문에 대해, 시간복잡도의 차이를 보면 확 체감할 수 있습니다. (다음의 경우 공간복잡도는 모두 O(N)으로 같습니다.)
DP를 왜 써야 하는가? 에 대한 의문을 먼저 풀어봅니다.
보통 재귀적으로 풀면, 피보나치의 경우,
F(5) = F(4) + F(3) 인데, F(4)를 계산할 때 F(4) = F(3) + F(2) 로 F(3)을 이미 계산했는데 F(5)를 계산하면서 F(5) = F(4) + F(3) 으로 F(3)을 한 번 더 계산하게 되서 비효율이 생깁니다.
- 재귀로 풀면 시간복잡도는 O(2^N).
- 여기에 재귀 + 메모이제이션(탑다운DP);한번 계산한 값은 딕셔너리에 메모해뒀다가 꺼내 쓰는 것 을 쓰면 시간복잡도는 O(N). 확 줄었음.
- 또 여기에 아예 재귀를 안쓰고 바텀업DP 쓸 수도 있는데. 시간복잡도는 O(N).
O(2^N)과 O(N)은 지수 시간, 선형 시간으로 보면 됩니다. 값이 지수적으로 늘어나는건 사실상 값이 폭발적으로 증가하는거니깐, 선형과는 스케일이 다르죠.
따라서 이런 식으로 재귀함수로 풀면 안되고, 메모이제이션을 곁들인 재귀함수를 사용하던가, 재귀 문제의 경우 점화식이 나오니까 그걸 가지고 DP를 써야만 합니다.
- 메모를 하는 재귀를 쓴다.(탑다운방식)
- DP테이블을 완성한다.(바텀업방식)
포스팅이 길어져서, 다음 포스팅에서 이어나가겠습니다. https://blog.naver.com/devramyun/223997745249
[20250906] Dynamic Programming이 하는 일은? 피보나치의 예를 들어 재귀적인 점화식 문제에서의 DP 필요성을 소개합니다(2/2) 아래 포스팅에서 이어서 작성하였습니다. https://blog.naver.com/devramyun/223997724675 DP를 소개하는… 아래 포스팅에서 이어서 작성하였습니다. https://blog.naver.com/devramyun/223997724675 DP를 소개하는…
+추가)
순수 재귀는 사실 상 쓰면 안되겠네요. ㅎㅎ. 안그래도 회사 알고리즘 구현할 때 재귀로 구현해둔 게 있는데, 대표님이 알고리즘 지속적으로 개선하면 좋겠다고 하신 게 타당하네요.
회사에서 구현한 건 깊게 끌고 들어갔다가 나왔다가 하면서 절차적으로 생성하는 알고리즘이었는데 이걸 재귀를 써야만 한다고 느꼈었지만, 알고리즘을 좀 더 능숙하게 볼 수 있게 되면 개선할 수 있는지 여부도 보이겠구나 싶습니다. 꼭 제가 할 필요는 없지만 말이죠. ㅎㅎ AI나.. 후임자가 할 지도…
#DP, #다이나믹프로그래밍, #탑다운, #바텀업, #메모이제이션, #DP테이블채우기, #피보나치, #점화식, #재귀, #재귀함수, #알고리즘, #개구리점프