You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
동적 프로그래밍(Dynamic Programming)이란?
DP는 문제의 크기를 변화하면서 정답을 계산하는데, 작은 문제의 결과를 이용해서 큰 문제의 정답을 빠르게 계산하는 알고리즘이다.
동적 프로그래밍 시나리오
DP로 문제를 접근할 때에는 규격화된 문제 풀이 순서를 외워서 적용해야 한다.
1. 풀고 싶은 가짜 문제 정의
진짜 문제는 실제로 맞춰야 하는 문제이고 가짜 문제는 DP로 문제 사이즈를 바꿔서 풀 문제이다.
코딩 테스트에 나오는 대표적인 DP 유형 3가지는 아래와 같다.
Dy[i] := 1~i번 원소에 대해서 조건을 만족하는 경우의 수Dy[i][j] := i~j번 원소에 대해서 조건을 만족하는 최댓값Dy[i][j] := 수열 A[1...i]와 수열 B[1...j]에 대해서 무언가를 계산한 값운이 좋으면 가짜 문제와 진짜 문제가 일치할 때에도 있고, 아닐때도 있다.
2. 가짜 문제를 풀면 진짜 문제를 풀 수 있을까?
진짜 문제 예시) 수열 A[1...N]에서 조건을 만족하는 부분 수열의 개수
가짜 문제 예시) Dy[i] := 수열 A[1...i]에서 조건을 만족하는 부분 수열의 개수
가짜 문제를 푼다면 Dy[1], Dy[2], ..., Dy[N]을 모두 계산했을 것이니까, Dy[N]에 적혀있는 값이 곧 진짜 문제가 원하는 값이 될 것이다.
3. 초기값은 어떻게 되는가?
가장 작은 문제는 굳이 쪼개지 않아도 풀 수 있는 문제이다.
문제가 충분히 작아서 풀 수 있는 경우를 초기값이라고 한다.
그 초기값부터 시작해서 조금씩 큰 문제를 풀어나가면 된다. 이게 잘 안 풀리면 다시 가짜문제를 정의해야한다.
4. 점화식 구해내기
초기값을 기반으로 점점 더 큰 문제들을 해결하면서 Dy 배열을 가득 계산하는 과정이다.
점화식이 잘 구해지지 않는다면 다시 가짜문제를 정의해야 한다.
5. 진짜 문제 정답 출력하기
1~4 단계가 성공적으로 끝난다면 완성된 Dy 배열이 있을 것이다. 이걸로 진짜 문제를 풀면 된다.
All reactions