IT's me

다이나믹(동적 계획법) 알고리즘 기초 문제 : 계단 오르기 (백준)

이번 문제를 풀면서 느낀 점은

다이나믹(동적 계획법) 알고리즘을 풀 때에는

답을 저장하는 DP배열이 꼭 필요하다는 것이다.

답을 담을 변수를 하나만 선언해서 이리저리 굴려보다가 결국 제시간에 풀지 못했다.

동적 계획법은

첫 째, 그 전에 구해놓은 답을 사용하여 현재의 답을 찾는 것!

둘 째, 구한 답을 저장할 DP배열을 사용할 것!

셋 째, 문제를 잘 읽고 규칙을 찾아 내는 것!

지금까지 다이나믹(동적 계획법) 알고리즘을 풀면서 중요하다고 느낀 부분이다.

익숙해질 때까지 반복적으로 문제를 풀어보는 것이 중요할 듯 하다.

계단 오르기 (백준)

문제를 처음 딱 접했는 때에는

DFS 알고리즘으로도 풀 수 있겠다 생각했지만,

동적 계획법으로 푸니 정말 간단하게 답이 나왔다.

짧은 코드로 많은 것을 해내는 코드는 그 만큼 어렵다고 했다.

위의 코드는 매우 간단해보이지만, 이 문제를 DFS 알고리즘으로

푼다고 생각했을 때는, 이렇게 간단한 코드로 끝나지 않을 것이다.

(물론 DFS도 그리 긴 코드는 나오지 않을 것이다.)

다이나믹 (동적 계획법) 알고리즘 기초 문제 : 숫자 삼각형 (백준)

첫 문제를 풀고나서 푸니까 확실히 시간이 단축된다.

원리에 좀 더 익숙해진다면 점점 더 단축되리라 믿는다.

다이나믹(동적 계획법) 알고리즘 기초 : 숫자 삼각형

RGB 거리라는 비슷한 문제를 풀고

바로 풀어서 그런지 시간이 15분 밖에 안걸렸다.

RGB와 같은 원리지만 위에서 아래로 향했던 것과 달리

이 문제는 아래에서 위로 계산하며 올라가야 한다.

다시한번 말하지만 다이나믹(동적 계획법) 알고리즘의 핵심은

구해놓은 답을 활용하여 현재의 답을 차근차근 찾아 나가는 것!!

꼭 기억하고 문제를 푼다면 더욱 이해하기 쉬울 것이다.

가장 밑의 바로 위층 부터 시작해서

(가장 밑 층의 데이터를 이용하여 밑의 바로 위층을 갱신하기 때문에 여기부터 시작한다.)

최대 값만을 골라 그 위치에 더하면서 갱신한다.

그렇다면 현재층의 모든 숫자는 아래층으로부터 올라온 최대값을 골라서 더하게 되며,

결국 꼭대기에서는 가장 최대값만을 골라서 더한 값이 저장되게 된다.

다이나믹(동적 계획법) 알고리즘은 코드의 크기는

DFS, BFS보다 훨씬 간결하다. 하지만 두 알고리즘 보다

훨씬 많은 고민을 해야하는 것은 분명한 사실인듯 하다.

다이나믹 (동적 계획법)알고리즘 기초 문제 : RGB 거리 (백준)

다이나믹 (동적 계획법) 알고리즘의 기초 문제를 풀어 보았다.

핵심은!! 그 전에 저장되었던 답을 끌어다가 현재의 답을 도출한다는 점!!

딱 저거 하나만 알면되는데.. 그 과정을 생각하기가 정말 쉽지 않다.

동적 계획법 기초 문제 : RGB 거리

몇줄 안되는 코드이지만 푸는 데 시간이 꽤 걸렸다..

잊지 말자!

처음 부터 차근차근 답을 구해서

구한 답을 바탕으로 계속해서 답을 찾아 나가는 것!

이번 문제는 기준을 잡는 것이 중요해 보였다.

처음에 집을 어떤 색으로 칠할 것이냐?

빨강, 초록, 파랑으로 모두 칠하면서 답을 찾아가봄

다이나믹 (동적 계획법) 알고리즘은

항상 풀 때마다 많은 고민을 하게 하는 것 같다.

꾸준히 풀어나가야 겠다는 생각이 든다.