Scribbling

현재 node -> Flattened Left Tree -> Flattened Right Tree # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ if not root: return None head, tail = self.helpe..

그냥...DFS로 푼다... from collections import defaultdict import copy def solution(tickets): tickets.sort() # dictionary["ICN"] = ["ATL", "SFO"] dictionary = defaultdict(list) for ticket in tickets: dictionary[ticket[0]].append(ticket[1]) def dfs(cur, dictionary, edges, path): if not edges: return path for v in dictionary[cur]: next_dictionary = copy.deepcopy(dictionary) next_dictionary[cur].remove(v)..

이와 유사한 문제를 이미 풀어보았다. * for문 안에서 삭제할때는 항상 주의하자. https://focalpoint.tistory.com/101 LeetCode: 126. Word Ladder II - 시바견의 끄적임 개인적으로 어려웠던 문제... A. 내가 푼 방법 일단 내가 푼 방법은 아래와 같다. 1) 모든 word에 대해 graph를 그린다. (word간 글자가 1개만 차이나는 경우 연결) 2) 다익스트라 알고리즘으로 최단 경 focalpoint.tistory.com from collections import deque def solution(begin, target, words): if target not in words: return 0 words = set(words) words.disca..

그래프의 서로소 판별 문제이다. 아래 알고리즘을 그대로 사용한다. https://focalpoint.tistory.com/12 서로소 집합 알고리즘 v, e = map(int, input().split()) edges = [] for _ in range(e): edges.append(list(map(int, input().split()))) parent = [0] * (v+1) for i in range(v+1): parent[i] = i def find_parent(parent, a): if pa.. focalpoint.tistory.com def solution(n, computers): edges = [] for i in range(n): for j in range(i+1, n): if comput..

완전탐색이다. 어떻게 구현하냐가 핵심인데, 모든 숫자를 다 사용한다는 점을 이용하면, O(2**N)으로 풀 수 있다. answer = 0 def solution(numbers, target): global answer dfs(numbers, target) return answer def dfs(numbers, target): if not numbers: if target == 0: global answer answer += 1 return number = numbers[0] dfs(numbers[1:], target-number) dfs(numbers[1:], target+number)

1. 완전탐색 완전탐색으로 짜잔하고 풀리면 hard일리가 없지. 역시 Time Out class Solution: def numDistinct(self, s: str, t: str) -> int: self.answer = 0 self.dfs(s, t) return self.answer def dfs(self, s, t): if not t: self.answer += 1 return target = t[0] for i, char in enumerate(s): if char == target: self.dfs(s[i+1:], t[1:]) 2. DP 문자열을 탐색 혹은 비교하는 문제는 대부분 DP인 경우가 많다. 말그대로 dp다. 문제는 이것도 Time Out class Solution: def numDist..

DFS Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]: if not root: return [] self.ret = [] self.dfs(root, [], 0, targetSum) return self.ret def dfs(self, node, path, tempSum, targ..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]: if not head:..

연이은 값을 선택할 수 없는 문제는 전형적인 DP 문제로 많이 접해보았을 것이다. 다만 이 문제는 첫 번째 값과 마지막 값을 동시에 선택할 수 없다는 조건이 추가되어있다. 이에 따라, 첫 번째 값을 선택가능한 case와 마지막 값을 선택 가능한 case로 나누어 그 중 최댓값을 return한다. 1) 0th idx ~ (n-1)th idx 2) 1th idx ~ (n)th idx def solution(money): dp1 = [0] * (len(money) - 1) dp1[0] = money[0] dp1[1] = max(money[0], money[1]) for i in range(2, len(money)-1): dp1[i] = max(dp1[i-2]+money[i], dp1[i-1]) dp2 = [0..

def solution(m, n, puddles): dp = [[0] * m for _ in range(n)] dp[0][0] = 1 for i in range(1, m): if [i+1, 1] in puddles: continue dp[0][i] = dp[0][i-1] for i in range(1, n): if [1, i+1] in puddles: continue dp[i][0] = dp[i-1][0] for i in range(1, n): for j in range(1, m): if [j+1, i+1] in puddles: continue dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[n-1][m-1] % 1000000007