TIL-231010(자료구조 & 알고리즘 5주차)

📝오늘 공부한 것

• 프로그래머스 문제풀기
• 스파르타코딩클럽 자료구조 & 알고리즘 5주차 강의 듣기
• 커리어톤 참여

 

알게 된 점❗

[ 동적 계획법 ]

동적 계획법(Dynamic Programming)

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 

동적 계획법은 여러개의 하위 문제를 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘이다. 즉, 우리가 재귀함수를 풀어나갈 때 많이 했던 함수의 수식화를 시키면 된다.

F(string) = F(string[1:n-2]) 라고 수식을 정의했던 것 처럼, 문제를 쪼개서 정의할 수 있으면 동적 계획법을 쓸 수 있다. 있

 

메모이제이션(Memoization)
결과를 기록하는 것

이미 실험했던 내용은 기록해두고 쓰면 된다는 것

 

겹치는 부분 문제(Overlapping Subproblem)

문제를 쪼갤 수 있는 구조

각 구간마다의 시간을 계산하면 최적의 시간을 구할 수 있는 것

 

-> 겹치는 부분 문제일 경우 동적 계획법을 사용하면 되는데, 이때 사용하는 방법은 메모이제이션을 이용하는 구나!라고 생각하면 된다.