동적 계획법(Dynamic Programming) 이란?

생성일: 2023년 1월 16일 오후 5:32 태그: 알고리즘 ❔ 동적 계획법 (Dynamic Programming)이 뭔가요? 이 DP 아닙니다.. DP 동적 계획법은 캐시를 사용하는 최적화 기법이다! *Dynamic Programming은 단지 이름이 멋있어서 지은것이며, 실제의미랑은 관계가 없습니다.* 최적화 문제를 연구하는 수학이론에서 왔으며, 처음 주어진 문제를 더 작은 부분 문제들로 나눈 뒤 각 조각의 답을 계산 하고 저장한 뒤에 이 답들로 부터 원래 문제에 대한 답을 계산해 낼 수 있는 최적화 기법입니다. 쪼개진 문제가 두 번 이상 계산이 되는 문제를 부분 문제라고 합니다. 이 부분 문제는 두 개 이상의 문제를 푸는데 사용되기 때문에, 이 문제의 답을 여러번 계산하는 대신 한번만 계산하고 계..

2023.01.18

그리디 알고리즘 이란?

greedy 탐욕법 👩‍💻 탐욕 알고리즘 ( Greedy Algorithm ) 알고리즘이란? 그리디 greedy : 욕심 많은 탐욕 스러운 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 각 단계 마다 지금 당장 가장 좋은 방법만을 선택합니다. 탐욕법은 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않음. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다.근사적인 방법? wiki : 근사 알고리즘 (approximation algorithm)은 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미한다. 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장..

2023.01.09