[이것이 취업을 위한 코딩테스트다] chap08 - 다이나믹 프로그래밍
다이나믹 프로그래밍 다이나믹 프로그래밍은 최적의 해를 구하기에 연산 속오데 한계가 있고, 메모리 공간을 사용할 수 있는 데이터 개수도 한정적일 때 중복되는 연산을 줄이면서 공간을 최대한으로 활용하기 위해 탄생되었다. 동적 계획법이라고도 하며, 2가지 방식(탑다운과 보텀업)이 있으며 메모이제이션 기법이 주료 사용된다. 위와 같이 피보나치 수열이 있을 때 아래와 같이 점화식을 나타날 수 있다. 반복되는 값이 있을 때, 점화식을 통해 나타내고 이 점화식을 코드로 구현하면 다이나믹 프로그래밍 유형을 풀 수 있다. 피보나치 수열을 이진 탐색 트리로 구현했을 때, 위와 같이 동일한 함수가 반복적으로 호출되는 것을 알 수 있다. 불필요한 연산을 수행함으로써 연산 속도가 느려지고 메모리 공간을 많이 차지하는 단점이 있..
Data Structure & Algorithm/문제풀이 & 코딩테스트
2022. 2. 23. 18:36
최근댓글