algo_lec9

Dynamic Programming (Part 2) - Summary

1. What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic technique for solving optimization problems by breaking them down into simpler subproblems and solving each subproblem only once, storing the results for future reuse.

동적 계획법(DP)은 최적화 문제를 더 단순한 부분 문제들로 분할하여, 각 부분 문제를 한 번만 해결하고 그 결과를 저장함으로써 중복 계산을 방지하고 전체 문제를 효율적으로 해결하는 알고리즘 기법이다.

*Key characteristics:
- Recursive relation

문제의 해를 더 작은 부분 문제의 해로 표현하는 재귀적 관계를 설정한다.
- Bottom-up computation

가장 작은 부분 문제부터 차례대로 해결하면서 큰 문제의 해를 점진적으로 완성해 나간다.
- Table (memoization) to store subproblem solutions

각 부분 문제의 결과를 배열(또는 테이블)에 저장하여 같은 계산을 반복하지 않도록 한다.

2. Example 1: Binomial Coefficients

- The recursive formula for binomial coefficients is:
B(i, j) = 1 if j == 0 or j == i
B(i, j) = B(i-1, j-1) + B(i-1, j) if 0 < j < i

- This can be represented using Pascal’s Triangle.

P[i][j]=P[i][j-1]*(i-(j-1))//(j-1)

 

- A dynamic programming approach avoids redundant computation by filling values bottom-up.

동적 계획법 접근 방식은 값을 아래에서부터 채워 나가는 방식으로 중복 계산을 피한다

3. Example 2: Longest Increasing Subsequence (LIS)

- Given a sequence, find the length of the longest increasing subsequence.

 

- For example, S=(9,5,2,8,7,3,1,6,4): the longest increasing subsequence has length 3 and is either (2,3,4) or (2,3,6).

a_4​ = 8은 앞선 원소들 중, a_2 = 5 다음에 올 수 있음 (5 < 8) 그리고 h_2 = 1 → h_4 = h_2 + 1 = 2 그러므로 LIS는 [5, 8] → predecessor[4] = 2

: predecessor 배열은 LIS (Longest Increasing Subsequence) 를 추적할 때, 각 위치에서 현재 수열에 붙는 직전 원소의 인덱스를 기록해두는 중요한 구조.

 

* predecessor[6]=3

• a_3 = 2에서 끝나는 LIS: [2] → 길이 = 1
• 거기에 a_6 = 3을 붙이면 → [2, 3] → 길이 = 2
• 따라서 h[6] = h[3] + 1 = 2
  그리고 그 직전 원소의 인덱스는 3 → predecessor[6] = 3

- How many searches we can expect?

2^n searches (or subsets)

- Recursive relation:
h[i] = max(h[j] + 1) for all j < i where a[j] < a[i]
LIS length = max(h[i])

- Implementation uses a nested loop to compute LIS in O(n^2) time.

 

[1단계]

먼저, 수열의 각 원소에서 끝나는 LIS의 길이를 저장할 배열 h를 초기화합니다.

모든 위치는 최소 자기 자신 하나만으로 LIS를 구성할 수 있으므로, h의 모든 값을 1로 초기화합니다.

 

[2단계]

그 다음, 바깥쪽 루프는 두 번째 원소부터 순차적으로 i = 1부터 n-1까지 진행되며,

현재 인덱스 i에서 끝나는 LIS의 길이를 업데이트합니다.

내부 루프에서는 j = 0부터 i-1까지의 모든 인덱스를 검사합니다.

- 이때 arr[j] < arr[i] 조건을 만족하는 경우, arr[i]는 arr[j]를 이어 증가 수열을 만들 수 있습니다.

그 경우에 h[i] < h[j] + 1이라는 조건도 확인합니다. 조건이 참이면 h[i]를 h[j] + 1로 갱신합니다.

 

[3단계]

