[Swift 알고리즘] 탐색 알고리즘

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

 

 

1. 깊이 우선 탐색(DFS: Depth-First-Search)

그래프 완전 탐색

재귀함수로 구현

스택 자료구조 이용

• 깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나
• 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여
  • 최대 깊이까지 탐색을 마친 후
    • 다른 쪽 분기로 이동하여 다시 탐색 수행
      • ⇒ 자식 노드부터 탐색
• 재귀 함수로 구현, 스택 자료구조를 이용
• 처음 탐색 노드의 어떤 인접 노드부터 탐색할지에 대한 순서는 상관없음

 

[깊이 우선 탐색의 원리]

• 한 번 방문한 노드를 다시 방문하면 안 된다.
  • 노드 방문 여부를 체크할 배열이 필요하다.
• 그래프를 인접 리스트로 표현
• DFS는 후입 선출의 특성을 가짐 → 스택 or 스택 성질을 갖는 재귀 함수로 구현

• DFS를 인접 리스트 그래프로 표현하고
  • 노드 방문 여부를 체크할 배열인 방문 배열을 초기화한다
    • 시작 노드를 정해서 시작 노드를 스택에 삽입한다.

• 스택에서 가장 마지막에 있는 노드(1)를 먼저 꺼내서 탐색 순서를 기록한다.
  • 꺼냈던 노드(1)의 인접 노드(2, 5)를 다시 스택에 삽입한다.
    • 이때 방문 배열에 기록되었는지를 확인하고 삽입한 후, 방문배열에 기록한다.

• 스택에서 가장 마지막에 있는 노드(5)를 먼저 꺼내서 탐색 순서를 기록한다.
  • 꺼냈던 노드(5)의 인접 노드(4)를 다시 스택에 삽입한다.
    • 이때 방문배열에 기록되었는지를 확인하고 삽입한 후, 방문배열에 기록한다.

• 스택에서 가장 마지막에 있는 노드(4)를 먼저 꺼내서 탐색 순서를 기록한다.
  • 꺼냈던 노드(4)는 인접 노드가 없기 때문에 스택에 삽입하지 않는다.
    • 스택에서 가장 마지막에 있는 노드(2)를 꺼내서 탐색 순서를 기록한다.
      • 꺼냈던 노드(2)의 인접 노드(3)를 다시 스택에 삽입한다.
        • 꺼낸 노드(2)의 인접 노드는 (3, 4)노드 2개가 있지만 (4)는 이미 방문한 상태이기 때문에 삽입하지 않는다.

• 스택에서 가장 마지막에 있는 노드(3)를 먼저 꺼내서 탐색 순서를 기록한다.
  • 꺼냈던 노드(3)는 인접 노드가 없기 때문에 스택에 삽입하지 않는다.
    • 스택이 빌 때까지 진행한다.

[DFS 구현(인접 리스트)]

//인접 리스트 구현 - 무방향 
var graph: [Int: [Int]] = [:]

for i in 0..<N{
    //input ex. 5 1
    let edge = readLine()!.split(separator: " ").map{Int(String($0))!}
    graph[edge[0], default: []].append(edge[1])
    graph[edge[1], default: []].append(edge[0])
}

func DFS(graph: [String: [String]], start: String) -> [String] {
    var visitedQueue: [String] = []
    var needVisitStack: [String] = [start]
    
    while !needVisitStack.isEmpty {
        let node: String = needVisitStack.removeLast()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
       needVisitStack += graph[node] ?? []
    }
    return visitedQueue
}

코드 출처 https://babbab2.tistory.com/107?category=908012

[DFS 구현(인접 리스트)-재귀]

var graph = Array(repeating: [Int](), count: N + 1)
var visited = Array(repeating: false, count: N + 1)

for _ in 0..<M {
    let edge = readLine()!.split(separator: " ").map { Int(String($0))! }
    graph[edge[0]].append(edge[1]) 
    graph[edge[1]].append(edge[0]) 
}

// 재귀함수로 dfs 구현
func dfs(_ node: Int) {
    visited[node] = true //현재 node 방문 
    
    //  처음 탐색 노드의 어떤 인접 노드부터 탐색할지에 대한 순서는 상관 없음
    for i in graph[node] {
        if !visited[i] { //아직 방문하지 않았다면
            dfs(i)     //dfs 실행
        }
    }
}

코드 참고 https://velog.io/@comdongsam/swift로-DFS-구현하기

 

2. 너비 우선 탐색(BFS: Breadth-First-Search)

그래프 완전 탐색

선입선출(FIFO) 탐색

큐 자료구조 이용

• 너비 우선 탐색은 그래프 완전 탐색 기법 중 하나
• 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하며 탐색하는 알고리즘
• 선입선출 방식으로 탐색하므로 큐 자료구조를 이용
• 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로
  • 목표 노드에 도착하는 경로가 여러 개일 때
    • 최단 경로 보장

 

[너비 우선 탐색의 원리]

• 한 번 방문한 노드를 다시 방문하면 안 된다.
  • 노드 방문 여부를 체크할 배열이 필요하다.
• 그래프를 인접 리스트로 표현
• BFS는 선입선출의 특성을 가짐 → 큐 자료구조를 사용

• BFS를 인접 리스트 그래프로 표현하고
  • 노드 방문 여부를 체크할 배열인 방문 배열을 초기화한다
    • 시작 노드를 정해서 시작 노드를 큐에 삽입한다.

