알고리즘

(알고리즘) Greedy (탐욕 그리디 알고리즘)

✋ (알고리즘) Greedy (탐욕 그리디 알고리즘)이란 선택의 순간에 그 상황에서의 최적의 선택안만 골라 최종적인 결과에 도달하는 알고리즘 빨간색은 최적의 답을 도출 (110), 파란색은 그리디를 통해 도출한 답(90), 결론적으로 그리디를 통해서는 최적의 답을 고를 수 없습니다. 따라서 그리디가 최적의 답을 얻는 데 좋은 알고리즘은 아닙니다. ⚡️ 그리디 알고리즘을 사용하는 이유 여러 가지 제약사항을 고려하는 게 아니라 오로지 그 순간에 가장 최적의 선택을 하기 때문에 계산 속도가 빠릅니다. 그리디 알고리즘은 동적계획법에서 시간소요가 크기 때문에 이를 보완하기 위해서 도출된 알고리즘입니다. 그리디 알고리즘은 최적의 답을 도출하는 알고리즘이 아닙니다. 하지만 몇몇 케이스에서는 통하는 유형이 있습니다. ..

알고리즘

(알고리즘) Dynamic Programming (동적 계획법)

✋ (알고리즘) Dynamic Programming (동적 계획법)이란? 큰 문제를 작은문제로 나누어 푸는 문제를 일컫는 말입니다. 대표적으로 피보나치 수열을 구할 때 동적 계획법을 씁니다. 그러면 분할정복과 비슷하다는 말이 있을 텐데 아닙니다. 다릅니다. 📌 분할정복과의 다른점 결정적인 차이점이 있습니다. 바로 작은 문제가 중복이 일어나는지(동적계획법) 안일어나는지(분할정복기법) 입니다. 분할정복은 큰 문제를 해결하기 어려워 작은 문제로 나누는 알고리즘입니다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점입니다. 반면 동적계획법은 작은 부분문제들이 반복되는 것 (Result 값이 고정: F(0) =1, F(1) = 1) 을 이용해 풀어나가는 방법입니다. 즉, 분할정복과의 차이점은 작은 부분문제..