https://leetcode.com/problems/longest-univalue-path/

 

Longest Univalue Path - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


풀이 과정

트리에서 같은 숫자로 이루어져 있는 가장 긴 경로를 구하는 문제이다.

 

DFS로 리프 노드에서부터 체크하면서 부모 노드의 값이 왼쪽 자식 노드의 값과 같으면 left 변수를 증가, 오른쪽 자식 노드의 값과 같으면 right 변수를 증가시키면서 정답을 구해주면 된다.


소스 코드

# 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:
    result = 0
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            
            if node.left and node.left.val == node.val:
                left += 1
            else:
                left = 0
            if node.right and node.right.val == node.val:
                right += 1
            else:
                right = 0
            
            self.result = max(self.result, left + right)
            return max(left, right)
            
            
        dfs(root)
        return self.result



https://leetcode.com/problems/diameter-of-binary-tree/

 

Diameter of Binary Tree - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


풀이 과정

이진 트리의 지름, 즉 이진 트리의 노드들 사이의 가장 긴 경로를 구하는 문제이다.

 

이진 트리의 지름은 루트 노드와 리프 노드 사이의 거리이거나, 리프 노드와 리프 노드 사이의 거리이다. 루프 노트와 리프 노드의 사이의 거리는 트리의 높이를 구하면 해결할 수 있는 문제이지만 리프 노드와 리프 노드 사이의 거리는 어떻게 문제를 해결할 것인가?

 

DFS로 각 노드들에 리프노드와의 거리를 상태값으로 부여하자. 그러면 특정 노드를 루트로 하는 트리의 Diameter는 왼쪽 노드의 상태값 + 오른쪽 노드의 상태값 + 2가 된다.

 

이 모든 과정을 마쳤을 때, 루트 노드에 대해서 왼쪽 노드의 상태값 + 오른쪽 노드의 상태값 + 2를 더해주면 전체 트리의 지름을 구할 수 있다. 

 

자식 노드가 없는 경우에는 그 자식 노드의 상태값을 -1로 가정하고 계산을 진행해주어야 트리의 지름을 정상적으로 구할 수 있다.

 

 


소스 코드

# 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:
    longest = 0
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return -1
            
            left = dfs(node.left)
            right = dfs(node.right)
            
            self.longest = max(self.longest, left + right + 2)
            return max(left, right) + 1
        
        
        dfs(root)
        return self.longest

https://leetcode.com/problems/maximum-depth-of-binary-tree/

 

Maximum Depth of Binary Tree - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


풀이 과정

이진 트리의 최대 깊이를 구하는 문제이다.

 

트리도 (사이클이 없는) 그래프이므로 BFS, DFS등으로 모두 순회할 수 있다. 깊이는 BFS로 트리를 순회해주면 구할 수 있다.


소스 코드

# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        
        Q = collections.deque([root])
        depth = 0
        
        while Q:
            depth += 1
            for _ in range(len(Q)):
                cur_root = Q.popleft()
                if cur_root.left:
                    Q.append(cur_root.left)
                if cur_root.right:
                    Q.append(cur_root.right)
        
        return depth

https://leetcode.com/problems/network-delay-time/

 

Network Delay Time - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


풀이 과정

노드와 간선이 주어질 때, 노드 k에서 시작해서 모든 노드를 순회하는데 걸리는 최소 시간을 구하는 문제이다. 순회가 불가능하면 -1을 출력해야 한다.

 

그래프에서 최소 거리, 최소 시간 문제를 풀 때는 BFS, 다익스트라, 플로이드, 벨만포드 알고리즘을 떠올릴 필요가 있고 이 문제에서는 간선의 가중치가 음수가 아님이 보장되므로 다익스트라를 통해서 문제를 해결하면 된다.

 

시작점 K와 나머지 모든 점의 최소 거리를 구하고, 거리의 최대값이 모든 점을 방문하는데 걸리는 시간이므로 이를 출력해주면 된다.

 

모든 정점으로의 거리가 추가되었는지 확인하고, 추가되지 않은 정점이 있으면 모든 정점을 순회하는게 불가능하다는 의미이므로 -1을 리턴해주면 된다.


소스 코드

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        dist = collections.defaultdict(int)
        for u, v, w in times:
            graph[u].append((v, w))
        Q = [(0, k)]
        
        while Q:
            time, node = heapq.heappop(Q)
            if node not in dist:
                dist[node] = time
                for v, w in graph[node]:
                    temp = time + w
                    heapq.heappush(Q, (temp, v))
        
        if len(dist) == n:
            return max(dist.values())
        return -1

https://leetcode.com/problems/course-schedule/

 

Course Schedule - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


풀이 과정

어떤 지점을 방문하기 위해 방문해야 하는 선행 방문 지점이 주어질 때, 주어진 코스가 순회 가능한지 여부를 구하는 문제이다.

 

