profile
Divide and Conquer

동적계획법(DP, Dynamic Programming)

계단오르기 문제를 재귀함수를 이용해서 풀려고 하다가 동적계획법에 대해 알게되어 관련 내용을 정리해본다 >### 동적계획법이란? 복잡한 문제를 간단한 여러개의 문제로 나눠 푸는 방법 부분 문제 반복(Overlapping subproblems)와 최적 부분 구조(Optimal substructure)를 가지고 있는 알고리즘을 짧은 시간 안에 풀 때 사용 이해하기 쉬운 예시로 피보나치 수열에 대해 살펴보자 재귀함수 형태의 피보나치 수열 수학적인 정의로 볼때, 매우 간단하고 명료하게 표현할 수있지만, 컴퓨터가 계산하기에는 부적합하다고 한다. 파이썬에서는 재귀함수를 이용해 간단하게 함수를 만들어볼 수 있다. n이 작은 값일 때는 괜찮지만, n이 조금만 커져도 시간복잡도와 공간복잡도가 기하급수적으로 증가하게 된다. n = 35쯤 입력하면 멍하게 있는 자신을 보게 된다. 동적 계획법 형태의 피보나치 수열 동적계획법에서는 반복되는 계산을 막기

2022년 3월 25일
·
0개의 댓글
·