Greedy: 그리디
이번 기회에는 그리디 알고리즘에 대해 알아보자.그리디 알고리즘.Greedy: 탐욕스러운, 욕심 많은문제 해결을 위해 지금 당장 최선의 선택을 하는 것을 바탕으로, 문제의 정답을 구하는 것을 목표로 하는 알고리즘이다.치명적인 단점으로는, 순간순간 최선의 선택을 하더라도 결과는 최적이 아닐 수 있다는 것이다.예시를 들어보자.대한민국의 화폐 중 동전은 현행 기준 10원, 50원, 100원, 500원의 4종류가 있다.어느 가게의 알바가 손님에게 줘야 할 거스름돈이 980원이라면, 과연 어떻게 거슬러줘야 동전의 개수가 가장 적을까?980원에서 500원(500 × 1)을 빼고, 남은 480원에서 400원(100 × 4)을 빼고, 남은 80원에서 50원(50 × 1)을 빼고, 남은 30원을전부 10원짜리 3개로 거슬..
[JAVA] 재귀와 DP(동적 계획법)
오늘은 재귀와 DP에 대해 알아보려고 한다. 둘은 뗄 수 없는 관계로, 먼저 재귀부터 알아보자.① 재귀(再歸, Recursion)재귀는 두 재(再), 돌아갈 귀(歸)로 이루어진 한자어다.두 재는 '두 번의' 의미고, '재차, 거듭, 다시 한 번'과 같은 의미로도 사용한다.재귀에서는 '거듭, 다시 한 번'의 뜻으로 받아들이는 게 훨씬 자연스러울 거 같다.단어를 풀이하면 '재차 돌아가다' 정도의 뜻이겠다.보통 코딩에서 재귀를 설명할 때, 팩토리얼 예제나 피보나치 수열의 예제를 가지고 설명하고는 한다.이 글에서도 피보나치 수열을 가지고 설명을 하도록 하겠다.피보나치 수열(Fn)은 특정 항의 값이 직전의 두 항의 합과 같은 수열로, 다음과 같은 점화식으로 유도된다.F0 = 0, F1 = 1Fn+2 = Fn+1 ..
