소피it블로그

문제, 풀이 출처: 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://leetcode.com/problems/add-two-numbers/ Add Two Numbers - 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 아주 간단한 링크드 리스트 문제인데, 나는 링크드 리스트에 대한 개념 정도만 있지 실제로 구현해서 문제풀이에 사용해본 경험은 거의 없었기 때문에 이 문제로도 꽤나 많은 오류를 거쳤다. 애초에 문제 자체는 연결 리스트를 숫자로 바꿔서 더한 후 다시 연결 리스트로 바꾸라는 의도는 아니었던 것 같으나, 나는..

https://leetcode.com/problems/flood-fill/ Flood Fill - 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 분명 어려운 문제는 아닌데 아직도 bfs에 완전히 익숙해지지가 않아서 꽤 헤맸다. 특히, dx, dy로 리스트를 만들어놓고 다른 노드를 방문하는 방법이 아직 익숙하지 않아 우선은 중복되고 장황한 while문을 썼다. 또한, 처음에는 visited 리스트를 따로 만들려고 했으나, 풀다보니 굳이 그럴 필요 없이 방문한 곳의..

https://leetcode.com/problems/binary-tree-inorder-traversal/ Binary Tree Inorder Traversal - 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 아직도 dfs-재귀 코드를, 개념적으로는 알겠는데 직접 구현해내는 것은 어렵다. 자꾸 삐걱거리고 이상한 살을 붙여버린다고 해야 할까. 재귀의 끝부분이 완전히 이해되지는 않는 느낌이다. 많이 풀다 보면 나아지려나. class Solution: def in..

https://leetcode.com/problems/evaluate-reverse-polish-notation/ Evaluate Reverse Polish Notation - 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 스택에 관한 기본적인 문제로, 크게 어렵지는 않았으나 음수를 고려 못하고 .isnumeric()을 써댄 탓에 꽤 헤맸다. 다른 답안 찾아다 놓고 일일이 한줄씩 고쳐가면서 간신히 오류를 파악함. 또한, 흥미롭게도 stack.append(toke..

https://leetcode.com/problems/valid-parentheses/ Valid Parentheses - 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 스택 클래스를 따로 구현하여 pop, push 메서드를 구현해줘도 되나 편의상 솔루션 클래스 안에 리스트 형식의 스택을 구현했다. class Solution: def isValid(self, s: str) -> bool: stack = [] for c in s: if c == "[" or c =..