반응형
동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다.
처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고,
이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다.
동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다.
동적 계획법(DP)은 다른 알고리즘과 함께 이용해서 문제를 풀어야 하는 경우가 있다.
특정 Case를 여러번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용하여 속도를 높이다.
그러기 위해 각 문제의 답을 메모리에 저장해 둘 필요가 있다. → DP[ ][ ]
▶ 연속된 부분 합(연속합) - 2 (Prefix Sum)
이때 미리 계산한 값을 저장해 두는 메모리 장소를 캐시(cache)라고 부르며,
두 번이상 계산되는 부분 문제를 "중복되는 부분 문제(Overlapping Subproblems)"라고도 한다.
일반적인 서비스를 만드는 업무에서는 적용하기 쉬운 방식은 아니기도 하고
개인적으로는 수학(?)적인 감각이 필요해서 선호하지 않는 기법이다. 🤦♀️
이러한 유형은 기업에 따라 1~2문제씩 출제되기도 하는데,
DP까지 이용하지 않고 문제 규칙을 이용하면 풀 수 있는 경우도 있다.
Reference
- [SWEA] 4062 Largest Empty Square
- [Algospot] BOGGLE 보글 게임 (+ 3차원 배열)
- [Algospot] CHRISTMAS 크리스마스 인형 (+ 부분합)
반응형
'알고리즘' 카테고리의 다른 글
| [ps] 순환되는 행렬 인덱스 (Index) (0) | 2021.05.30 |
|---|---|
| freopen( )을 이용한 파일 입출력 (2) | 2021.05.24 |
| 순열과 조합 (백준 N과 M 시리즈) (4) | 2021.05.08 |
| 아스키(Ascii) 코드 활용 (1) | 2021.05.06 |
| [알고리즘] 시간 성능 향상을 위한 코드 최적화 (C/C++) (0) | 2021.05.05 |
댓글