• 큐에서 가장 앞에 있는 노드(1)를 먼저 꺼내서 탐색 순서를 기록한다.
  • 꺼냈던 노드(1)의 인접 노드(2, 5)를 다시 큐에 삽입한다.
    • 이때 방문 배열에 기록되었는지를 확인하고 삽입한 후, 방문배열에 기록한다.

• 큐에서 가장 앞에 있는 노드(2)를 먼저 꺼내서 탐색 순서를 기록한다.
  • 꺼냈던 노드(2)의 인접 노드(3, 4)를 다시 큐에 삽입한다.
    • 방문 배열을 확인하고 삽입한 후, 방문 배열에 기록한다.

• 큐에서 가장 앞에 있는 노드(5)를 먼저 꺼내서 탐색 순서를 기록한다.
  • 꺼냈던 노드(5)는 인접 노드(4)는 이미 방문한 노드이기 때문에 큐에 삽입하지 않는다.

• 큐에서 가장 앞에 있는 노드(3)를 먼저 꺼내서 탐색 순서를 기록한다.
  • 꺼냈던 노드(3)는 인접 노드가 없기 때문에 스택에 삽입하지 않는다.

• 큐에서 가장 앞에 있는 노드(4)를 를 먼저 꺼내서 탐색 순서를 기록한다.
  • 꺼냈던 노드(4)는 인접 노드가 없기 때문에 스택에 삽입하지 않는다.

 

[DFS 구현(인접 리스트)]

func BFS(graph: [String: [String]], start: String) -> [String] {
    var visitedQueue: [String] = []
    var needVisitQueue: [String] = [start]
    
    while !needVisitQueue.isEmpty {
        let node: String = needVisitQueue.removeFirst()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
        needVisitQueue += graph[node] ?? []
    }
    return visitedQueue
}

[DFS 구현(자료구조 큐)] - 시간 복잡도 개선

var graph = Array(repeating: [Int](), count: N + 1)
var visited = Array(repeating: false, count: N + 1)

for _ in 0..<M {
    let edge = readLine()!.split(separator: " ").map { Int(String($0))! }
    graph[edge[0]].append(edge[1]) 
    graph[edge[1]].append(edge[0]) 
}

func BFS(node: Int) -> [Int]{
    var check = Array(repeating: false, count: input[0] + 1)
    var order = Array(repeating: 0, count: input[0] + 1)
    var queue = Queue<Int>()

    queue.enqueue(node)
		check[node] = true
    
    while !queue.isEmpty {
        let node = queue.dequeue()
        for nextNode in graph[node]{
            if !check[nextNode]{
                check[nextNode] = true
                queue.enqueue(nextNode)
            }
        }
    }
    return order
}

public struct Queue<T> {
    var nodes = [T]()
    var idx = 0
    
    var isEmpty: Bool {
        return !(nodes.count > idx)
    }
    
    mutating func enqueue(_ element: T) {
        nodes.append(element)
    }
    
    mutating func dequeue() -> T {
        defer {
            idx += 1
        }
        return nodes[idx]
    }
}
// dequeue에서 removeFirst()대신 idx만 증가시키면 
// ~ 데이터는 삭제하지만 공간은 그대로이기 때문에 앞으로 당기는 작업이 필요 없다.
// dequeue에서 시간 복잡도는 O(1)

 

3. 이진 탐색(Binary Search)

• 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘
• 데이터가 정렬돼 있는 상태에서
  • 대상 데이터의 중앙값과 찾고자 하는 값을 비교해
    • 데이터의 크기를 절반씩 줄이면서 대상을 찾는 방법
• 시간 복잡도: O(logN)
  • 이진 탐색에서 N개의 데이터에서 log(N) 번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.
    • 16개의 데이터에서는 최대 4번의 연산으로 원하는 데이터의 위치를 찾을 수 있다.

 

[이진 탐색의 원리]

[이진 탐색 코드 - 반복문]

func binarySearch(arr: [Int], l: Int, r: Int,  target: Int) -> Bool{
    var left = l
    var right = r

    while left <= right{
        let midIndex: Int = (left + right) / 2
        if arr[midIndex] > target {
            right = midIndex - 1
        }else if arr[midIndex] < target{
            left = midIndex + 1
        }else{
            return true
        }
    }
	return false
}

[이진 탐색 코드 - 재귀]

func binarySearch(arr: [Int], left: Int, right: Int,  target: Int) -> Bool{
    var result = false
    let midIndex: Int = (left + right) / 2

    if left > right {
        return false
    }

    if arr[midIndex] > target {
        result = binarySearch(arr: arr, l: left, r: midIndex - 1, target: target)
    }
    else if arr[midIndex] < target {
        result = binarySearch(arr: arr, l: midIndex + 1, r: right, target: target)
    }else{
        return true
    }

	return result
}

 

4. 백트래킹

• 기본적으로 완전 탐색 알고리즘이며 DFS나 BFS와 같은 방식으로 진행되지만,
  • 진행 과정에서 답이 아닌 분기를 만나면 탐색을 진행하지 않고 돌아가 다른 분기로 감으로써 가지치기를 한다는 차이가 있다.

 

 

 

 

 

참고하였습니다. 감사합니다.

http://www.yes24.com/Product/Goods/108571508

Do it! 알고리즘 코딩 테스트 자바 편 - YES24

 

•  

•