[알고리즘] Greedy Algorithm (탐욕 알고리즘) 1. Greedy Algorithm이란? - Greedy: 탐욕스러운, 욕심 많은 - 탐욕 알고리즘: 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 - 최적 해를 구하는 데에 사용하는 근사적인 방법 - 여러 경우 중 하나를 결정할 때마다 그 순간 최적이라고 생각되는 것을 선택하는 방식 > 최종적 해답에 도달 (지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려 X) - 그 순간에는 지역적으로 최적이라도, 지역적인 최적을 수집한 최종적(전역적)인 답이 최적이라는 보장은 없다. - 탐욕 알고리즘에 적용할 수 있는 문제: 지역적, 전역적 모두 최적! * 간단한 예시 - 문제: 노드에서 가장 합이 높은 방법을 선택하는 방법 - 그리디 알고리즘: 상황에 맞게 가.. [알고리즘] Dynamic Programming(동적 계획법) 1. 다이나믹 프로그래밍이란? - "동적 계획법" - step1. 하나의 큰 문제를 여러 개의 작은 문제로 나눈다. - step2. 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용한다. - 하나의 문제 해결 패러다임 (특정한 알고리즘 X) - 기억하기 프로그래밍 2. 재귀와 DP의 차이? - 일반적인 재귀(Naive Recursion)를 단순히 사용 시, 동일한 작은 문제들이 여러 번 반복 > 비효율적 계산 ex. 피보나치 수열 - 재귀: f(n-1), f(n-2)에서 각 함수를 1번씩 호출 => 동일한 값을 2번씩 구하게 됨 => n 값이 증가함에 따라 호출되는 함수의 횟수는 기하급수적으로 증가 (약 7해) - DP: 한 번 구한 작은 문제의 결과 값을 저장하고 재사용 > 반복 X > 약 200회 .. 이전 1 다음
