알고리즘/개념

동적 계획법 (Dynamic Programming) 동적 계획법, DP는 복잡한 큰 문제를 여러 개의 작은 문제로 나누어 푸는 방식이다.다이나믹 프로그래밍이라는 이름은 고안자인 Richard Bellman이 붙인 이름인데 Dynamic이라는 단어가 멋져서 그렇게 지어졌으며 실제 원리와는 전혀 상관없다고 한다.반복되어 나오는 작은 문제들을 저장해 두었다가 재활용하기 때문에 직관적으로 '기억하며 풀기' 로 생각하는 것이 좋다. 왜 사용하는가? 피보나치 수를 구하는 재귀함수를 생각해 볼 수 있다. f(n-1)에서 구한 값을 f(n-2)에서 한번 더 구하기 때문에 실행되는 함수의 횟수가 기하급수적으로 증가하게 된다. 그러나 한번 구한 작은 문제의 값을 저장해놓는다면 연산 수가 급격히 감소하여 효율성이 증가한다...

그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘은 "현재 상황에서의 최적해를 선택하는 방식"이다. 백트래킹을 통해 추가적인 점검을 하지 않고, 현재 선택지 이외에는 검증을 하지 않는다. 하지만 그 해가 항상 최적해라는 보장을 할 수 없다는 한계가 존재한다. 위와 같은 최소 가중치 문제에서, 그리디 알고리즘을 적용하면 7과 10중에 7을 선택하고, 12와 15중에 12를 선택하여 7 + 12 = 19의 가중치를 해로 갖게 된다. 그러나 그림을 보면 알 수 있듯이 실제 최소 가중치는 10 -> 5를 선택하는 15이다. 그리디 알고리즘을 적용했을 때, 매 선택마다 부분 최적해는 구했지만, 전체 최적해를 구하지 못한 것이다. 따라서 그리디 알고리즘은 항상 최적해를 보장하지 못한다고 할 수 있다..

그리디 알고리즘 - 최적화 문제 데이터 간의 관계를 고려하지 않고 수행 과정에서 욕심내서 최소 또는 최댓값을 가진 데이터를 선택한다. (근시안적 선택) 동전 거스름돈 알고리즘 #의사코드 change=W, n500=n100=n50=n10=n1=0 // n500, n100, n50, n10, n1은 각각의 동전 카운트 while ( change ≥ 500 ) change = change-500, n500++ // 500원짜리 동전 수를 1 증가 while ( change ≥ 100 ) change = change-100, n100++ // 100원짜리 동전 수를 1 증가 while ( change ≥ 50 ) change = change-50, n50++ // 50원짜리 동전 수를 1 증가 while ( c..