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

백상휘·2023년 4월 7일

CodingTest

목록 보기

5/6

코딩테스트 하나를 봤다. 4시간이었고 두 문제였다. 하나는 트리로 잘(왜 이 말이 불안하지..) 풀었고, 하나는 음.... 이것저것 끄적거리기는 했지만 결과적으로 못 풀었다.

좌표평면의 사각형을 움직일 수 있을 때까지 움직이는 문제였다. 간단해보이면서 코드로 구현하려니 아주 죽을 맛이었다. 이런 문제 유형을 만나보니 여기서 사용할 수 있는 알고리즘을 배워놓으면 쓸만한 곳이 많겠다는 생각이 들었다.

그래도 예전에는 트리를 사용할 줄도 모르던 내가 트리로 하나 풀어냈다는 것은 만족스러웠다.

그러므로 오늘은 그래프를 한다. 트리는 많이 했으니까.

Overview

그래프는 예전에 말했듯 두 개의 요소로 이루어져 있다.

그래프의 요소

Vertex: 정점. 데이터와 자신의 위치(인덱스) 를 저장한다.
Edge: 간선. 두 정점 사이를 잇기 때문에 양 쪽의 정점을 참조하고 있다. 가중 그래프일 경우엔 간선을 지나는데 필요한 비용인 weight 값도 저장하고 있다.

그래프의 종류

3 개가 있다.

Weighted graphs : 가중 그래프
- 간선을 지나는 데 비용이 드는 그래프를 말한다.
- 비용이 있기 때문에 가장 합리적인 경로를 탐색하는 데 유용하다.
Directed Graph : 유향 그래프.
- 정점 A 에서 정점 B 간 간선으로 연결되어 이동할 경우 A -> B 혹은 A <- B 혹은 A <-> B 세 가지 경우로 이동할 수 있다.
- 간선이 양방향 혹은 단방향일 수 있는 것이다.
Undirected Graph : 비유향 그래프.
- 유향 그래프와 유사하나, 간선이 언제나 양방향인 그래프이다.

그래프 구현

구현체로는 AdjacencyList, AdjacencyMatrix 가 있다.

AdjacencyList: 인접배열. 배열 안에 정점과 간선에 대한 정보를 모두 담는 형태의 그래프이다.
AdjacencyMatrix: 인접배열. 2차원 배열 안에 정점과 간선에 대한 정보를 모두 담는 형태의 그래프이다.
- matrix[row][column] 에서 row 는 간선의 출발점, column 은 도착점이 된다. 반환 값은 가중치 혹은 정점의 데이터가 된다.

참고로 구현체 각각의 시간복잡도는 다음과 같다.

Operations	Adjacency List	Adjacency Matrix
Storage Space (공간 복잡도/확장)	O(V+E)	O(V2)
Add Vertex (정점 삽입)	O(1)	O(V2)
Add Edge (간선 삽입)	O(1)	O(1)
Finding Edges and Weight (간선 혹은 가중치를 검색)	O(V)	O(1)

마지막으로 그래프의 API 는 다음과 같다.

createVertex(data:) : vertex 를 만들고 그래프에 삽입한다.
addDirectedEdge(from:to:weight:) : 단뱡향의 edge 를 두 vertice 사이에 삽입한다.
addUndirectedEdge(between:and:weight:) : 양방향의 edge 를 두 vertice 사이에 삽입한다.
add(from:to:) : edge 의 타입을 이용해 단방향 혹은 양방향의 edge 를 두 vertice 사이에 삽입한다.
edges(from:) : 특정 vertex 에서 출발하는 edge 를 반환한다.
weight(from:to:) : 특정 vertex 에서 가중된 edge 를 반환한다.

그래프 선택 기준

간선의 수를 기준으로 정해볼 수 있다.

만약 간선이 적다면 인접배열로 구현해보자. 간선이 적은 인접행렬은 메모리 소비가 심하다.
만약 간선이 많다면 인접행렬로 구현해보자. 메모리 효율이 좋다.

Implementation

그래프를 구현할 때는 다음의 과정을 거친다.

Vertex 구조체를 선언한다.
- 필요에 따라 Vertex 가 protocol Hashable, protocol Equatable 을 구현하도록 제네릭 선언을 한다. (Hashable 은 Equatable 을 구현하고 있어야 한다)
Edge 구조체를 선언한다.
- Edge 검색 API 를 위해 Edge 는 Equatable 을 구현하도록 한다.
그래프에 공통적으로 필요한 구현 요소들을 protocol Graph 로 선언한다.
- protocol 구현 중 addUndirectedEdge() 와 add() 는 동일한 구현을 가지므로, 미리 extension 해둔다.
인접행렬과 인접배열을 구현한다.

struct Vertex

struct Vertext<T> {
	let index: Int
    let data: T
}

// 필요 시
extension Vertex: Equatable where T: Equatable {}
extension Vertex: Hashable where T: Hashable {}

struct Edge

