📝오늘 공부한 것
- 프로그래머스 문제풀기
- 스파르타코딩클럽 자료구조 & 알고리즘 5주차 강의 듣기
- 커리어톤 참여
알게 된 점❗
[ 동적 계획법 ]
동적 계획법(Dynamic Programming)
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
동적 계획법은 여러개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘이다. 즉, 우리가 재귀함수를 풀어나갈 때 많이 했던 함수의 수식화를 시키면 된다.
F(string) = F(string[1:n-2]) 라고 수식을 정의했던 것 처럼, 문제를 쪼개서 정의할 수 있으면 동적 계획법을 쓸 수 있다. 있
메모이제이션(Memoization)
결과를 기록하는 것
이미 실험했던 내용은 기록해두고 쓰면 된다는 것
겹치는 부분 문제(Overlapping Subproblem)
문제를 쪼갤 수 있는 구조
각 구간마다의 시간을 계산하면 최적의 시간을 구할 수 있는 것
-> 겹치는 부분 문제일 경우 동적 계획법을 사용하면 되는데, 이때 사용하는 방법은 메모이제이션을 이용하는 구나!라고 생각하면 된다.
'TIL(Today I Learned)' 카테고리의 다른 글
TIL-231012(Jacoco로 코드 커버리지 측정(1)) (0) | 2023.10.12 |
---|---|
TIL-231011(TDD) (0) | 2023.10.11 |
TIL-231009(자료구조 & 알고리즘 5주차) (0) | 2023.10.09 |
TIL-231007(자료구조 & 알고리즘 4주차) (0) | 2023.10.07 |
TIL-231006(자료구조 & 알고리즘 4주차) (0) | 2023.10.06 |