예를 들어 1을 방문하기 위해서 0을 방문해야 하고, 0을 방문하기 위해서 1을 방문해야 한다면, 두 지점 모두 방문이 불가능하므로 코스가 순회가 불가능하다고 할 수 있다.

 

문제에서 주어진 prerequisites를 그래프의 간선으로 생각해 그래프로 모델링 한 후, 그래프에서 사이클이 존재하면 코스가 순회 불가능, 사이클이 존재하지 않으면 코스가 순회가 가능하다고 판단해주면 된다.

 

visit set으로 방문점 파악, route set으로 사이클 존재 여부를 파악하게 하여 코드를 작성하였다. 방문점, 사이클 존재 파악시 in을 사용하면 시간복잡도가 O(N)이라 비효율적인 코드가 아닌가 하는 생각이 들 수 있다.

 

Python의 경우 list, tuple 자료형에서는 in 사용시 하나하나 순회하기 때문에 O(N)이지만, set이나 dictionary에서는 내부적으로 hash를 통해서 자료들을 저장하기 때문에 해시 충돌이 정말 많이 발생하지 않는 이상 O(1)로 작동한다.


소스 코드

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        route = set()
        visit = set()
        graph = collections.defaultdict(list)
        for a, b in prerequisites:
            graph[b].append(a)
        
        def dfs(x):
            if x in route:
                return False
            if x in visit:
                return True
            
            visit.add(x)
            route.add(x)
            
            for arrive in graph[x]:
                if not dfs(arrive):
                    return False
            
            route.remove(x)
            return True
    
        for x in list(graph):
            if not dfs(x):
                return False

        return True

https://leetcode.com/problems/reconstruct-itinerary

 

Reconstruct Itinerary - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


풀이 과정

JFK에서 시작하는, 주어진 모든 비행 티켓을 사용하는 여행 경로를 구하는 문제이다. 경로는 여러가지가 존재할 수 있지만 사전식 순서로 앞선 경로만을 출력해야 한다.

 

비행기 티켓을 딕셔너리에 전부 넣어놓고, JFK에서 시작해 DFS 방식으로 사전식 순서가 앞선 도착지를 우선으로 탐방하여 문제를 해결하였다.


소스 코드

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        graph = collections.defaultdict(list)
        answer = []
        for depart, arrive in sorted(tickets, reverse=True):
            graph[depart].append(arrive)
        
        def dfs(x):
            while graph[x]:
                dfs(graph[x].pop())
            answer.append(x)
        
        dfs('JFK')
        return answer[::-1]

https://leetcode.com/problems/subsets/

 

Subsets - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


풀이 과정

주어진 배열의 부분 집합을 구하는 문제이다.

 

재귀로 배열의 각 인덱스에 해당하는 원소가 부분 집합에 들어갈지, 안들어갈지 판단해주면서 answer 배열에 추가해주었다. 어떤 배열이 주어지던, 부분 집합에 공집합은 반드시 포함되므로, 정답 배열에 공집합을 넣어놓고 재귀 함수를 수행하였다.


소스 코드

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        answer = [[]]
        output = []
        
        def subset(index):
            if index >= len(nums):
                return
            output.append(nums[index])
            answer.append(output[:])
            subset(index+1)
            output.pop()
            subset(index+1)
        
        subset(0)
        return answer

https://leetcode.com/problems/combination-sum/

 

Combination Sum - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


풀이 과정

배열로 주어진 수들의 중복조합의 합이 target이 되는 경우를 구하는 문제이다.

 

https://greentea31.tistory.com/196?category=947572 

 

LeetCode - 77. Combinations [Python]

https://leetcode.com/problems/combinations/ Combinations - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next..

greentea31.tistory.com

위 문제를 해결했던 것 처럼 어떤 수를 고르고, 안고르고의 경우를 재귀함수로 계산하게끔 하였다. 단 이번 문제는 중복조합이므로, 어떤 수를 골랐어도 다음에도 또 고를 수 있으므로, 어떤 수를 골라서 sum_value가 증가하는 경우, 고를지 말지 판별해야 하는 index가 증가하게끔 하지 않았다.

 

어떤 수를 고르지 않는 경우에는 index+1을 시켜줘야 한다.

 

i 안 고름 -> i 안 고름 -> i 안 고름 -> 무한반복 -> i 고름

i 고름

 

는 같은 경우인데 연산 과정만 늘어나고 재귀를 탈출하지도 못하기 때문이다.


소스 코드

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        answer = []
        output = []
        
        def combination(index, sum_value):
            if sum_value >= target:
                if sum_value == target:
                    answer.append(output[:])
                return
            if index >= len(candidates):
                return
                
            output.append(candidates[index])
            combination(index, sum_value + candidates[index])
            output.pop()
            combination(index+1, sum_value)
        
        combination(0, 0)
        return answer

