문제 정보 Leet Code 문제 링크 난이도 : Medium 해결 방법 pay[val] 을 val 가격을 지불하는데 필요한 최소 코인 갯수 라고 정의한다면 Dynamic Programming 를 사용할 수 있습니다. pay[코인 중 1개의 가격] = 1 이고 pay[코인1 가격 + 코인2 가격] = 2 이므로 가능한 가격들 중 최소값을 구할 수 있기 때문입니다. Dynamic Programming 을 사용하면서 묘하게 불필요한 연산이 들어가는 것 같이 느꼈었는데, 지금까지는 거의 DP 풀이를 Top-Down 방식을 사용했고 Memoization 으로 구현했었습니다. 그런데 이번 문제는 Bottom-Up 방식을 사용했고 Tabulation 으로 구현했습니다. Memoization 은 재귀를 이용하기 때문..

문제 정보 Leet Code 문제 링크 난이도 : Easy 해결 방법 문제 자체가 기본적인 Dynamic Programming 의 꼴을 하고 있어서 그렇게 구현했습니다. dp 함수를 따로 사용하지 않고 배열에 for loop 를 순회하면서 데이터를 채워 넣어도 구현이 가능합니다. 소스 코드 // Leet Code // #70. Climbing Stairs // Success // Runtime: 72 ms, faster than 74.80% of JavaScript online submissions for Climbing Stairs. // Memory Usage: 38.6 MB, less than 58.88% of JavaScript online submissions for Climbing Stairs..

문제 정보 Leet Code 문제 링크 난이도 : easy 해결 방법 첫 시도에는 단순히 이중 for loop 를 사용하여 O(n^2) 의 시간이 걸리게 구현하니 Time Limit Exceeded 을 판정되었습니다. 두 번째 시도에서는 prices 를 두번 순회하지 않기 위해 고민을 하던 중에 변화량을 기록하는 diff 라는 Array 를 만들고 최대 부분합을 구할 수 있는 Dynamic Programming 을 사용하여 값을 구했습니다. ( 참고로, 최대 부분합을 구하는 이 알고리즘을 카데인 알고리즘이라고 한다고 합니다. 기존 DP 와 내용은 같긴한데... 자주 등장하기 때문에 그런것 같습니다. ) 이렇게 풀고 나서 Solution 탭을 확인해보니 for loop 마다 minPrice 와 maxPro..

문제 정보 프로그래머스 문제 링크 난이도 : level 4 해결 방법 현재까지 확인한 idx 번째 집에서 털 수 있는 돈의 최댓값을 dict 에 key-value 형태로 저장했습니다. 집 사이의 간격은 최대 3칸이 될 수 있어서 헷갈렸는데 ( 아래 이미지에 고뇌의 흔적이 보입니다. ) 현재까지 확인한 이라는 조건이 붙기 때문에 방범장치가 영향을 줄 수 있는 2칸만 확인하면 됩니다. 점화식으로는 아래와 같이 나타낼 수 있습니다. newDp = max(memoization1[idx - 1], memoization1[idx - 2] + money[idx]) 그리고 첫 번째 ( idx 값으로는 0 ) 집을 털지 여부를 판단하기 위해 selZero 라는 변수로 판단했습니다. 첫 번째 집을 털게 되면 마지막 집을 ..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 왼쪽 위 (1, 1) 부터 오른쪽과 아래로만 이동할 수 있는 최단거리 문제로 중학교(?) 교과 과정에서 많이 풀던 경로 문제입니다. 왼쪽 위부터 갈 수 있는 경우의 수를 표시하면서 왼쪽과 위의 경우의 수를 순차적으로 합산하여 구현할 수 있습니다. 그래서 Dynamic Programming 알고리즘을 사용해 구현했습니다. 처음 구현할 때는 두 가지 문제점이 있었는데 첫 번째는 중간에 웅덩이가 있을 경우 지나가지 못하는 경우를 중복으로 세서 물 웅덩이가 많을 경우 음수로 나와버리는 경우를 발견했는데 물 웅덩이에서의 경로의 수를 0 으로 세팅하여 해결했습니다. 두 번째는 위에서 기술했듯이 예전 교과 과정에서 많이 풀던 방식으로 인해 생긴 문..

문제 정보 프로그래머스 문제 링크 난이도 : level 3 해결 방법 1. 문제에 명시된 대로 거쳐간 숫자의 합이 가장 큰 경우를 찾기 위해 Top-down 방식의 DP 를 사용하여 구현했습니다. 제출하니 시간이 많이 초과되어 다른 방법의 풀이를 시도했습니다. 2. 모든 경로를 반복해서 수행하지 않도록 특정 경로까지의 최대 값을 triangle 배열에 update 했습니다. 짧은 경로는 금방 구할 수 있기 때문에 Bottom-up 방식으로 구현했습니다. 소스 코드 # 시간초과 def solution(triangle): answer = 0 answerList = [] def dp(depth, curSum, idx): curNum = triangle[depth - 1][idx] curSum += curNum..