pythaac의 개발노트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 트리 계층형 트리 구조를 시뮬레이션 하는 추상 자료형 서로 연결된 노드의 집합 재귀로 정의된 자기 참조 자료구조 - Recursively Defined Self-Referential - 즉, 트리는 자식도 트리, 그 자식도 트리 (서브트리) 트리의 명칭 차수 (Degree) - 자식 노드의 개수 크기 (Size) - 차수 + 자신을 포함(1) 깊이 (Depth) - 루트에서 현재 노드까지의 거리 높이 (Height) - 현재 노드에서 리프 노드까지의 거리 (가장 깊은) 그래프 vs 트리 트리는 순환(cycle)이 없어야 함 - 간선을 따라 탐색했을 때, 이미 탐색된 노드를 다시 만나지 않음 트리는 부모 -> 자식 단방..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 K개 경유지 내에 도착하는 최소 가격 리턴 책에서 구현된 코드 # Fail def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int: graph = collections.defaultdict(list) for u, v, w in flights: graph[u].append((v,w)) Q = [(0, src, k)] while Q: price, node, k = heapq.heappop(Q) if node == dst: return price if k >= 0: for v, w in graph..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 출발지에서 각 노드까지 weight중 최대값 구하기, 못가는 노드가 있을 경우 -1 책에서 구현된 코드 def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int: graph = collections.defaultdict(list) for u, v, w in times: graph[u].append((v,w)) Q = [(0, k)] dist = collections.defaultdict(int) while Q: time, node = heapq.heappop(Q) if node not in dist: dist[node] = time ..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 최단 경로 문제 각 간선의 가중치 합이 최소가 되는 두 정점 사이의 경로를 찾는 문제 그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재 가장 유명한 것이 다익스트라 알고리즘 다익스트라 알고리즘 항상 노드 주변의 최단 경로만 택하는 대표적인 그리디 알고리즘 단순하고 실행 속도가 빠름 노드 주변을 탐색할 때 BFS를 이용 다익스트라 알고리즘 특징 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단 거리 계산이 끝났다고 가정 - 즉, 탐색을 위한 출발노드가 갖는 최단거리는 최단거리임이 보장되어야함 따라서, 음수를 처리할 수 없음 - 벨만-포드 알고리즘과 같이 음수 사용이 가능한 알고리즘 사용..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 우선순위가 있는 task들에 대해 모든 코스가 완료 가능한지 판별 책에서 구현된 코드 # 재귀 - Fail def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool: graph = collections.defaultdict(list) for x, y in prerequisites: graph[x].append(y) traced = set() def dfs(i): if i in traced: return False traced.add(i) for y in graph[i]: if not dfs(y): return False trac..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 JFK에서 출발하는 여행 일정 구성 책에서 구현된 코드 from collections import defaultdict def findItinerary(self, tickets: list[list[str]]) -> list[str]: graph = collections.defaultdict(list) for a, b in sorted(tickets, reverse=True): graph[a].append(b) route = [] def dfs(a): while graph[a]: dfs(graph[a].pop()) route.append(a) dfs('JFK') return route[::-1] 기억해야할 기..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 모든 부분 집합 리턴 책에서 구현된 코드 def subsets(self, nums: list[int]) -> list[list[int]]: result = [] def dfs(index, path): result.append(path) for i in range(index,len(nums)): dfs(i+1, path + [nums[i]]) dfs(0, []) return result 기억해야할 기법 조건 확인해서 필요없는 코드 제거하기 내가 구현한 코드 def subsets(nums: list[int]) -> list[list[int]]: result = [] def dfs(elts: list, s: in..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 숫자 집합을 중복 포함 조합하여 합이 target이 되는 원소들 나열 책에서 구현된 코드 def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]: result = [] def dfs(csum, index, path): if csum < 0: return if csum == 0: result.append(path) return for i in range(index, len(candidates)): dfs(csum - candidates[i], i , path + [candidates[i]]) dfs(target, 0, []..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 조합 구현 책에서 구현된 코드 # 재귀 def combine(self, n: int, k: int) -> list[list[int]]: results = [] def dfs(elements, start: int, k: int): if k == 0: results.append(elements[:]) return for i in range(start, n+1): elements.append(i) dfs(elements, i + 1, k - 1) elements.pop() dfs([], 1, k) return results # itertools def combine(self, n: int, k: int) -> l..

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 문제 정의 순열 구현 책에서 구현된 코드 # 재귀 def permute(self, nums: list[int]) -> list[list[int]]: results = [] prev_elements = [] def dfs(elements): if len(elements) == 0: results.append(prev_elements[:]) for e in elements: next_elements = elements[:] next_elements.remove(e) prev_elements.append(e) dfs(next_elements) prev_elements.pop() dfs(nums) return results ..