* 이것이 취업을 위한 코딩 테스트다 with 파이썬 책을 통해 공부한 내용을 정리한 것입니다.
DP(다이나믹 프로그래밍) 이란,
1. Dynamic Programming(동적 계획법)의 정의
- 동적 계획법이란, 큰 문제를 작은 문제로 나누어 푸는 방식으로
- 메모리를 적절히 사용하여, 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
- 다이나믹 프로그래밍에서는, 이미 계산된 결과(작은 문제)는 -> '별도의 메모리 영역'에 저장하여 -> 다시 계산하지 않도록 한다.
- 다이나믹 프로그래밍 구현 방식에는 Top-Down(하향식)과 Bottom-Up(상향식)의 2가지 방식이 있다.
2. Dynamic Programming 특징
- 다이나믹 프로그래밍 = '동적 계획법' 이라고 부른다.
- 일반적으로 프로그래밍 분야에서 동적(Dynamic)이란,
- 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 필요한 메모리를 할당하는 기법' 이다.
- 반면, 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어이다.
3. Dynamic Programming 문제 해당 조건
1) 최적 부분 구조(Optimal Structure)
- 큰 문제를 -> 작은 문제로 나눌 수 있으며,
- 작은 문제의 답을 모아 -> 큰 문제를 해결 가능 해야한다.
2) 중복되는 부분 문제(Overlapping Subproblem)
- 동일한 작은 문제를 반복적으로 해결해야 한다.
위의 두 가지 조건을 만족할 경우, 다이나밍 프로그래밍을 사용할 수 있다.
4. Dynamic Programming 문제 예시
- 대표적인 DP 예시로, 피보나치 수열을 볼 수 있다.
- 피보나치 수열은
1 1 2 3 5 8 13 21 34 55 89 ...
와 같이 나열되는 수열이다.
(1) 표현 방법
- 점화식 : 인접한 항들 사이의 관계식
- 피보나치 수열을 점화식으로 표현하면, 다음과 같다.
| an=an-1+ an-2 , a1=1, a2=1 |
- 위와 같은 수열을 프로그래밍에서 표현할 때에는 배열이나 리스트(table)을 이용해 나타낸다.
(2) 시간 복잡도 분석
- 단순 재귀 함수로 피보나치 수열을 해결할 경우 '지수 시간 복잡도'를 가지게 된다.
- 예를 들어, f(6)를 구하는 피보나치 수열 문제에서 f(2) 가 '여러 번 호출' 되고 이는 [중복되는 부분 문제]로 간주할 수 있다.
-> 따라서, 한 번 해결한 문제 f(2)에 대해 이 값을 미리 저장하여 사용하는 것이다.
1) 세타 표기법 : θ(1.618…^N)
2) 빅오 표기법 : O(s^N)
- 빅오 표기법 기준, f(30)을 계산하기 위해서는 약 10억 가량의 연산을 수행해야 한다.
(2) 피보나치 수열의 효율적인 해법 - 다이나믹 프로그래밍
- 다이나믹 프로그래밍의 '사용 조건'을 만족하는지 확인해보면,
1) 최적 부분 구조 : 큰 문제를 -> 작은 문제로 나눌 수 있다.
2) 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결
-> 따라서, 피보나치 수열은 다이나믹 프로그래밍의 사용 조건을 만족한다.
DP 구현 방식 - Memoization(메모이제이션)
1. Memoization(메모이제이션) 정의
- 다이나믹 프로그래밍을 구현하는 방법 중 하나로,
- '한 번 계산한 결과' 를 -> '메모리 공간'에 메모하는 기법
-> 같은 문제를 다시 호출하면, 메모했던 결과를 그대로 가져온다.
- 값을 기록해 놓는다는 점에서, '캐싱(Chaching)' 이라고 한다.
+ ) 다이나믹 프로그래밍에서 자주 사용하는 배열 이름 : cache, memo, table, dp, d 등으로 설정
2. 메모이제이션 동작 분석
- 이미 계산된 결과를 메모리에 저장하면
f(6) -> f(5) -> f(4) -> f(3) 과 같이 아래 그림에서 색칠된 노드만 처리할 것을 기대한다.
- 이때, 색칠된 노드 값을 찾는 것은 '상수 시간'이 소요되고
- 피보나치 수열 함수의 시간 복잡도 = O(N) 이라고 할 수 있다.
3. 메모이제이션 방식 해법
(1) 문제 접근 방식
- 메모이제이션 방식은 ' Bottom Up(상향식) ' 과 ' Top Down(하향식) ' 의 두 가지로 접근할 수 있는데,
- 다이나믹 프로그래밍의 전형적인 형태는 Bottom Up(상향식) 방식을 취한다.
- 각 단계에서 계산 결과를 저장하는 리스트(배열) = 'DP 테이블' 이라고 한다.
(2) 메모이제이션 의미
- 메모이제이션은, '이전에 계산된 결과를 일시적으로 기록해 놓은 넓은 개념'을 의미한다.
-> 따라서, 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아니다.
-> 한 번 계산된 결과를 담아 놓기만 하고, 다이나믹 프로그래밍을 위해 활용하지 않을 수도 있다는 것이다.
1. Bottom Up 방식
2. Top Down 방식
Dynamic Programmic(다이나믹 프로그래밍) VS 분할 정복
- 분할 정복의 대표 예시로 '퀵 정렬' 을 기준으로 보면,
- 퀵 정렬에 사용되는 리스트에서 한 번 기준 원소(Pivot)가 자리를 변경해서 자리를 잡으면
-> 그 기준 원소의 위치는 바뀌지 X
- 분할 이후에 해당 Pivot을 다시 처리하는 부분 문제는 호출되지 X
Ex) Pivot : 5 인 원소에 대해 분할을 수행한 수
-> 왼쪽 / 오른쪽 범위에 대해 정렬이 다시 수행되는 재귀를 수행하지만,
한 번 분할이 이루어진 5는 다른 부분 문제에 포함되지 않고, 다시 호출되지 않는다는 것이다.
다이나믹 프로그래밍 문제 접근 방법
[Step 1] 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요
[Step 2] 가장 먼저, 그리디 / 구현 / 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토
- 다른 알고리즘으로 풀이 방법이 떠오르지 않으면, 다이나믹 프로그래밍을 고려한다.
[Step 3] 일단, '재귀 함수'로 '비효율적인 완전 탐색 프로그램'을 작성한 뒤(Top Down),
-> 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선하는 방법 사용
+ ) 일반적인 코딩 테스트 수준에서는, 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다!
'Programming > Algorithm' 카테고리의 다른 글
| [Algorithm] 비트마스킹(Bit Masking) (0) | 2022.06.25 |
|---|---|
| [Algorithm] 프로그래머스 전화번호 목록(해시) (0) | 2022.05.13 |
| [Algorithm] 백트래킹(Backtracking) (0) | 2022.02.27 |
| [Data Structure] 힙(Heap) 연산 (0) | 2022.02.21 |
| [Data Structure] 트리(Tree) 자료구조 (0) | 2022.02.14 |
