코딩테스트 마스터의 길 (2)

백상휘·2023년 3월 30일

BFS DFS Swift_Coding_Test queue stack 코딩테스트_마스터의_길

CodingTest

목록 보기

2/6

앞으로 누누이 얘기할 것이지만 이건 "알고리즘 마스터를 위한 길" 이 아니다.

코딩 테스트 결과를 기반으로 다음 전형 진행여부를 결정 하는 회사에 지원해 보았다.

4월5일 오후6시 링크로 들어가 테스트를 보면 된다. 오늘이 코딩테스트 마스터의 길 2일째(3/30) 인데 4월5일까지 전력질주하게 생겼다. 마스터의 길은 험난하고 고되다.

난감한 건 개인 프로젝트 화면 Rotation 관련해 코딩하는 것도 멈출 수는 없다는 것이다. 코딩테스트만 잘 봐서는 개발자로서 재미는 있을 수 있겠지만 돈은 못 번다.

테스트 관련 책도 읽고 있는데.... 코딩테스트 연습하면 좌절할 일이 많을텐데, 그럴 시간도 없이 바쁘게 생겼다.

어려운 것부터 해결해버리기

시간이 부족한 건 사실이다. 하지만 실패할 때 실패하더라도 할만큼 하고 실패하는거다.

개인적으로 코딩테스트 출제자는 일종의 개미털기를 위해 DFS/BFS 를 많이 출제한다고 생각한다. 대부분 코딩테스트 고레벨 문제도 DFS/BFS 다.

구글로 찾아보니 훌륭한 포스팅은 많았지만 내가 직접 공부하던 자료를 한번 들여다보기로 했다.

이 책은 자료구조&알고리즘을 Swift 로 풀어낸 책이다. 좋긴 좋은데 굉장히 내용이 많고 영어라서 공부하기가 쾌적하지는 않다. 그래도 Swift 로 이만큼 자세히 자료구조&알고리즘을 다뤄준 책은 드물다고 생각한다.

두 알고리즘의 구현을 잠깐 보니 세 개의 자료구조 구현이 필요했다.

Queue
Stack
Graph

우선 자료구조 구현부터 실습이다.

Graph 를 깊이 공부하는 것은 DFS/BFS 보다 공부할 것이 더 많은 것 같아서 단순히 [Int: [Int]] 로 대체하기로 하였다.

let graph: [Int: [Int]] = [
    1 : [8, 5, 2],
    8 : [1, 6, 4, 3],
    5 : [1],
    2 : [1, 9],
    6 : [8, 10, 7],
    4 : [8],
    3 : [8],
    9 : [2],
    10 : [6],
    7 : [6]
]

Queue(QueueStack)

이건 간단하다.

Queue 에 left/right Stack 을 개념을 끼얹은 것인데 약간 복잡하지만 금방 이해할 수 있다.

// 배열을 사용하기 때문에 공간복잡도 상으로 유리
struct Queue<T> { 
	private var leftStack: [T] = []
    private var rightStack: [T] = []
    
    var isEmpty: Bool {
    	leftStack.isEmpty && rightStack.isEmpty
    }
    
    var peek: T? {
    	leftStack.isEmpty == false ? leftStack.last : rightStack.first
    }
    
    // enqueue 할 때는 rightStack 에 보관
    mutating func enqueue(_ element: T) {
    	rightStack.append(element)
    }
    
    // dequeue 할 때는 leftStack 에서 하나씩 반환.
    // leftStack 이 비었다면 rightStack 뒤집어서 leftStack 에 저장한 뒤 하나씩 반환.
    @discardableResult
    mutating func dequeue() -> T? {
    	if leftStack.isEmpty {
        	leftStack = rightStack.reversed()
            rightStack.removeAll()
        }
        
        return leftStack.popLast() // O(1)
    }
}

Stack

이것도 간단하다.

struct Stack<T> {
	private var elements: [T] = []
    
    init() {}
    init(_ elements: [T]) {
    	self.elements = elements
    }
    
    var isEmpty: Bool {
    	peek() == nil
    }
    
    mutating func push(_ element: T) {
    	elements.append(element)
    }
    
    @discardableResult
    mutating func pop() -> T? {
    	elements.popLast()
    }
    
    func peek() -> T? {
    	elements.last
    }
    
    func contains(_ element: T) -> Bool {
    	elements.contains(element)
    }
}