이 과정을 반복하면, 각 i에 대해 그 지점에서 끝나는 가장 긴 증가 부분 수열의 길이가 h[i]에 저장됩니다. 반복문이 모두 끝난 후에는 h 배열에서 가장 큰 값을 찾아 반환합니다. 그 값이 전체 수열에서의 최장 증가 부분 수열의 길이가 됩니다.

 

예를 들어 수열 [10, 22, 9, 33, 21, 50, 41, 60]의 경우, h_i 배열은 [1, 2, 1, 3, 2, 4, 4, 5].

따라서 이 수열에서 LIS의 길이는 5이며, 가능한 수열 중 하나는 [10, 22, 33, 50, 60]입니다.

---

Today's Topic

Exampe 3: Number Triangles

Example 4: Revisit minimum coin change

---

4. Example 3: Number Triangles

- Goal: Maximize the sum from top to base in a number triangle.

숫자 삼각형의 꼭대기에서 바닥까지 내려가는 경로 중, 지나간 숫자의 합이 최대가 되도록 하는 경로를 찾는 것.

 

- Recursive relation: best(r, c) = a[r][c] + max(best(r-1, c-1), best(r-1, c))
이는 (r, c) 위치에 도달하기 위한 경로가 윗줄에서 왼쪽 대각선 (r-1, c-1) 또는 바로 위 (r-1, c) 중 하나에서 올 수 있으므로, 이 둘 중 더 큰 경로 합을 선택하여 현재 위치의 값을 더해주는 방식.

- This DP approach reduces the exponential time of exhaustive search to O(n^2).

---

Dynamic Programming - Number Triangle Summary

 

1. 문제 설명

숫자가 삼각형 형태로 배치된 구조에서, 꼭대기에서 바닥까지 내려가는 경로 중 지나가는 숫자의 합이 최대가 되는 경로를 찾는 문제이다. 한 번에 아래로 이동할 때는 왼쪽 아래 대각선 또는 오른쪽 아래 대각선으로만 이동할 수 있다.

 

2. 완전 탐색의 한계

삼각형의 레벨이 k일 경우, 가능한 경로의 수는 2^(k-1)개가 되며, 시간 복잡도는 Θ(2^n)으로 매우 비효율적.

level = k / n = (총 원소 개수)

 

3. 동적 계획법 접근

- 동적 계획법을 적용하기 위해 다음과 같은 재귀 관계를 정의:

best(r, c) = a[r][c] + max(best(r-1, c-1), best(r-1, c))

→ 여기서 a[r][c]는 r번째 행 c번째 열의 값이며, best(r-1, c-1)과 best(r-1, c)는 그 위쪽에서 내려올 수 있는 두 경로의 누적 합을 의미. 이 중 더 큰 값에 현재 값을 더해 최적 합을 계산.

 

 

4. 구현 방식

1) 첫 번째 행(꼭대기)은 그대로 사용.
2) 이후 각 행에 대해 다음과 같이 값을 갱신:
- 왼쪽 끝 열(c = 0): 바로 위에서만 올 수 있음 → dp[r][0] = dp[r-1][0] + a[r][0]
- 오른쪽 끝 열(c = r): 왼쪽 위에서만 올 수 있음 → dp[r][r] = dp[r-1][r-1] + a[r][r]
- 나머지: 두 경로 중 큰 누적 값을 선택 → dp[r][c] = a[r][c] + max(dp[r-1][c-1], dp[r-1][c])

max(11,16)=16 / max(25,23)=25 / max(20,19)=20 에 집중

 

5. 시간 복잡도

삼각형의 각 칸을 한 번씩만 계산하므로 총 연산 수는 1 + 2 + ... + n = n(n+1)/2.

따라서 전체 알고리즘의 시간 복잡도는 O(n²). 이는 완전 탐색의 지수 시간 복잡도에 비해 매우 효율적.

 

5. Example 4: Revisit Minimum Coin Change