struct Edge<T> {
	let source: Vertex<T>
    let destination: Vertex<T>
    let weight: Double?
}

extension Edge: Equatable where T: Equatable {}

protocol Graph

protocol Graph {
	associatedtype Element
    
    // 정점 만들기
    func createVertex(data: Element) -> Vertex<Element>
    // 간선(단방향) 만들기
    func addDirectedEdge(
    	from source: Vertex<Element>,
    	to destination: Vertex<Element>
    	weight: Double?)
    // 간선(양방향) 만들기
    func addUndirectedEdge(
    	between source: Vertex<Element>,
		and destination: Vertex<Element>,
		weight: Double?)
    // 정점 사이에 정점 끼워넣기
    func add(
    	_ edge: EdgeType,
        from source: Vertex<Element>,
        to destination: Vertex<Element>,
        weight: Double?)
    // 시작(정)점부터 탐색이 끝나기 까지의 간선들을 모두 반환
    func edges(from source: Vertex<Element>) -> [Edge<Element>]
    // 시작(정)점부터 끝(정)점까지의 가중치(탐색비용)을 반환
    func weights(
    	from source: Vertex<Element>, 
        to destination: Vertex<Element>) -> Double?
}

extension Graph {
	func addUndirectedEdge(
    	between source: Vertex<Element>,
        and destination: Vertex<Element>,
        weight: Double?) {
        
        	addDirectedEdge(from: source, to: destination, weight: weight)
        	addDirectedEdge(from: destination, to: source, weight: weight)
    	}
    
    func add(
    	_ edge: EdgeType,
        from source: Vertex<Element>,
        to destination: Vertex<Element>,
        weight: Double?) {
        
        switch edge {
        case .directed:
        	addDirectedEdge(from: source, to: destination, weight: weight)
        case .undirected:
        	addUndirectedEdge(between: source, and: destination, weight: weight)
        }
    }
}

extension Graph where Element: Hashable {

class AdjacencyList

class AdjacencyList<T: Hashable>: Graph {
	private var adjacencies: [Vertex<T>: [Edge<T>]] = [:]
    init() {}
    
    func createVertex(data: T) -> Vertex<T> {
    	let vertex = Vertex(index: adjacencies.count, data: data)
        adjacencies[vertex] = []
        return vertex
    }
    
    func addDirectedEdge(
    	from source: Vertex<T>,
        to destination: Vertex<T>,
        weight: Double?) {
        
	        let edge = Edge(
    	    	source: source, 
        	    destination: destination, 
            	weight: weight)
	        adjacencies[source]?.append(edge)
        }
    
    func edges(from source: Vertex<T>) -> [Edge<T>] {
    	adjacencies[source] ?? []
    }
    
    func weight(
    	from source: Vertex<T>,
        to destination: Vertex<T>) -> Double? {
        
    	    edges(from: source)
        		.first({ $0.destination == destination})?
            	.weight
        }
}

class AdjacencyMatrix

class AdjacencyMatrix<T: Hashable>: Graph {
	private var vertices: [Vertex<T>] = []
    private var weights: [[Double?]] = []
    
    init() {}
    
    func createVertex(data: T) -> Vertex<T> {
    
    	let vertex = Vertex(index: vertices.count, data: data)
        vertices.append(vertex)
        
        for i in 0..<weights.count {
        	weights[i].append(nil) // Add Column
        }
        
        let row = [Double?](repeating: nil, count: vertices.count)
        weights.append(row)
        
        return vertex
    }
    
    func addDirectedEdge(
    	from source: Vertex<T>,
        to destination: Vertex<T>,
        weight: Double?) {
        
        	weights[source.index][destination.index] = weight
        }
    
    func edges(from source: Vertex<T>) -> [Edge<T>] {
    	var edges: [Edge<T>] = []
        
        for column in 0..<weights.count {
        	
            guard let weight = weights[source.index][column] else {
            	continue
            }
            
            edges.append(
            	Edge(
            		source: source,
                    destination: vertices[column],
                    weight: weight)
            )
        }
        
        return edges
    }
    
