소개글

면접 대비겸 여러 블로그들을 참고하면서 정리해본 CS 지식들을 포스팅하고 있습니다.
만약 틀린 내용이 있다면 피드백은 언제나 환영합니다.
제 나름대로 요약한 내용이기 때문에 자세한 내용은 제일 아래쪽 참고 사이트에서 확인하면 좋을 것 같습니다!
말투는 편한 말투로 작성하니 양해 부탁드립니다.

DP, Greedy, Divide and Conquer

Dynamic Programming (동적 계획법)

• 복잡한 문제를 여러 개의 간단한 하위 문제로 나누어 푸는 방법 (하위 문제 중복O)
• 같은 하위 문제를 가지고 있는 경우 - Memorization 이용
• bottom-up 접근법
• ex) 피보나치 수열

Greedy (탐욕법)

• 각 단계마다 지금 당장에 가장 좋은 방법만을 선택해서 해결하는 방법
• 비교적 훨씬 빠름
• 탐욕법을 사용해서 최적해를 구할 수 있는 경우가 있고 아닌 경우가 있음
• 최적해 대신 근사해를 찾아서 해결하기도 함
• ex) 크루스칼 알고리즘

Divide and Conquer (분할 정복)

• Divide - 큰 문제를 여러 작은 문제로 쪼갬 (하위 문제 중복X)
• Conquer - 작은 문제들을 해결함
• Merge - 해결한 작은 문제들을 합침 (이 단계가 필수적이지는 않음)
• top-down 접근법
• ex) 이분탐색, 퀵소트

참고 사이트

https://velog.io/@zz1996zz/동적-계획법Dynamic-Programming과-분할정복Divide-and-Conquer