최장 부분 증가 수열1 1/22 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. 동적 계획법 (Dynamic Programming) DP, 다이내믹 프로그래밍이라 불린다. 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 큰 문제를 해결하는 것이다. 특정 알고리즘이라기 보다는 하나의 문제 해결 패러다임이다. 일반적인 재귀 방식을 사용하면 동일한 작은 문제들의 값이 여러번 반복되어 시간복잡도가 늘어난다. 이를 해결하기 위해 작은 문제의 값들을 저장하여 중복 계산을 제거하는 DP가 사용된다. DP를 사용하기 위해서는 메모이제이션, 작은 문제들의 값을 저장하는 리스트가 필요하다. 수학적 귀납법, 점화식을 생각해서 풀어야한다. 수학적 귀납법 => n = 1일 때, n = 2일.. 2023. 1. 22. 이전 1 다음
