알고리즘 공부를 정말 제대로 시작해보기로 했다. 예전에는 멋도 모르고 문제만 풀었다. 하지만 그러니까 오히려 머리에 남는 것이 없는 거 같더라.

이제는 <이것이 취업을 위한 코딩 테스트다>라는 책을 보면서 알고리즘의 기초 개념도 잡고, 그 개념과 연관된 문제들을 리트코드에서 찾아서 풀어볼까 한다.
그리고 내 솔루션 뿐만이 아닌, 다른 솔루션도 분석하고 그 솔루션으로도 문제를 풀 수 있도록 완벽하게 체화하고 넘어가려고 한다.

DFS/ BFS

컴퓨터 공학을 전공한 사람이나, 혹은 비전공자라도 알고리즘 문제를 접해봤다면 들어봤을 DFS, BFS를 보자. DFS, BFS는 트리나 그래프를 탐색할 때에 사용하는 탐색 방법이다.

DFS: 너비 우선 탐색

DFS란 너비 우선 탐색이다. 즉, 더 깊이 있는 노드을 우선적으로 탐색한다. 탐색한 노드의 sibling이 더 이상 없을때 (왼쪽, 오른쪽 node 가 None일때) 다시 최상단 parental 노드로 올라간다.

BFS: 깊이 우선 탐색

BFS란 깊이 우선 탐색이다. 즉, 인접 노드들부터 탐색을 진행한다.

Stack, Queue

그렇다면 위와 같은 탐색을 진행할 때 왜 stack, queue와 같은 자료 구조가 필요한 것일까? 어느 노드를 방문했고, 방문하지 않았는지를 기록하기 위해서이다. (이래서 자료 구조를 공부해야한다.)

DFS

 def DFS(start_node):
    	# 1) stack 에 첫 번째 노드 넣으면서 시작
        stack = [start_node, ]
        
        while True:
            # 2) stack이 비어있는지 확인 
            if len(stack) == 0:
            	print('All node searched.')
                return None
                
            # 3) stack에서 맨 위의 노드를 pop
            node = stack.pop()
                
            # 4) 만약 node가 찾고자 하는 target이라면 서치 중단!
            if node == TARGET:
            	print('The target found.')
                return node
            
            # 5) node의 자식을 expand 해서 children에 저장
            children = expand(node)
            
            # 6) children을 stack에 쌓기
            stack.extend(children)
            
            # 7) 이렇게 target을 찾거나, 전부 탐색해서 stack이 빌 때까지 while문 반복

BFS

def BFS(start_node):
    	# 1) queue 에 첫 번째 노드 넣으면서 시작
        queue = [start_node, ]
        
        while True:
            # 2) queue가 비어있는지 확인 
            if len(queue) == 0:
            	print('All node searched.')
                return None
                
            # 3) queue에서 맨 앞의 노드 를 dequeue (0번 인덱스를 pop)
            node = queue.pop(0)
                
            # 4) 만약 node가 찾고자 하는 target이라면 서치 중단!
            if node == TARGET:
            	print('The target found.')
                return node
            
            # 5) node의 자식을 expand 해서 children에 저장
            children = expand(node)
            
            # 6) children을 stack에 쌓기
            queue.extend(children)
            
            # 7) 이렇게 target을 찾거나, 전부 탐색해서 queue가 빌 때까지 while문 반복

Leetcode 100

이 문제를 풀기 위해서는 맨 위부터 하나하나 보면서, p와 q에서 탐색하는 노드의 숫자가 모두 같은지, 그리고 그 노드의 왼쪽 오른쪽도 같은지 확인해야한다. 즉, BFS를 사용하는 것이 편하다.

Approach 1. Recursion

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q: 
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right,q.right)

Approach 2. Iteration with Deque

from collections import deque 

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        def check(p, q):
            if not p and not q:
                return True
            if not p or not q:
                return False
            if p.val != q.val:
                return False
            return True
            
        deq = deque([(p,q),])
        while deq:
            p, q = deq.popleft()
            if not check(p, q):
                return False
            if p:
                deq.append((p.left, q.left))
                deq.append((p.right, q.right))
        return True

위의 솔루션은 내가 생소했던 자료구조인 deque와 recursion 대신에 iteration을 사용하는 방법이다. 마찬가지로 인접한 노드부터 탐색하므로 (left, right) BFS를 사용한다.

Reference
DFS, BFS의 개념을 이해하는 데에 매우 도움이 됐던 블로그 글이니 읽어보면 좋을 것 같다!
https://jeinalog.tistory.com/18