-
Dynamic Programming코딩테스트 2020. 11. 30. 19:19
다이나믹 프로그래밍 (동적 프로그래밍)
- 기억하기 프로그래밍이라는 단어가 더 잘 어울릴 수도.
- DP에서 프로그래밍은 코딩하는 것이 아니라, 테이블을 이용하여 문제를 해결하는 방법
- 부분 문제의 해를 결합하여 큰 문제를 해결해 나간다. (분할정복기법)
- 이 때 부분문제는 무조건 계산하는 것이 아니라 테이블을 통해 재사용.
- 즉, 한 번 계산한 문제는 다시 계산하지 않는다
- 큰 문제를 한번에 해결하기 힘들 때 작은 여러개의 문제로 나눠 푸는 기법
- 그 문제들을 재계산하지 않고 값을 저장해두었다가 재사용하는 기법 (불필요한 계산 줄이기)
- 재귀적으로 생각하기
- DP문제를 풀기 위해서는 점화식(인접한 항들 사이의 관계식)을 세워야 한다.
메모제이션(동적 프로그래밍 기법 중 하나)
- 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해, 이전에 계산했던 값을 저장해두었다가 재사용하는 방법.
피보나치 수열을 dp를 이용하여 구현
def fibo_dp(n): cache = [0 for _ in range(n+1)] cache[0] = 0 cache[1] = 1 for i in range(2, n+1): cache[i] = cache[i-2] + cache[i-1] return cache[n] a = fibo_dp(10) print(a)
계산한 값들은 캐시에 저장한 후 재계산하지 않고, 이미 계산했던 값을 재사용함.
https://koitp.org/problem/ROD_CUTTING/read/
'코딩테스트' 카테고리의 다른 글
[SQL] SQLZOO JOIN operation 13번 문제 (0) 2020.11.08 코딩테스트 빈출 유형 / 준비법 (0) 2020.10.28 [프로그래머스] 피보나치 수열 - Python (1) 2020.08.22 [SQL] 오랜 기간 보호한 동물(2) (0) 2020.08.17 [프로그래머스 SQL] String ,Date - 중성화 여부 파악하기 (0) 2020.08.10