    func weight(
    	from source: Vertex<T>,
        to destination: Vertex<T>) -> Double? {
        
       		weights[source.index][destination.index]
        }
}

구현만 한번 쭉 훑어보았다. 하지만 이걸론 부족하다.

요즘 코딩테스트 마스터가 되기 위해 광야를 떠도는 느낌으로 공부를 하면서 느낀 것이 있다.

어떤 주제든 문제 2개는 풀어봐야 익힐 수 있다. 답을 봐도 괜찮고 안보고 풀었다면 칭찬 드림.

그러므로 지금 구현한 인접행렬이나 인접배열을 이용해서 풀 수 있는 문제를 찾아보기로 했다.

전체적으로 느껴진 점은 경로찾기 문제가 아주 적당할 것 같다. 백준에 아주 재미있는 문제를 봤는데, 알고리즘 수업 이라는 카테고리로 분류되어 있는 문제들인 것 같다. 의사코드를 제시해주고 풀이에 따른 성능 차이를 비교하라는 것이다.

문제 : https://www.acmicpc.net/problem/24418

인접행렬에서 Greedy 알고리즘을 통해 가장 큰 값을 반환하는 방법으로 재귀, 동적 프로그래밍 이 있다는 점을 설명해주고 있다. 실제 시간복잡도를 비교하기 위해 다음의 의사코드를 Swift 로 구현해 보고 #코드1, #코드2 라고 명시된 부분이 실행되는 횟수를 반환하는 것이다.

# 행렬 경로 문제 재귀호출 의사 코드는 다음과 같다.
matrix_path(m[][], n) {  # (1, 1)에서 (n, n)에 이르는 최고 점수를 구한다.
	return matrix_path_rec(m, n, n);
}
matrix_path_rec(m[][], i, j) {  # (1, 1)에서 (i, j)에 이르는 최고 점수를 구한다.
	if (i == 0 or j == 0) then
		return 0; # 코드1
	else
		return (mij + (max(matrix_path(m, i-1, j), matrix_path(m, i, j-1))));
}

# 행렬 경로 문제 동적 프로그래밍 의사 코드는 다음과 같다.
matrix_path(m[][], n) {  # (1, 1)에서 (n, n)에 이르는 최고 점수를 구한다.
	for i <- 0 to n
		d[i, 0] <- 0;
	for j <- 1 to n
		d[0, j] <- 0;
	for i <- 1 to n
		for j <- 1 to n
			d[i, j] <- mij + max(d[i - 1, j], d[i, j - 1]);  # 코드2
	return d[n, n];
}

읽는 데 좀 무리가 있었지만 여차저차 구현하기는 했다. 예를 들어 동적 프로그래밍 구현을 보면 인덱스를 0부터 세는 것은 좋은데, #코드2 를 실행하는 부분을 보면 IndexOutOfRange 가 발생한다. 길이가 5인 배열에 인덱스 5를 지정하면 말이다.

여차저차 구현은 했고 답은 틀렸다.... 왜 틀리지???

// 재귀를 이용한 탐색. 의사 코드 이용.
func traversalCountOfRecursionPaths(
    from matrix: [[Int]],
    row: Int,
    column: Int,
    result numberOfCount: inout Int) -> Int { // numberOfCount 는 실제 코드를 실행할 때마다 추가되는 inout 파라미터이다.
        
        guard matrix.reduce(0, { $0 + $1.count }) >= 4 else {
            return matrix.first?.first ?? 0
        }
        
        if row == 0 || column == 0 {
        	numberOfCount += 1
            return 0
        }
        
        let result = matrix[row][column]
        let maxResult = max(
            traversalCountOfRecursionPaths(
                from: matrix, 
                row: row-1, 
                column: column, 
                result: &numberOfCount),
            traversalCountOfRecursionPaths(
                from: matrix, 
                row: row, 
                column: column-1, 
                result: &numberOfCount)
        )
        
        return result + maxResult
    }

// 동적 프로그래밍을 이용한 탐색. 의사 코드 이용.
func traversalCountOfDynamicPaths(
    from matrix: [[Int]],
    row: Int,
    column: Int,
    result numberOfCount: inout Int) -> Int {
        guard matrix.reduce(0, { $0 + $1.count }) >= 4, row >= 2, column >= 2 else {
            return matrix.first?.first ?? 0
        }
        
        var matrix = matrix
        for i in 0..<n {
            numberOfCount += 1
            matrix[i][0] = 0
            
            guard i != 0 else { continue }
            
            numberOfCount += 1
            matrix[0][i] = 0
        }
        
        for i in 1..<n {
            for j in 1..<n {
                numberOfCount += 1
                matrix[i][j] = matrix[i][j] + max(matrix[i-1][j], matrix[i][j-1])
            }
        }
        
        return matrix[n-1][n-1]
    }

이리저리 돌려보고 굴려봤지만 답이 나오질 않는다.

우선 여기까지 정리하고 넘어가야 할 것 같다. 공부할 다른 것들이 많은데 여기서 시간을 계속 잡아먹을 수는 없다. 근데 궁금증이 없는 건 아니다.

동적 프로그래밍 구현에서 왜 첫번째 행과 열을 모두 0으로 만드는가? 의미가 있나?
재귀 구현에서 재귀가 멈추는 조건은 열 혹은 행 번호가 0일 경우이다. 정말 이것이 맞나? 문제는 [0,0] 부터 [n-1,n-1] 까지 이동하면서 수를 더할 때 가장 큰 값이 나온다면 어떤 값인지 물어보는 것인데 [0,3] 등의 상황에서 더 움직일 필요가 없느냐는 것이다.

의사코드 자체를 그냥 코드로 옮긴다는 아이디어 자체가 틀렸을 수도 있다. 머리 좀 식히고 다시 돌아와야겠다.

광야를 떠도는 코딩테스트 마스터(예정) 의 여정은 아직 끝나기엔 멀었다.