[항해99 취업 리부트 코스 학습일지] 4주차 알고리즘 학습 Day 4

Q. 오늘 진행된 강의에서 학습한 내용은 무엇인가요?

다이나믹 프로그래밍 (Dynamic Programming)

동적 계획법이란?

동적 계획법(dynamic programming, DP)은 복잡한 문제를 더 간단한 여러 하위 문제로 나누어 해결하는 알고리즘 기법입니다. DP는 특정 구조가 내부적으로 반복되는 문제에서, 일부 문제의 풀이 결과를 재활용(메모이제이션)함으로써 계산의 효율성을 크게 높입니다. 이 기법은 부분 문제 반복과 최적 부분 구조를 가지며, 일반적인 방법에 비해 시간 복잡도를 크게 줄일 수 있습니다.

다이나믹 프로그래밍의 특징

1. 하위 문제의 재사용:
   • 문제를 더 작은 하위 문제로 나누고, 각 하위 문제의 답을 저장하여 동일한 하위 문제를 반복해서 계산하지 않습니다.
2. 메모이제이션(Memoization):
   • 계산한 하위 문제의 결과를 메모리에 저장하여 필요할 때마다 재사용하는 방식입니다. 이는 주로 재귀를 사용하여 하위 문제를 해결하면서 그 결과를 저장하는 탑다운 방식입니다.
3. 탑다운(Top-Down)과 바텀업(Bottom-Up):
   • 탑다운 방식은 재귀와 메모이제이션을 사용하여 상위 문제를 해결하기 위해 하위 문제를 호출하는 방식입니다.
   • 바텀업 방식은 반복문을 사용하여 작은 하위 문제부터 차례대로 해결해 나가면서, 더 큰 문제의 답을 구하는 방식입니다.

Q. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

DP의 경우, 문제를 해결하는 핵심 수식을 찾는 것이 중요하다. 문제를 작은 부분으로 나누어 재사용 가능한 형태로 만드는 과정에서 수식을 도출 하는데 보통 4번 인덱스까지 보면 패턴을 찾을 수 있다. 백트래킹을 통해 가능한 모든 경우를 탐색하면서 최적의 해를 찾는 과정에서 DP를 적용하면, 중복 연산을 줄이고 효율적으로 문제를 해결 할 수 있다.

 

 

 

항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지