https://leetcode.com/problems/combinations/

 

Combinations - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


풀이 과정

주어진 n개의 원소의 리스트에서 k개의 숫자로 이루어진 조합을 구하는 문제이다.

 

https://greentea31.tistory.com/111?category=939228 

 

재귀로 조합 구현하기 [C++}

#include using namespace std; int output[10]; void go(int index, int selected, int max_number, int length) { if (selected == length) { for (int i = 0; i < length; i++) { cout << output[i] << ' '; }..

greentea31.tistory.com

 

위의 글의 코드를 구현하였다. 1~4까지의 수를 원소로 가진 리스트에서 2개를 뽑아 조합을 만들어야 한다면 1을 고르는 것과 안고르는 것, 2를 고르는 것과 안고르는 것, 3을 고르는 것과 안고르는 것, 4를 고르는 것과 안고르는 것... 이런식으로 구하다 골라야 하는 수가 4를 넘어가거나, 이미 고른 수가 2를 넘어가면 그만두게 하고, 이미 고른 수가 2개가 되는 경우마다 정답 배열에 추가해 주면 모든 조합을 구할 수 있다.

 

책에서 본 좋은 코드도 재귀 2에 기록해 두었고, itertools 모듈의 combinations 함수를 사용하면 문제를 더 쉽게 해결할 수 있다.

 


소스 코드

재귀 1

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        answer = []
        output = [-1 for _ in range(k)]
        
        def combination(index, selected):
            if selected == k:
                answer.append(output[:])
                return
            if index > n:
                return
            
            output[selected] = index
            combination(index+1, selected+1)
            combination(index+1, selected)
        
        combination(1, 0)
        return answer

 

재귀 2

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        results = []
        
        def combination(elements, start, k):  # 추가된 원소, 탐색 시작점, 넣어야 될 남은 원소 개수
            if k == 0:  # 다 넣었으면 정답 추가
                results.append(elements[:])
                return
            
            for i in range(start, n+1):
                elements.append(i)  # i를 넣는 경우
                combination(elements, i+1, k-1)
                elements.pop()  # i를 넣지 않는 경우
        
        combination([], 1, k)
        return results

 

itertools

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(itertools.combinations(range(1, n+1), k))

 

https://leetcode.com/problems/permutations/

 

Permutations - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com


풀이 과정

주어진 리스트의 순열을 구하는 문제이다.

 

itertools 모듈의 permutation 함수를 사용하면 문제를 쉽게 해결할 수 있다. 또한, DFS로도 순열을 생성할 수 있다.

 

https://greentea31.tistory.com/110?category=939228 

 

재귀로 순열 구현하기 [C++]

#include using namespace std; int discovered[10]; int output[10]; void go(int index, int max_number, int length) { if (index == length) { for (int i = 0; i < length; i++) { cout << output[i] << ' ';..

greentea31.tistory.com

 

위의 재귀로 순열을 구현하는 예제가 일종의 dfs - backtracking으로 순열을 구현한 것이다.

 

 

재귀 1의 소스코드에서, answer.append(output)을 사용하면 맨 마지막 output이 중복 저장되므로

 

1. answer.append(output[:])

 

2. answer.append([i for i in output])

 

3. import copy

    answer.append(copy.deepcopy(output))

 

등을 이용해주어야 한다.  위의 2방법은 객체 내의 내부 객체까지는 복사되지 않는 반면, deepcopy를 사용하면 깊은 복사가 되어 내부 객체까지 완벽히 복사된다. 이 문제에서는 리스트 내의 리스트까지 존재하지는 않으므로 위의 2방법을 사용해도 된다.

 

 


소스 코드

재귀 1

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        length = len(nums)
        output = [-1 for _ in range(length)]
        answer = []
        discovered = collections.defaultdict(bool)
        
        def go(index, length):
            if index == length:
                answer.append(output[:])  # answer.append(output) 사용시 맨 마지막 output값 중복 저장됨.
                return
            
            for num in nums:
                if not discovered[num]:
                    discovered[num] = True
                    output[index] = num
                    go(index+1, length)
                    discovered[num] = False
        
        go(0, length)
        return answer

 

재귀 2

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        prev_elements = []  # 이미 순열에 넣은 원소의 집합
        
        def dfs(elements):
            if len(elements) == 0:  # 모든 원소를 다 넣었으면 결과 값에 넣는다.
                results.append(prev_elements[:])
                # [:]가 없으면 prev_elements가 변경되면서 results에 들어갔던 값들도 변경된다.
            
            for ele in elements:
                prev_elements.append(ele)
                #  next_elements는 앞으로 순열에 넣어야 할 원소의 집합
                next_elements = elements[:]
                next_elements.remove(ele)
                
                dfs(next_elements)
                prev_elements.pop()
        
        dfs(nums)
        return results

 

itertools

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums))

+ Recent posts