- Given coins of different denominations, find the minimum number of coins to make a certain value y.

 

- Recursive relation:
minCoins[y] = min(minCoins[y - coin] + 1 for coin in coins if coin <= y)

- Greedy algorithms may fail; DP provides an optimal solution using a table of size y+1.

- Time complexity: O(m*y) where m is the number of coin types.

 

1. 문제 설명

동전의 종류가 여러 개 주어졌을 때, 특정 금액 y를 만들기 위한 최소 동전 개수를 구하는 문제.

예를 들어, 동전이 [1원, 5원, 10원]이고 목표 금액이 11원이라면, 최소 동전 개수는 2개(10원 + 1원)이다.

 

2. 재귀 관계

이 문제는 다음과 같은 재귀 관계를 기반으로 해결할 수 있다:

minCoins[y] = min(minCoins[y - coin] + 1 for coin in coins if coin <= y)

즉, 금액 y를 만들기 위해 모든 가능한 동전 coin에 대해 y - coin 값을 만들 수 있는 최소 동전 수를 확인하고, 그 값에 현재 coin 하나를 더한 것 중 최소값을 선택하는 방식.

 

이 문제를 해결하기 위한 핵심 아이디어는 '큰 문제를 더 작은 문제로 나누는 재귀 관계'를 세우는 것.

예를 들어, 어떤 동전 c₁을 먼저 선택했다고 하면, 그 이후에는 남은 금액 y - c₁에 대해 동일한 문제를 다시 푸는 방식으로 진행된다.

이 아이디어를 기반으로 한 재귀 관계는 다음과 같다:
minCoins(y) = min { minCoins(y - c_i) + 1 | 모든 c_i ≤ y }

- minCoins(y): 금액 y를 만들기 위한 최소 동전 수
- c_i: 사용 가능한 동전 중 하나
- y - c_i: 현재 동전 하나를 사용하고 남은 금액
- +1: 현재 사용한 동전 1개를 의미

 

#Pseudo-code (recursive version)

if y == 0:
    return 0
if y > 0:
    return min(1 + minCoins(y - coin[i])) for all coin[i] ≤ y

3. DP 방식의 장점

탐욕적(greedy) 알고리즘은 항상 최적 해를 보장하지 않는다.

 

: 예를 들어, 동전이 [25원, 20원, 10원, 5원, 1원]이고 목표 금액이 65원일 때,

가장 큰 동전부터 선택하는 탐욕 방식은 4개(25+25+10+5)를 사용하지만,

최적 해는 3개(20+20+25)이므로, 이 문제는 동적 계획법(DP)을 사용하는 것이 더 안정적이고 정확.

 

4. 구현 방식 [Explore with dynamic programming]

1) DP를 활용하기 위해 길이가 y+1인 테이블을 생성한다.

2) 테이블의 각 인덱스 i는 금액 i를 만들기 위한 최소 동전 수를 저장.

3) 테이블의 초기값은 모두 무한대로 설정하고, 0원을 만들기 위한 최소 동전 수는 0으로 초기화.

4) 그 후 각 금액 i에 대해 가능한 모든 동전 coin을 확인하면서, i - coin 위치에 저장된 값에 1을 더한 값과 현재 값을 비교하여 최소값으로 갱신.

min { 1+minCoins(y-Coin{i]) }

 

---

목표 금액(y): 11센트 동전 종류(coins): 9센트, 6센트, 5센트, 1센트 목표: 최소 개수의 동전으로 11센트를 만드는 방법 찾기

---

5. 시간 복잡도

이중 반복문을 사용하므로 시간 복잡도는 O(m*y)이다. 여기서 m은 동전 종류의 개수, y는 목표 금액이다.

각 금액에 대해 모든 동전을 시도하기 때문에 m번의 반복이 필요하고, y까지 계산하므로 전체 시간은 O(m*y)이다.

- Time Complexity: O(my)

- Space Complexity: O(y)