Greedy와 DP 알고리즘에 대한 고찰

문제를 풀면서, 깨닫는게 많아지면서 변화할 생각을 적어보고자 한다.

 

결국 DP의 미학은 계산한걸 또 계산하지 않겠다는 것이다. 그래서 메모이제이션이 필요한 것이다.

점화식을 구하는 것이 핵심인데, 점화식이라는 어려운 말보다 다음 껀 어떻게 구할래? 이렇게 생각하면 편할것이다.

DP의 경우 N번째가 모두 정답이다. 곧, 정답만 저장된다는 것도 그 정답을 이용해 다음 정답을 이끌어내야하는 과제가 있다.

 

실버문제의 경우

초기식을 세우고 dp[0] 처럼 하드코딩으로 내가 정의할 수 있는 경우가 많다.

그 후, 문제를 풀때 dp[1], dp[2]는 어떻게 될지 나열하다보면, 결국 문제는 풀리기 마련이다.

 

골드문제의 경우

dp의 자료구조를 어떻게 정할지에 대해 고민스러웠던 경험이 있었다. dp자체에 어떤 정답을 담아야할지 dp를 어떻게 이용해야할지 아직 문제를 더 풀어야 하겠지만, 주로 어려웠던 경험은 그래프형식으로 dp를 이용하는 문제가 생각하기 어려웠던 것 같다.

 

Greedy알고리즘의 경우, 

구현이 핵심이라고 생각한다. 제한된 메모리와 시간안에 문제를 해결해야한다. 아직 경험치가 부족한것 같다.

지금까지의 적은 경험으로, Greedy알고리즘 문제를 마주쳤을때, 실버 문제정도의 경우 아이디어를 빨리 떠올리느냐의 문제이며, 골드문제의 경우 구현문제로 변하는 것 같다.

 

((제 생각을 바꿔 댓글은 정말 환영합니다.))