[Algorithm] Greedy(그리디) 개념 정리
수업시간에 교수님께서 그리디 알고리즘을 소개하실 때 단어 뜻 그대로 '탐욕' 알고리즘이라고 설명하셨던게 기억난다. 실제로 이 알고리즘은 가장 좋아보이는, 당장 좋은 것을 먼저 고르는 알고리즘이다. 대표적으로 동전 개수 구하기, 회의실 배정 등의 문제들이 있다. 무조건적으로 그리디가 최적해를 보장하지는 않기 때문에 (오히려 그리디로 최적의 해를 찾기 어렵다고 한다.) 그리디를 사용할 때는 문제 유형을 보고 판단하도록 하자. 동전문제는 그리디의 대표적인 문제인데, 이때 그리디 알고리즘으로 최적해가 보장되는 경우는 아래의 조건을 만족한 경우이다. - 동전의 액면이 모두 바로 아래 액면의 배수가 된다. 백준에 올라와있는 동전 문제는 주어진 동전들이 배수의 관계이므로 그리디 알고리즘을 사용하여 풀 수 있었다. h..
다이나믹 프로그래밍이란, 한마디로 똑같은 계산을 두번 다시 하지 않도록 하는 알고리즘이다. DP는 메모리 공간을 조금 더 사용하는 대신, 연산 속도를 증가시키는 방법이다. 따라서 한번 구한 결과값을 별도의 메모리 공간에 저장하는 방식을 따른다. 이러한 방식을 Memoization(메모이제이션)이라고 한다. DP에도 두가지 방식이 있는데 하나는 Top-Down(하향식), 하나는 Bottom-Up(상향식)이다. '이것이 코딩테스트다' 교재에도 나와있고 백준에도 나와있는 DP의 가장 베이직한 문제 "1로 만들기"를 다이나믹 프로그래밍으로 푼 코드이다. 이때 Bottom-Up(상향식)을 사용했다. Top-Down 방식으로도 구현해보려고 했는데 찾아보니 메모리 초과가 난다고... https://www.acmicp..