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

백상휘·2023년 4월 1일
Swift_Coding_Test코딩테스트_마스터의_길
0

CodingTest

목록 보기
3/6

오늘은 많은 시간을 BinarySearch 에 시간을 좀 썼다.

func binarySearch<T: Comparable>(_ arr: [T], target: T) -> Int? {
    var left = 0
    var right = arr.count - 1
    
    while left <= right {
        let mid = (left + right) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid+1
        } else {
            right = mid-1
        }
    }
    
    return nil
}

func binarySearch<T: Comparable>(arr: [T], target: T) -> Bool {
    guard arr.count > 2 else {
        return arr.contains(where: { $0 == target })
    }
    
    let middle = Int(arr.count / 2)
    if arr[middle] == target {
        return true
    } else if arr[middle] > target {
        return binarySearch(arr: Array(arr[arr.index(after: middle)...]), target: target)
    } else {
        return binarySearch(arr: Array(arr[0..<arr.index(before: middle)]), target: target)
    }
}

BinarySearch 는 배열 안에 target 값을 빨리 찾는 알고리즘이다.

  • target 값이 있을 것으로 기대되는 배열은 오름차순 정렬되어 있어야 한다.
  • 중간 인덱스를 정한 뒤 중간에 위치한 값이 target 이라면 중간 인덱스를 반환한다.
  • 중간 인덱스보다 크다면 중간 인덱스 오른쪽의 배열만 고려하여 다시 BinarySearch 를 실행한다.
    오른쪽 배열만 가지고 다시 중간 인덱스를 검증하기 때문에 시간 복잡도 면에서 유리하다.
  • 반대로 중간 인덱스보다 작다면 왼쪽 배열만으로 BinarySearch 를 진행한다.

위에 것은 AI 가 짜준 코드에 제네릭 선언을 추가한 것이고, 아래는 내가 직접 구현한 것이다.

내가 짠 코드는 Array 를 새로 만들어줘야 한다. 메모리를 낭비가 있을 것 같다.

이걸 파본 이유는 다음의 문제를 풀고 싶었기 때문이다.

백준 1920 문제

https://www.acmicpc.net/problem/1920

BinarySearch 가 그렇게 어렵지는 않은 알고리즘은데 정답률이 30% 정도여서 의아했다. 아마 나처럼 구글링이나 AI 의 도움을 받지 않고 풀었기 때문이 아닐까 싶다.

let _ = readLine()!
let a = readLine()!
    .split(separator: " ")
    .compactMap({Int($0)})
    .sorted(by: <)
let _ = readLine()!
var targets = readLine()!
    .split(separator: " ")
    .compactMap({Int($0)})

func binarySearch<T: Comparable>(_ arr: [T], target: T) -> Int? {
    var left = 0
    var right = arr.count - 1
    
    while left <= right {
        let mid = (left + right) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid+1
        } else {
            right = mid-1
        }
    }
    
    return nil
}

for target in targets {
    let result = binarySearch(a, target: target) != nil
    print(result ? 1 : 0)
}

결론: AI 승리!

내가 짠 BinarySearch 는 시간초과가 발생했다.

Array 의 일부를 잘라서 다시 생성하는 나의 알고리즘이 시간초과를 발생시킨 것이지 이진 탐색을 사용하는 것에는 이상이 없었던 것 같다.

이제는 어제 공부한 BFS/DFS 를 다시 파보자.

BFS, DFS 를 하루에 끝내지 못한 이유

다시 생각해보면 그래프는 간단히 넘어간다 라는 말 자체가 잘못된 것 같다. 자료구조를 간단히 넘어가면 안되는 것 같다.

그러므로 오늘은 3가지를 한다.

  1. 인접행렬, 인접그래프 구현을 학습한다.
  2. DFS/BFS 에 적용한다.
  3. 다시 푼다.

원래는 면접 준비, 포트폴리오 강화도 같이 하지만 면접 준비를 뺐다. 면접 준비야 우선 코딩테스트를 붙고 준비해야 하지 않겠는가?

뭐 하나 쉬운 것이 없다.

Kodeco 의 자료구조&알고리즘 책에서 알고리즘 구현을 보았다. 이해는 되는데 뭔가 어렵다........ 난이도도 있지만 코딩테스트 시간 안에 구현을 하고 문제풀이까지 갈 수 있을지 의문이다.

한번 Chat-GPT 와 공부해보자.

Graph, BFS, DFS by Chat-GPT

내가 한 질문은 다음과 같았고, 아래와 같은 답을 주었다. 그대로 복사 붙여넣기를 하였다.

  1. Can you implement breadthFirstSearch algorithm using graph data structure?
    (답) python 으로 bfs 를 구현해주기 시작했다.
  2. Can you implement breadthFirstSearch algorithm using graph data structure using swift language?
    (답) Graph 클래스에 정점을 Dictionary 로 관리하고, addVertex/addEdge 를 구현했으며, bfs 를 구현해주었다. 하지만 다음 방문 예정인 정점을 Array 로 만들면 공간복잡도에 문제가 있을 것으로 예상하고 Queue 로 바꿔달라고 했다(Array 를 Queue 처럼 사용하면 removeFirst() 로 저장된 요소를 빼오는데, O(n) 시간복잡도를 갖는다.)
  3. I think swift dictionary search an element in O(n). Is it right? (번외 질문)
    (답) 딕셔너리는 Hashable 을 키로 갖기 때문에 O(1) 을 평균으로 갖는다고 한다. NSDictionary 로 Wrap 된 경우는 O(n) 이라고 하는데 여기선 해당하지 않는다.
  4. You implement swift bfs and using dictionary. How about using Queue? (2번에 이은 질문)
    (답) Queue 구현을 추가하고 2번의 답과 연결시켜서 bfs 를 구현해주었다.
  5. Your graph Vertex must be hashable?
    (답) 그렇다고 한다. Vertex 구현도 해주었다. Hashable 이 안되는 경우는 어쩌나 잠시 고민해보았다. 우선은 그래프로 다시 돌아가기!
  6. Thanks. I also want to implement depthFirstSearch algorithm. Can you implement this one also?
    (답) 말 그대로 dfs 를 구현해주었다. 그래프는 비슷한 구조를 가지고 있었다.

