junhwa100 님의 블로그

1. 문제 이해오름차순으로 정렬된 배열을 Height Balanced BST로 변환하는 문제이다.  2. 풀이 과정BST를 만들기 위해서 정렬된 배열을 이진 검색으로 쪼개 나가야 한다. 중앙값의 인덱스를 구하기 위해서 배열의 길이를 2로 나누어서 내림을 한다.mid = len(nums)//2 중앙값의 인덱스를 이용하여 분할 정복을 구현한다.node = TreeNode(nums[mid])node.left = self.sortedArrayToBST(nums[:mid])node.right = self.sortedArrayToBST(nums[mid+1:])  3. 전체 코드class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[Tre..

1. 문제 이해이진 트리를 반전시키는 문제다.반전시킨 뒤, root 노드를 리턴한다.  2. 풀이 과정큐를 이용한 반복 구조로 BFS 알고리즘을 구현한다. 처음 구현한 코드는 다음과 같다.class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root is None: return queue = collections.deque([root]) while queue: for _ in range(len(queue)): cur = queue.popleft() ..

1. 문제 이해이진 트리에서 같은 value를 가지는 노드들의 가장 긴 경로의 길이를 구하는 문제이다.(경로의 길이는 두 노드 사이 엣지의 개수이다.) 2. 풀이 과정DFS 알고리즘으로 리프 노드까지 탐색한다.백트래킹하면서 value가 일치하면 거리를 증가시킨다.def dfs(node: TreeNode) -> int: left = dfs(node.left) right = dfs(node.right) #이 값이 백트리킹되면서 증가한다. if node is None: return 0 백트래킹 과정에서 왼쪽과 오른쪽의 자식 노드를 각각 확인해서 왼쪽과 오른쪽의 거리를 각각 증가시킨다.왼쪽과 오른쪽 거리를 각각 계산한다는 발상이 중요하다.if node..

1. 문제 이해이진 트리의 diameter의 길이를 구하는 문제이다.diameter의 길이는 이진 트리의 두 노드 간의 가장 긴 경로의 길이이다.  2. 풀이 과정두 노드 간 가장 긴 경로의 길이는 루트 노드에서 왼쪽 방향과 오른쪽 방향의 최대 깊이의 합이다.어떻게 각 방향의 최대 깊이를 구할 수 있을까? DFS 알고리즘을 통해 왼쪽, 오른쪽 방향 각각의 리프 노드를 찾는다.더 노드가 존재하지 않는다면 -1을 리턴한다.def dfs(node: TreeNode) -> int: if not node: return -1 left = dfs(node.left) right = dfs(node.right) 리프 노드에서 거슬러 올라가며 상태값을 업데이트한다.(상태값은 리프 노드에서 현..

1. 문제 이해도시(노드)의 개수 n이 주어진다. n개의 도시들은 각각 0~n-1로 라벨링 된다.flights 리스트가 주어진다. 하나의 flights 요소는 (출발 도시, 도착 도시, 가격) 형식이다. src, dst, k라는 세 가지 integer가 주어진다.최대 k개의 경유지를 거쳐서 src 노드에서 dst 노드로 가는 가장 저렴한 가격을 구해야 한다.만약 그런 루트가 존재하지 않는다면 -1을 리턴한다.  2. 풀이 과정flights를 딕셔너리 형태의 그래프로 구성한다.graph = collections.defaultdict(list)for u, v, w in flights: graph[u].append((v, w)) 가중치가 있는 그래프에서 일종의 최단 경로를 구하는 문제이다. 우선순위 큐를 이용..

1. 문제 이해노드의 개수 n이 주어진다. n개의 노드들은 각각 1~n로 라벨링 된다. 또 times 리스트가 주어지는데 하나의 times 요소는 (출발 노드, 도착 노드, 소요 시간) 형식이다.마지막으로 k가 주어지는데 k는 신호가 시작되는 노드이다.  k 노드에서 출발하여 n개의 노드들에 신호를 모두 전달하는 최소 시간을 구해야 한다.만약 n개의 노드들에 신호를 전달하는 것이 불가능하다면 -1을 리턴한다.  2. 풀이 과정times를 딕셔너리 형태의 그래프로 구성한다.graph = collections.defaultdict(list)for u, v, w in times: graph[u].append((v, w)) 가중치가 있는 그래프에서 일종의 최단 경로를 구하는 문제이다. 우선순위 큐를 이용한 Di..

1. 문제 이해이진 트리의 최대 깊이를 구하는 문제이다.만약 입력이 root = [3,9,20,null,null,15,7]라면 이진 트리는 아래와 같다. 이때 결과는 3이 나온다.  2. 풀이 과정트리의 최대 깊이를 구하기 위해서는 트리의 root에서 레벨을 한 단계씩 높여가며 확인해야 한다. BFS는 같은 레벨에 있는 노드들을 다 확인한 뒤, 다음 레벨로 넘어가므로 풀이에 적합하다. BFS는 통상적으로 큐를 이용한 반복 구조를 활용한다.같은 레벨의 노드들을 큐에 넣고 pop하여 자식 노드가 있는지 확인하고 있다면 자식 노드를 큐에 넣는 과정을 큐에 노드가 존재할 때까지 반복해 보자. "def maxDepth(self, root: Optional[TreeNode]) -> int:" 에서 Optional[..

1. 문제 이해코스 n개와 코스 간의 관계를 입력으로 받는다. 그리고 모든 코스가 완료 가능한지 판단하여 true, false로 출력을 하도록 한다.ex). 입력이 2, [[1, 0]]이면 코스가 2개 있고 1을 완료하기 위해 0을 끝내야 하는 관계가 존재한다는 뜻이다. 이는 가능하므로 true가 출력된다.  2. 풀이 과정언제 false가 출력될까? Cyclic 구조가 존재한다면 false로 출력된다. 닭이 먼저냐 달걀이 먼저냐 같은 문제다. 코스 간의 관계를 그래프로 표현해야 한다. 딕셔너리로 만든다.graph = collections.defaultdict(list)for a, b in prerequisites: #a를 완료하기 위해 b를 끝내야 한다. graph[a].append(b) 그래프에서 C..