leetcode (44) 썸네일형 리스트형 [리트코드] Balanced Binary Tree(python) 리트코드, Balanced Binary Tree_균형 이진 트리 TL;DR 트리(Tree) 깊이 우선 탐색(DFS) 문제 요약 1. 주어진 이진 트리가 높이 균형이 맞는지 아닌지를 판별하는 프로그램을 작성하라. 2. 높이 균형이 맞는 이진 트리는 모든 노드들의 왼쪽 및 오른쪽 서브 트리의 높이 차이가 1을 초과하지 않는 트리를 의미한다. - 형제 노드 간의 차이가 1을 초과하지 않을 때는 True를, 그렇지 않은 경우에는 False를 반환하면 된다. 입출력 형태 - 예시 1의 경우 모든 서브트리에서 높이 차이가 최대 1이다. 그렇기 때문에 True를 반환하였다. - 예시 2의 경우 가장 하위에 있는 서브트리와([3, 4, 4])가 루트의 서브트리([1, 2, 2])와 높이 차이가 1을 초과하기 때문에 f.. [리트코드] Serialize and Deserialize Binary Tree(python) 리트코드, Serialize and Deserialize Binary Tree(이진 트리 직렬화와 역직렬화) TL;DR 트리(Tree) 문제 요약 1. 주어진 트리를 컴퓨터에서 다루기 쉬운 형태로 변형하는 직렬화(Serialize)하는 코드를 작성하라. 2. 직렬화된 트리를 다시 원래의 형태로 되돌리는 역직렬화(Deserialize)하는 코드를 작성하라. 3. 이진 트리를 입력받아 문자열 형태로 직렬화 해야 하고, 직렬화된 문자열을 다시 이진 트리로 역직렬화할 수 있어야 한다. - 트리와 같이 논리적인 데이터 구조를 갖고 있는 자료 구조를 컴퓨터 내부에 저장하기 위해서는 물리적인 구조로 바꾸어주어야 할 필요가 있다. 이 때, 논리적인 데이터 구조에서 물리적인 데이터 구조로 변경하는 작업을 직렬화(Seri.. [리트코드] Network Delay Time(python) 리트코드, Network Delay Time_네트워크 지연 시간 TL;DR 너비 우선 탐색(BFS) 다익스트라 알고리즘(Dijkstra Algorithm) 문제 요약 1. 1부터 n까지 노드가 있는 네트워크가 주어진다. 주어진 네트워크는 출발 노드, 도착 노드, 출발 노드로부터 도착 노드까지 걸리는 시간을 의미한다. 2. 주어진 k 노드로부터 신호를 전달한다고 했을 때 모든 n개의 노드들 도는데 걸리는 시간을 반환하라. 3. 만약 모든 노드를 순회할 수 없다면 -1을 반환하라. - 주어진 k 노드로부터 그래프에 존재하는 모든 노드를 순회할 때의 시간을 반환하면 된다. 이는 가장 k 노드로부터 가장 먼 거리의 노드까지 걸리는 시간을 반환하면 된다. - 모든 노드를 순회할 수 있다면 BFS에서 조회할 수 있.. [리트코드] Reconstruct Itinerary(python) 리트코드, Reconstruct Itinerary_경로 재구성 TL;DR 깊이 우선 탐색(DFS) 문제 요약 1. 출발지와 도착지가 [출발지, 도착지] 형태로 주어진 배열에 대해서 경로를 재구성해서 반환하여라. 2. 'JFK'에서 출발하기 때문에 모든 입력에는 'JFK'가 있는 것이 보장된다. 3. 존재하는 여러 경로 중 가장 최소의 알파벳 순서로 된 경로를 반환해야 한다. 4. 모든 티켓은 최소 하나의 유효한 경로가 존재하며, 하나의 티켓은 한 번만 사용해야 한다. - 모든 티켓을 사용하여 만들 수 있는 경로 중 가장 최소이며, 알파벳 순서로 돌아다니는 경로를 반환하면 된다. 입출력 형태 - 예시 1의 경우, 그림에서 주어지는 그림과 같이 순서대로 이동하는 것이 유효한 최소 알파벳 순서의 경로이다. -.. [리트코드] Subsets(python) 리트코드, Subsets_부분집합 TL;DR 깊이 우선 탐색(DFS) 문제 1. 주어진 중복이 없는 정수 배열 nums에 대해서 생성할 수 있는 모든 부분 집합을 반환하라. 2. 정답 배열은 복사된 부분 집합을 포함해서는 안되며 정렬 순서에는 큰 상관이 없다. 입출력 형태 - 주어진 숫자 배열로 만들 수 있는 모든 부분 집합을 반환하면 된다. - 공집합 또한 부분 집합의 일부이므로 포함시켜야 한다. 풀이 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: answer = [] def dfs(index: int, subsets: List[int]): answer.append(subsets) for i in range(index, l.. [리트코드] Combination Sum(python) 리트코드, Combination Sum_조합의 합 TL;DR 깊이 우선 탐색(DFS) 문제 1. 주어진 구분된 정수 배열 candidates와 목표 정수 target에 대해서 조합한 숫자들의 합이 target이 되는 유일한 조합들의 배열을 반환해야 한다. 2. candidates 내에 동일한 숫자를 여러 번 고를 수 있으며, 만약 적어도 하나의 숫자가 다르다면 두 조합은 다른 조합이다. 3. 문제에서 target이 되는 조합의 수가 150보다 적은 것을 보장한다. - 주어진 정수 배열 candidates 내에 있는 숫자를 중복 선택한 조합들에 대해서 조합의 합이 target이 되는 배열을 반환하면 된다. 입출력 형태 - 주어진 정수 배열 [2, 3, 6, 7]에서 합이 7이 되도록 숫자를 조합하는 경우는.. [리트코드] Combinations(python) 리트코드, Combinations_조합 TL;DR 깊이 우선 탐색(DFS) 문제 분석 [1, n] 범위의 수로 만들 수 있는 k개의 모든 가능한 조합을 반환하라. - 1 ~ n 사이의 수에 대해서 k개를 뽑아 만들 수 있는 모든 조합을 반환하면 된다. 입출력 형태 - 1 ~ 4 사이의 숫자에서 2개를 뽑아 만들 수 있는 모든 조합을 반환하고 있다. - 만들 수 있는 조합의 개수는 공식(`n! / (n - k)!k!`)에 따라 6개가 반환되어야 한다. 틀린 풀이 class Solution: def combine(self, n: int, k: int) -> List[List[int]]: answer = [] def dfs(vertex: int, combinations: List[List[int]] = []).. [리트코드] Permutations(python) 리트코드, Permutations_순열 TL;DR DFS(깊이 우선 탐색) 문제 분석 1. 주어진 숫자 배열에 대해 만들 수 있는 모든 순열을 반환하라. 2. 반환된 배열은 어떤 순서로 되어 있어도 상관 없다. - 주어진 숫자들로 만들 수 있는 순열을 반환하면 된다. 입출력 형태 풀이 class Solution: def permute(self, nums: List[int]) -> List[List[int]]: answer = [] def dfs(v: int, permutation: List[int] = []): permutation.append(v) if len(permutation) == len(nums): answer.append(permutation) return for num in nums: if.. 이전 1 2 3 4 5 6 다음
