[WEEK04] 다이나믹 프로그래밍 & 4주차 복기

다이나믹 프로그래밍

1. 특징 

- 컴퓨터 연산속도의 한계 + 메모리 공간을 사용할 수 있는 데이터 개수의 제약

- 연산속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘이 필요

   ⇒ 메모리 공간을 약간 더 사용하면 연산속도를 비약적으로 증가시킬 수 있음

   ⇒ 동적프로그래밍 (≠ 동적할당)

 

- 큰 문제를 작게 나누고 같은 문제라면 한번씩만 풀어 문제를 효율적으로 해결하는 알고리즘

- 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한번만 계산하고 저장해둔 뒤 다시 한번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킴

 

다음 조건을 만족할 때 사용할 수 있음

- Overlapping Subproblems (겹치는 부분 문제)

1. 동일한 작은 문제들이 반복하여 나타나는 경우 사용 가능
2. 큰 문제를 작은 문제로 나눌 수 있음

- Optimal Substructure

1. 부분 문제의 최적 결과값을 사용해 전체 문제의 최적 결과를 낼 수 있음
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일

2. 문제풀이 방법

특정한 경우에 사용하는 알고리즘이 아니라 하나의 방법론이므로 다양한 문제해결에 쓰일 수 있음

 

1. 주어진 문제가 다이나믹 프로그래밍 유형임을 파악

- 완전 탐색으로 너무 오랜 시간이 걸리면 다이나믹 프로그래밍으로 문제 해결이 가능한지 확인

- 현재의 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지 판단

- 보통 특정 데이터 내 최대화 / 최소화 계산을 하거나 특정 조건 내 데이터를 세야 한다거나 확률 등의 계산의 경우 DP로 풀 수 있는 경우가 많음

 

2. 문제의 변수 파악

- 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것을 거침

- 즉, 문제 내 변수의 개수를 알아내야 함 (state를 결정)

   - 예를들어, 피보나치 수열은 n번째 숫자를 구하는 것이므로 n이 변수가 됨

   - 문자열 간의 차이를 구할 때는 문자열의 길이, edit 거리 등 2가지 변수를 사용

   - Knapsack 문제의 경우 index, 무게로 2가지의 변수를 사용

 

3. 변수간의 관계식 만들기

- 한마디로 말해서 점화식 만들기

 

4. 메모하기

- 변수의 값에 따른 결과 저장 필요

 

5. 가장 작은 문제의 상태 파악하기

- 가장 작은 문제의 상태를 파악 후 해당하는 값 등을 미리 배열 등에 저장

- 예를 들어 f(0) = 0, f(1) = 1과 같은 방식

 

6. 구현하기

- Bottom-up 혹은 Top-Down

3. 탑다운 방식 (Top-Down)

- 하향식

- Memoization

- 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법으로 

  메모이제이션은 값을 저장하는 방법이므로 캐싱(Caching)이라고도 부름

4. 바텀업 (Bottom-up)

- 상향식

- 반복을 통해 dp[0]부터 채워가는 방식으로 "table-filling"이라고 부름

- 근본적인 개념은 결과값을 기억하고 재활용한다는 측면에서 Memoization과 크게 다르지 않음

5. Q & A

- 분할정복과 다이나믹 프로그래밍의 차이점?

: 분할정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어나면 동적프로그래밍을 씀

 

---

WEEK04 복기

노션으로 정리를 하고 블로그에 다시 한번 복습 차원으로 정리를 하려고 하는데

해야 할 일들이 많아 하나하나 쳐내기에 바쁜 생활을 하고 있다. 🤣

다이나믹 프로그래밍을 좀 더 깊이있게 봤었으면 좋았을건데 라는 아쉬움이 있었다.

잘 해내고 싶은 마음은 굴뚝 같다 🌋

해야할 일들을 분할정복하고 필요한 개념들은 머릿 속에 메모이제이션 하자 🙏