IT/알고리즘 (1) 썸네일형 리스트형 동적 계획법 동적 계획법을 효율적으로 활용하기 위한 두 가지 조건 1. 작은 문제의 해결책의 합으로 큰 문제를 해결할 수 있는 구조 (최적 부분 구조) 2. 큰 문제를 나누었을 때 작은 문제가 여러 개 반복되는 구조 (중복 부분 문제) 즉, 동적 계획법 == 점화식 세우기 라고 생각 하면 된다. 규칙을 잘 찾는게 우선!! 점화식 구현은 주로 재귀를 활용하여 구현 But, 재귀 호출은 함수를 계속하여 호출하므로 (스택 메모리에 함수 호출 정보가 쌓여) 메모리와 런타임에 문제가 생길 수 있음 이럴 때 개선 할 수 있는 방법은 1. 재귀 호출 자체를 사용 X : 반복문 2. 재귀 호출의 횟수를 줄이는 방법 : 메모이제이션 >> 메모이제이션 : 이미 계산한 값을 저장해두었다가 이후에 쓸 일이 있을 때 활용하는 개념 => 반.. 이전 1 다음