소피it블로그

https://leetcode.com/problems/daily-temperatures/ Daily Temperatures - 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 문제 자체는 그렇게 어렵지는 않다. 인덱스 값들을 저장해둘 필요가 있다는 점만 파악하면 스택으로 쉽게 구현이 가능하다. 그런데 enumerate로 값과 함께 저장하려고 하니 시간 제한에 걸린 반면, 인덱스만 저장했을 때는 잘 풀렸는데 도대체 이유가 뭔지 아직도 잘 모르겠다. enumerate..

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://leetcode.com/problems/longest-substring-without-repeating-characters/ Longest Substring Without Repeating Characters - 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를 활용해야 하는 문제인 것 같기는 했는데, 아직 해당 유형을 많이 풀어본 적이 없는지라 어떻게 풀어야 할지 막막해서 계속 코드를 썼다 지웠다 하고 종이에 그림도 그렸다 포기도 했다 온갖 ..

문제 출처: 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]를 마..