소피it블로그

https://leetcode.com/problems/maximum-depth-of-binary-tree/ Maximum Depth of Binary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 재귀적으로 풀 수 있었다. 다이나믹 프로그래밍의 원리를 이용해서, 특정 노드에서의 최대 깊이는 자식 노드의 최대 깊이에 1을 더한 것이라는 점에 착안하여 풀었다. 다만 재귀적으로 푸는 과정에서 바로 max값을 구해주었기 때문에 메모이제이션은 사용하지 않았다..

https://leetcode.com/problems/climbing-stairs/ Climbing Stairs - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이거 DP일것 같다고 직접 그래프도 그려놓고선 왠지 자신이 없어서 다른 방법 고민하다가 시간 너무 많이 썼다. 뭔 itertools permutations 이런거 찾아보고 divmod로 고민해보고 증말........ 진짜 속쓰리다. 결론부터 말하면 너무나도 DP인 문제 맞다. n = 5라고 했을 때 (..

문제 출처: https://youtu.be/5Lu34WIx2Us 이 문제가 다이나믹 프로그래밍 유형인 이유를 먼저 생각해보자. 2, 3원을 가지고 15원을 만들 수 있는지, 있다면 최소한의 화폐 개수는 몇 개인지 알기 위해서는 어떻게 해야 할까? 15원을 만들기 위한 최소한의 화폐 개수를 f(15)라고 하자. (15원에서 2원을 뺀) 13원과 (3원을 뺀) 12원을 만들 수 있다면, 각각 +2원 or +3원의 과정을 한 번만 더 하면 15원을 만들 수 있을 것이다. 즉, f(15)의 최솟값은 min(f(13), f(12)) + 1원이 된다. 13원일 때의 최소 화폐 개수와 12원일 때의 최소 화폐 개수를 비교하여 거기에 한 번의 연산만 더해준다면 f(15)를 구할 수 있다는 것. 그렇다면 f(13)과 f..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net https://youtu.be/5Lu34WIx2Us 병사 배치하기 문제를 풀려다가 이 문제 먼저 푸는 게 나을 것 같아서 풀어보았다. 역시나 다이나믹 프로그래밍의 일종으로, 동빈님의 강의의 도움을 받았다. 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence) D[i] = arr[i]를 마..

문제, 풀이 출처: https://youtu.be/5Lu34WIx2Us 이 문제 역시 1) 최적의 부분 구조와 2) 중복되는 부분 문제라는 조건을 만족시키기 때문에 다이나믹 프로그래밍으로 접근하여 풀 수 있다. 핵심은, 한 칸 이상씩 떨어진 식량 창고를 털어야 하기 때문에 마지막 n번째 식량 창고에 대하여 1) i - 1 번째 식량 창고까지의 최적의 해 2) i - 2 번째 식량 창고까지의 최적의 해 + i번째 식량 창고에 저장된 식량 둘 중 더 큰 값을 선택하면 된다는 것. 그리고 각각은 부분 문제로 반복된다는 점을 파악하는 게 중요하다. i번째 창고까지의 최적의 해를 Ai라고 하고, i번째 창고에 있는 식량의 양을 Ki라고 한다면 다음과 같은 점화식이 성립한다. Ai = max(Ai-1, Ai-2 +..

자료 출처: https://youtu.be/5Lu34WIx2Us 이전까지는 다이나믹 프로그래밍이 뭔지 아예 모르고 이름만 많이 들어봤었는데, 이 강의 덕에 개념이 잡혔다. 문제를 아주 많이 풀어봐야 할 것 같다. 1. 다이나믹 프로그래밍 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법으로, 이미 계산된 결과는 별도의 메모리 영역에 저장한다. 조건 최적 부분 구조 (Optimal Substructure): 큰 문제를 작은 문제로 나눌 수 있는 경우. 즉, 작은 문제의 답을 모아 큰 문제를 해결할 수 있음 중복되는 부분 문제 (Overlapping Subproblem): 동일한 작은 문제를 반복적으로 해결해야 함 다이나믹 프로그..