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)

Python Class 관련하여 잘 몰랐던 부분을 정리해둔다. 1. 비공개 속성 및 메서드 속성이나 메서드에 "__"를 붙이면 클래스 외부에서 접근할 수 없다. class person: def __init__(self, name, nickname): self.name = name self.__nickname = nickname def __tease(self): print(self.__nickname) 2. 클래스 속성 클래스 속성은 아래처럼 선언가능하며, 클래스명으로 접근하는 것이 가독성에 좋다. class Person: all_names = [] def __init__(self, name): Person.all_names.append(name) self.name = name 3. 정적 메서드 (Stat..

클로저는 간단히 말해 함수 안에 함수를 만드는 것이다. 클로저를 사용하는 이유는 크게 두가지이다. 1) 코드와 지역 변수를 묶어서 사용 가능하다. 2) 지역 변수를 숨기고 싶을 때 사용한다. 아래는 클로저의 예시이다. - 함수가 종료되어도 a, b 값이 유지되는 것을 확인할 수 있다. - nonlocal keyword를 이용하여 지역 변수의 변경이 가능하다. def line(a, b): total = 0 def get_value(x): nonlocal total total += a * x + b print('현재 누적 합: ' + str(total)) return a * x + b return get_value c = line(1, 2) print(c(1)) print(c(2)) print(c(3)) c..

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:..