쓸 때마다 느끼는 건데 예전 방식처럼 무조건 구현을 외우고 그대로 적용하는 방식이 이제 무슨 소용인가 생각해본다. 정말 무섭기까지 하다.

소스코드는 약간 수정을 했다. 한꺼번에 표시하는게 좋겠다 싶어서 구조 등을 조금씩 변경한 것이다. 물론 정말 이 구현이 옳은 것인지 검증도 필요했다.

class Graph<T> where T: Hashable {
    var vertices: [Vertex<T>: Set<Vertex<T>>] = [:]
    
    func addVertex(_ vertex: Vertex<T>) {
        if vertices[vertex] == nil {
            vertices[vertex] = []
        }
    }
    
    func addEdge(from start: Vertex<T>, to end: Vertex<T>) {
        addVertex(start)
        addVertex(end)
        vertices[start]?.insert(end)
        vertices[end]?.insert(start)
    }
}

extension Graph { // bfs
    func bfs(start: Vertex<T>) -> [Vertex<T>] {
        var visited = Set<Vertex<T>>(); visited.insert(start)
        let queue = Queue<T>(); queue.enqueue(start)
        var result: [Vertex<T>] = []
        
        while let current = queue.dequeue() {
            result.append(current)
            
            guard let neighbors = vertices[current] else { continue }
            
            for neighbor in neighbors {
                if !visited.contains(neighbor) {
                    visited.insert(neighbor)
                    queue.enqueue(neighbor)
                }
            }
        }
        
        return result
    }
}

extension Graph { // dfs
    func dfs(start: Vertex<T>) -> [Vertex<T>] {
        var visited: Set<Vertex<T>> = []
        var result: [Vertex<T>] = []
        
        dfsHelper(start: start,
                  visited: &visited,
                  result: &result)
        
        return result
    }
    
    private func dfsHelper(
        start: Vertex<T>,
        visited: inout Set<Vertex<T>>,
        result: inout [Vertex<T>]
    ) {
        visited.insert(start)
        result.append(start)
        
        guard let neighbors = vertices[start] else { return }
        
        for neighbor in neighbors {
            if !visited.contains(neighbor) {
                dfsHelper(start: neighbor, visited: &visited, result: &result)
            }
        }
    }
}

class Vertex<T>: Hashable where T: Hashable {
    let value: T
    var hashValue: Int {
        return value.hashValue
    }
    
    init(_ value: T) {
        self.value = value
    }
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(value)
    }
    
    
    static func == (lhs: Vertex, rhs: Vertex) -> Bool {
        return lhs.value == rhs.value
    }
}

class Queue<T> where T: Hashable {
    private var elements: [Vertex<T>] = []
    
    func enqueue(_ element: Vertex<T>) {
        elements.append(element)
    }
    
    func dequeue() -> Vertex<T>? {
        guard !elements.isEmpty else {
            return nil
        }
        return elements.removeFirst()
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
}

몇 가지 논란이 있을 법 하다고 생각되는 부분만 추가로 언급하고 정리는 여기까지 해야겠다.

  1. Queue 는 Class 로 선언하였다. elements 가 자주 바뀔 예정이므로 조금의 복잡도도 허용하고 싶지 않았다.
  2. Graph 는 Hashable 한 데이터를 저장하는 정점들을 포함하고 있다. 이 점은 주의해야 할 수도 있겠지만 대부분의 상황에서 큰 문제가 된다고 생각하지는 않았다. 좀 더 고민해보고 문제가 발생할 수도 있겠다 싶으면 추가로 수정해야 겠다.
  3. Edge 를 직접 구현하는 경우도 있지만 여기는 없다.
    대신 Graph 안에 있는 딕셔너리가 특정 Vertex 에 대해 연결된 다른 Vertex 들을 저장하는 Set 을 반환하기 때문에 그 역할을 대신한다.

트리도 공부해야 하는데.... 우선 여기까지!!!!

출처

백준 1920 : https://www.acmicpc.net/problem/1920
그래프 이론 : https://letzgorats.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-1-%EC%BD%94%EB%94%A9-%ED%85%8C%EC%8A%A4%ED%8A%B8%EC%97%90%EC%84%9C-%EC%9E%90%EC%A3%BC-%EB%93%B1%EC%9E%A5%ED%95%98%EB%8A%94-%EA%B8%B0%ED%83%80-%EA%B7%B8%EB%9E%98%ED%94%84-%EC%9D%B4%EB%A1%A0
도서 : Kodeco - [Data Structures & Algorithms in Swift]
빠르게 대답해주는 AI : https://chat.openai.com/chat
기본 Swift 자료구조의 시간복잡도 : https://demian-develop.tistory.com/30

profile
백상휘
plug-compatible programming unit
이전 포스트

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

다음 포스트

코딩테스트 마스터의 길 - (4)

0개의 댓글