그럼 이를 토대로 노션 AI 가 휘리릭 만들어준 소스코드를 정리해보자.

BFS 와 DFS 정의

DFS 를 포함해서 BFS 는 경로 탐색을 위한 알고리즘이다. root 부터 시작하여 차례로 탐색을 하는데 각각 단점과 장점이 존재한다.

BFS 는 root 부터 아래로 쭉 탐색을 한다. 왼쪽 자식노드부터 탐색을 시작해서 처음 방문한 자식 노드의 자식 노드까지 왼쪽으로 모두 탐색해야 다음 노드로 넘어간다.

DFS 는 약간 다르다. 시작점이 root 인 것은 같다. 하지만 왼쪽 자식노드를 처음 만나 탐색했다면 자식노드의 자식으로 가는 것이 아니다. 아까 탐색한 노드 탐색이 끝나면 이웃한 오른쪽의 노드로 탐색을 시작한다.

즉, 같은 레벨의 노드들을 모두 검색하고 다음 레벨의 노드들을 모두 검색하는 식이다.

역시 그림이 짱이다. 나도 예전에 한번 본 기억이 있는 그림이다.

출처: https://covenant.tistory.com/132

이제 이론은 한번 짚었으니, Notion AI 로 만든 구현체를 가지고 나만의 구현체를 만들어보기로 한다.

// 빈 path 를 inout 파라미터로 전달하여 반환받는 느낌
func dfs<T: Equatable>(
  _ graph: [T: [T]]
  , start: T
  , target: T? = nil
  , visited: inout [T]
  , path: inout [T]) -> Bool {
    
    visited.append(start)
    path.append(start)
    
    if start == target {
      return true
    }
    
    for neighbor in graph[start] ?? [] {
      if
        visited.contains(neighbor) == false // 방문한 적이 없으며
          , dfs(
            graph
            , start: neighbor
            , target: target
            , visited: &visited
            , path: &path
          )
      {
        return true
      }
    }
    
    return false
  }

// 반환하는 경로로 가면 원하는 노드를 만날 수 있음.
func bfs<T: Equatable>(
  _ graph: [T: [T]]
  , start: T
  , target: T) -> [T] {
    
    var queue = QueueStack<T>()
    queue.enqueue(start)
    var visited = Set<T>()
    var parent = [T: T]()
    
    while let current = queue.dequeue() {
      visited.insert(current)
      
      if current == target {
        
        var path = [T]()
        var node = target
        
        while node != start {
          
          path.append(node)
          node = parent[node]!
        }
        
        path.append(start)
        return path.reversed()
      }
      
      for neighbor in graph[current] ?? [] {
        
        if visited.contains(neighbor) == false {
          
          queue.enqueue(neighbor)
          parent[neighbor] = current
        }
      }
    }
    
    return []
  }

func bfs<T: Equatable>(
  _ graph: [T: [T]]
  , start: T) -> [T] {
    
    var visited = Array<T>()
    var needVisited = QueueStack<T>()
    needVisited.enqueue(start)
    
    while let node = needVisited.dequeue() {
      guard visited.contains(node) == false else { continue }
      
      visited.append(node)
      
      for neighbor in graph[node] ?? [] {
        needVisited.enqueue(neighbor)
      }
    }
    
    return visited
  }

let graph: [Int: [Int]] = [
    1 : [8, 5, 2],
    8 : [1, 6, 4, 3],
    5 : [1],
    2 : [1, 9],
    6 : [8, 10, 7],
    4 : [8],
    3 : [8],
    9 : [2],
    10 : [6],
    7 : [6]
]

var visited = [Int]()
var path = [Int]()
dfs(
    graph
    , start: 1
    , target: nil
    , visited: &visited
    , path: &path
  )

print("visited from dfs is", visited) // [1,2,4,3]
print("path from dfs is", path) // [1,2,4,3]

visited.removeAll()
path.removeAll()

dfs(
    graph
    , start: 1
    , target: 4
    , visited: &visited
    , path: &path
  )
  
print("visited from dfs is", visited) // [1,2,4]
print("path from dfs is", path) // [1,2,4]

print("traversal all using bfs", bfs(graph, start: 1)) // [1,2,3,4]
print("traversal until meet target using bfs", bfs(graph, start: 1, target: 4)) // [1,3,4]