본문 바로가기

알고리즘/Leetcode

[leetcode]140. Word Break II, 파이썬 문제 릿코드 문제 링크 풀이 난이도 : hard 풀이, dfs 주어진 wordDict을 돌며 해당 단어로 시작하면 재귀로 돌려줌 s가 빈 채로 인자로 넘어왔다는 뜻은 주어진 wordDict 배열 원소로 문장 s가 완성 가능하다는 뜻이므로 ret에 words 리스트를 더해줌 문제 조건에 맞춰 리턴 코드 class Solution: def wordBreak(self, s, wordDict): ret = [] self.dfs(s, wordDict, ret, []) for i, e in enumerate(ret) : ret[i] = ' '.join(e) return ret def dfs(self, s, wordDict, ret, words): if not s: ret.append(words) fo..
124. Binary Tree Maximum Path Sum - 파이썬 문제 [릿코드 링크](https://leetcode.com/problems/binary-tree-maximum-path-sum/_ 이진트리의 각 노드를 한 번만 지날 수 있을 때 path의 최대값을 구하는 문제 풀이 난이도 hard 처음 풀었을 때 틀려서 다시 풀었다. 한 번만 지날 수 있기 때문에 결국 어느 노드에서 left와 right를 모두 포함할지 결정해야 한다.(어느 노드를 root 노드로 할지) path를 이어나가기 위해서는 왼쪽 혹은 오른쪽 중 하나만 선택해야 한다. 따라서 아래 코드를 실행하면 가장 밑에 level부터 cur_max를 갱신하게 된다. 밑에 있는 노드부터 차례로 path값을 계산한 후 path를 잇는 것이 더 값이 크면 이어나간다. 코드 class Solution: def m..
40. Combination Sum II, 파이썬 예전에 풀었을 때는 시간초과 때문에 틀렸던 것 같다. [1, 1, 1, 1, 1, 1, 1] 등에서 시간초과가 났었다 문제 1. 숫자들이 배열로 주어졌을 때 합이 target인 숫자 조합을 중복 없이 구하는 것. 풀이 1. 어려운 문제는 아니지만 중복을 피하고, 시간을 줄이는 것이 핵심. 2. target 8, [1, 1, 4, 6, 7] 이라고 했을 때 [1, 1, 6] 은 체크하고 [1, 7], [1, 7] 이 중복이 나오지 않게 해야한다. 3. 따라서 정렬된 배열에서 path에서 arr[i] 값이 중복되어 다음 dfs로 넘어가지 않도록 체크해준다. class Solution(object): def combinationSum2(self, candidates, target): ret = [] self...
22. Generate Parentheses - 파이썬 이 문제는 dfs로 풀려다 뭔가 꼬여서 틀렸던 문제이다. 릿코드는 일단 200번까지 푸는게 목표인데 145번을 풀고 있는 지금 다시 풀어보니 풀렸다. Medium에서 알 수 있듯 그다지 어려운 문제는 아닌데 전형적인 문제라 남겨준다. 문제 1. n이 주어졌을 때 가능한 괄호 닫기 모든 경우의 수. 2. Parentheses가 무슨 뜻인지 몰라 검색했던 기억이 난다... ^^ 풀이 1. 핵심은 "(" , 즉 괄호가 열려있던 적이 있어야 괄호 닫기 ")"를 사용할 수 있다는 점. n이 충분할 때 "((" 는 가능하지만 "())"는 불가능 2. n의 개수만큼 (를 사용 할 수 있고 사용할 때마다 스택에 )를 쌓아 둔다. 3. 재귀와 스택을 활용 개선점 1. 무언가 코드가 너저분 2. 변수가 너무 많아 직관성이..