Velog의 주간 트랜드 글을 구경하다 Eddy 님의 인풋 말고 아웃풋 글을 읽고 그동안의 막막함이 한 번에 해소되는 기분을 느꼈다.

그 글 그대로, 나는 계속 인풋을 카운트하며 공부하고 있었다. Swift 문법책을 읽고, 읽고... UIKit 책도 앱을 만들 수도 없는 상황에서 읽고, SwiftUI 책도 제대로 따라갈 수 없는 환경에서 읽고... 이미 이해했다는 핑계로 코드도 직접 따라 치지 않고 책을 읽기만 하면서, 오만하게 공부하고 있다고 생각했다.

읽고 정리조차 제대로 하지 않았더니, 다시 그 책을 봤을 때는 정말 처음 보는 듯한 문장이 곳곳에서 튀어나왔다. 읽고 이해한 순간에는 내 것이 되었다 느꼈는데 말이다. 아무리 스키 타는 법에 관해 공부해서 가도 정작 스키를 타면 넘어질 수밖에 없는 것처럼, 아웃풋이 없다면 결코 내 것이 될 수 없다.

많이 읽을수록 멍청해지는 경험

브런치의 과도한 인풋은 인풋이 아니었음을 글도 많은 도움이 되었다. 많이 읽을수록 멍청해진다, 인풋을 지나치게 따라다니는 건 즐거움과 창의성을 상실하게 만든다. 는 이야기를 적어주셨다.

맞다. 사실 인풋을 하는 데는 그렇게 큰 노력이 필요하지 않다. 그냥 가만히 있으면 정보가 알아서 들어온다. 무언가 창작하지 않으니 생각할 필요가 없으니까 편하고, 편하니까 인풋에 중독되고 만다. 머릿속에서는 잠깐의 관심사에 머물고, 스스로 새로운 결과를 만들어 낼 시간마저 뺏긴다.

물론 지속적이고 꾸준한 인풋도 중요하겠지만, 거기에 매몰되어서는 안 된다. 사실 이 블로그를 시작하게 된 이유이기도 하다.

결론

인풋에 매달리던 방식을 바꾸자. 아웃풋을 먼저 목표로 세운다. 그러면 이를 위해 자연스럽게 인풋이 딸려 오는 것이다. 예를 들어 내가 class와 struct, 그리고 enum 간의 차이점에 대한 글을 쓸 것이다! 하면, 설명글을 쓰기 위해 아주 깊고 상세하게 공부할 수밖에 없다. 그렇게 좋은 아웃풋까지 만들어 낸다면, 정말 의미 있는 내 것이 된 인풋도 어느덧 쌓여 있으리라 믿는다.

앞 글과 같은 이야기를 조금 반복하자면,

BFS(너비 우선 탐색)과 DFS(깊이 우선 탐색)는 트리의 노드를 스캔하는 대표적인 방법이다. 각 방식은 큐와 스택을 이용해 구현하게 되는데, Swift에서 스택은 배열로 구현하면 되지만 큐를 구현하는 것이 문제다. C++처럼 STL로 기본 자료구조들을 제공하고 있지 않기 때문이다... 😢

배열의 메소드 removeFirst()를 쓰면 되지 않느냐 할 수 있지만.. removeFirst()의 시간 복잡도는 무려 O(n)이다! 큐에 쌓여가는 값에 비례해 느려지기 때문에, 코딩테스트에서 일반적으로 사용하기에는 좋지 않다. 그렇다고 큐를 매번 직접 구현해서 쓰기도 힘들다.

그래서 우리는 편법이 필요하다. 큐를 사용하지 않고 값을 넣고 빼는 과정의 시간 복잡도를 최대한 줄이면서도 배열만으로 큐와 같은 효과를 내야 한다. 그렇게 며칠간 고민하고 BFS를 풀며 정리한 편법들을 소개한다. 😏

🗝️ Swift로 BFS를 구현해보자.

총 세 가지 방법을 실제 문제를 풀어보며 살펴보자. 이번에 풀어볼 문제는 백준의 2178 미로탐색 이다.

앞서 BFS를 설명하며 살펴본 문제와 동일한 것으로 N x M 크기의 길(1)과 벽(0)으로 이루어진 미로에서 탈출하는 최단 거리를 구하는 것이 목표이다. 항상 탈출구까지 도착할 수 있는 경우만 입력으로 주어지기 때문에, 탈출 불가 상황은 신경 쓰지 않아도 된다.

방법 1. 배열과 Pointer

큐의 선입 선출 방식대로 배열의 요소를, pointer를 이용해 읽어 들이는 방법이다. 기존 BFS와 달리 값을 계속 배열에 쌓아두는 대신 pointer 값만 바꾸어 현재 탐색 노드를 바꿔가면 된다. 바로 풀이를 보자.

// 문제에서 주어진 미로의 크기 입력 받기.
let NM = readLine()!.split{$0 == " "}.map{Int(String($0))!}
let (N, M) = (NM[0], NM[1])

// 문제에서 주어진 미로 입력 받기.
var map = Array(repeating: [0], count: N)
for i in 0..<N {
    map[i] = Array(readLine()!).map{Int(String($0))!}
}

// 문제에서 길은 1, 벽은 0, 탈출구는 N-1, M-1
let wall = 0
let road = 1

// 상하좌우 인접한 칸 탐색을 수월하게 하기위한 상수.
let dr = [1, -1, 0, 0], dc = [0, 0, 1, -1]

// 실제 큐는 아니지만, 의미를 살리기 위해 queue라고 이름지었다.
var queue: [(Int, Int)] = [(0, 0)]
// 배열 queue를 실제 큐처럼 작동하게 만들어줄 pointer 변수.
var pointer = 0

// BFS
// pointer가 queue.count와 같아진다면,
// 원래 BFS에서 큐가 비어 BFS가 끝나는 것과 의미가 동일하다.
while pointer < queue.count {

    // 현재 대상 노드. 이 노드의 주변을 탐색할 것이다.
    let cur = queue[pointer]

    // 앞서 정의한 배열을 통해 간단하게 상하좌우를 탐색한다.
    for i in 0..<4 {

        // 탐색할 노드의 좌표
        let nr = cur.0+dr[i]
        let nc = cur.1+dc[i]

        // 인덱스 범위를 벗어난 값 처리
        if nr>N-1 || nr<0 || nc>M-1 || nc<0 {
            continue
        }

        // map의 값중 road인 것은, 방문한 적이 없으며 벽도 아니라는 것이다.
        // 따라서 이동 가능한 길!
        if map[nr][nc] == road {

            // 방문 표시를 현재 대상 노드 칸의 값 + 1을 해주면
            // 자연스럽게 루트로부터의 거리가 된다.
            map[nr][nc] = map[cur.0][cur.1] + 1

            // 새롭게 방문 가능한 칸이었으므로
            // 다음엔 이 칸의 주변을 탐색할 것이므로 큐에 추가한다.
            queue.append((nr, nc))
        }
    }

    // 현재 대상 노드의 주변 탐색이 모두 끝났으므로 pointer 값을 하나 올려 준다.
    // 이는 큐를 이용한 BFS에서 팝을 해주어 다음 대상 노드로 넘어가는 과정과 같다.
    pointer += 1
}

// 탈출 칸의 값은 방문 표시와 겸한 루트로부터의 거리로 채워져 있을 것이므로,
// 탈출 칸의 값을 출력하면 최단거리를 알 수 있다.
print(map[N-1][M-1])

참고로, 이 문제는 시작점의 값이 이미 1이기 때문에 방문 표시를 따로 하기가 애매해서 하지 않았다. 그러나 일반적으로 BFS를 사용할 때 시작점에 방문 표시를 하는 걸 까먹으면 큰일난다!

이전 글의 이미지와 큐의 작동 방식을 떠올리며 위 풀이가 배열과 pointer 를 이용해 어떤 식으로 큐를 대체했는지 살펴보자.

위 풀의 배열에는 (시계방향으로 위부터 탐색한다는 가정하에) 이 같은 순서로 값이 채워져 간다.

queue = [(0, 0)]

1번째 루프
pointer = 0, cur = (0, 0)
queue = [(0, 0), (1, 0)]

2번째 루프
pointer = 1, cur = (1, 0)
queue = [(0, 0), (1, 0), (1, 1), (2, 0)]

3번째 루프
pointer = 2, cur = (1, 1)
queue = [(0, 0), (1, 0), (1, 1), (2, 0), (1, 2)]

4번째 루프
pointer = 3, cur = (2, 0)
queue = [(0, 0), (1, 0), (1, 1), (2, 0), (1, 2), (3, 0)]

...

큐는 없지만 새로운 탐색 노드는 뒤에 쌓이고, 현재 대상 노드(cur)은 앞에서부터 하나씩 진행하는 것을 확인할 수 있다. 이처럼 큐 없이 구현할 수 있다!

장단점

장점: 시간 복잡도가 O(N)인 removeFirst()를 사용하지 않고 현재 대상 노드를 배열에서 인덱스로 바로 접근해 꺼내오므로 큐를 이용한 BFS와 같이 시간복잡도를 O(1)로 확보할 수 있다. 구현이 간단하다.

단점: BFS는 동일한 레벨의 노드를 모두 탐색하고, 다음 레벨의 노드로 넘어가는데, 이 계층 탐색의 구조를 잃는다. 정확히 몇 번째 레벨을 탐색하고 있는지 알 수 없다. (근데 이건 큐를 이용해서 구현한 원래 BFS에서도 같다.)

방법 2. 배열과 2개의 Pointer

이번엔 두 개의 pointer를 이용해 BFS의 계층별로 탐색하는 구조를 살린 풀이다.

let NM = readLine()!.split{$0 == " "}.map{Int(String($0))!}
let (N, M) = (NM[0], NM[1])

var map = Array(repeating: [0], count: N)
for i in 0..<N {
    map[i] = Array(readLine()!).map{Int(String($0))!}
}

let wall = 0
let road = 1

let dr = [1, -1, 0, 0], dc = [0, 0, 1, -1]

var queue: [(Int, Int)] = [(0, 0)]

// 배열 queue를 실제 큐처럼 작동하게 만들어줄 pointer 변수
// 이번에 탐색해야 할 계층에 해당하는 queue 내의 칸의 범위를 표현한다.
var startPointer = 0, endPointer = queue.count

// BFS
// 큐에 새로 추가된 칸이 없으면, 두 포인터의 값이 같아지므로 종료하게 된다.
Outer: while startPointer < endPointer {

    // 한 계층씩 탐색한다.
    searchLevel(startPointer, endPointer)

    // 큐 내의 이번 계층에 해당하는 칸의 탐색을 마쳤으므로, 다음 계층으로 넘어간다.
    // startPointer는 다음 계층의 첫번째 탐색 노드를, endPointer는 다음 계층의 마지막 탐색점 노드를 가리킨다.
    // (정확히는 마지막 탐색 노드의 인덱스 + 1)
    startPointer = endPointer
    endPointer = queue.count
}

func searchLevel(_ startPointer: Int, _ endPointer: Int) {
    for pointer in startPointer..<endPointer {
        let cur = queue[pointer]

        for i in 0..<4 {
            let nr = cur.0+dr[i]
            let nc = cur.1+dc[i]

            if nr>N-1 || nr<0 || nc>M-1 || nc<0 {
                continue
                }

            if map[nr][nc] == road {
                map[nr][nc] = map[cur.0][cur.1] + 1
                queue.append((nr, nc))
            }
        }
    }
}

print(map[N-1][M-1])

역시 이전 글의 이미지와 큐의 작동 방식을 떠올리며 위 풀이가 배열과 2개의 pointer를 이용해 어떤 식으로 큐를 대체했는지 살펴보자.

queue = [(0, 0)]

1번째 Outer 루프 (루트로부터 거리가 1인 노드 탐색)
startPointer = 0, endPointer = 1
queue = [(0, 0), (1, 0)]

2번째 Outer 루프 (루트로부터 거리가 2인 노드 탐색)
startPointer = 1, endPointer = 2
queue = [(0, 0), (1, 0), (1, 1), (2, 0)]

3번째 Outer 루프 (루트로부터 거리가 3인 노드 탐색)
startPointer = 2, endPointer = 4
queue = [(0, 0), (1, 0), (1, 1), (2, 0), (1, 2), (3, 0)]

4번째 Outer 루프 (루트로부터 거리가 4인 노드 탐색)
startPointer = 4, endPointer = 6
queue = [(0, 0), (1, 0), (1, 1), (2, 0), (1, 2), (3, 0),
         (0, 2), (3, 1)]

...

각 Outer 루프 한번마다 거리가 같은 모든 노드를 탐색하는 것을 알 수 있다.

장단점

장점: 앞의 방법과 동일하게 O(1)의 시간 복잡도로 큐와 같이 동작하도록 구현하였다. 계층마다 탐색하고 구분 짓는 것이 중요한 문제라면 이 방법을 통해 풀 수 있다. 한 계층씩 탐색해야 하는 문제는 추후 BFS 응용문제 글에서 다뤄 보겠다!

단점: 음...구현이 복잡한 느낌이다? 시작점이 두 종류인 BFS 문제를 풀 때 주로 한 계층씩 탐색하는 방식으로 구현하게 되는데, 이 방법으로는 구현하는 게 좀 복잡해질 수 있다.

방법 3. 배열을 이용한 계층탐색

queue로 정의한 배열 자체를 계층이 바뀔 때마다 갈아 끼우며 계층 탐색을 할 수 있도록 구현한 것이다. 역시 코드를 보며 생각해 보자.

let NM = readLine()!.split{$0 == " "}.map{Int(String($0))!}
let (N, M) = (NM[0], NM[1])

var map = Array(repeating: [0], count: N)
for i in 0..<N {
    map[i] = Array(readLine()!).map{Int(String($0))!}
}

let wall = 0
let road = 1

let dr = [1, -1, 0, 0], dc = [0, 0, 1, -1]

var queue: [(Int, Int)] = [(0, 0)]
var escaped = false

// BFS
while !escaped {
    bfs()

    if queue.isEmpty {
        escaped = true
    }
}

func bfs() {
    var nextQueue: [(Int, Int)] = []

    for cur in queue {
        for i in 0..<4 {
            let nr = cur.0+dr[i]
            let nc = cur.1+dc[i]

            if nr>N-1 || nr<0 || nc>M-1 || nc<0 {
                continue
                }

            if map[nr][nc] == road {
                map[nr][nc] = map[cur.0][cur.1] + 1
                nextQueue.append((nr, nc))
            }
        }
    }
    queue = nextQueue
}

print(map[N-1][M-1])

역시 이전 글의 이미지와 큐의 작동 방식을 떠올리며 위 풀이가 어떤 식으로 작동하는지 살펴보자.

queue = [(0, 0)]

1번째 루프 (루트로부터 거리가 1인 노드 탐색)
현재까지 탐색한 칸 = [(0, 0), (1, 0)]
queue = [(1, 0)]

2번째 루프 (루트로부터 거리가 2인 노드 탐색)
현재까지 탐색한 칸 = [(0, 0), (1, 0), (1, 1), (2, 0)]
queue = [(1, 1), (2, 0)]

3번째 루프 (루트로부터 거리가 3인 노드 탐색)
현재까지 탐색한 칸 = [(0, 0), (1, 0), (1, 1), (2, 0),
                   (1, 2), 3, 0)]
queue = [(1, 2), (3, 0)]

4번째 루프 (루트로부터 거리가 4인 노드 탐색)
현재까지 탐색한 칸 = [(0, 0), (1, 0), (1, 1), (2, 0),
                   (1, 2), (3, 0),(0, 2), (3, 1)]
queue = [(0, 2), (3, 1)]

...

장단점

장점: 역시 동일하게 O(1)의 시간 복잡도로 큐와 같이 동작하도록 구현하였다. 계층마다 탐색하고 구분 짓는 것이 중요한 문제라면 이 방법을 통해 풀 수 있다. 특히, 이 방법은 두 종류의 시작점이 있는 문제에서 각각의 BFS를 구현하기 쉽기 때문에 깔끔하게 풀 수 있다. 추후 BFS 응용문제 글에서 다뤄 보겠다!

단점: -

결론

처음에 BFS 개념을 배우고, 막상 풀어보려 하니 Swift에서는 기본적으로 큐를 제공하지 않아 이러면 도대체 어떻게 해야하는지.. 하는 막막함이 있었다. 그냥 removeFirst()를 쓰는 글도 많았지만, 시간복잡도 면에서 큰 손해이기 때문에 실제로 N이 큰 경우 시간 초과가 나기도 하였다.

그렇게 한동안 고민해 보고 다른 사람의 풀이도 보며 생각해 본 결과, 위 세 가지 방법이 Swift에서 BFS 문제를 푸는 데 그나마 최적의 방법이라고 결론 내렸다. 특히, 마지막 방법은 시작점이 두 종류인 복잡한 BFS 문제를 풀 때 구현이 편해 탁월한 성능을 발휘한다. 다음 글로 BFS의 응용문제 풀이를 작성할 예정이다.

BFS는 자주 나오는 유형인 만큼, 개념을 바탕으로 이러한 틀 자체를 익혀두고 빠르게 작성할 수 있는 정도로 연습해 두자.

Swift로 된 자료들이 많이 부족한 만큼, 이 글이 Swift로 알고리즘 문제를 푸는 사람들에게 도움이 되길 바란다.

참고

여러 사람의 풀이와 나의 문제 풀이 경험

일단 기초부터

🎄트리

트리는 데이터 사이의 계층 관계를 표현하는 자료구조로, 아래 그림과 같이 노드(동그라미, 정점이라고도 함)와 가지(동그라미 간의 연결선, 간선이라고도 함)로 구성된다. 각 노드는 가지를 통해 다른 노드와 연결될 수 있다.

간단하게 노드는 마을 하나하나를, 가지는 마을을 서로 연결하는 다리라고 생각하면 된다.

트리의 가장 위쪽에 있는 노드를 루트(root)라고 하며, 루트는 트리 하나에 한 개만 존재한다. 또한, 루트에서 얼마나 멀리 떨어져 있는가를 나타내는 것이 레벨(level)이다. 가장 위쪽에 있는 루트의 레벨은 0이고, 가지가 한 단계씩 아래로 뻗어 내려갈 때마다 레벨이 1 증가한다.

👀 너비 우선 탐색 (Breadth-First Search)

너비 우선 탐색은 동일 레벨 전체를 탐색한 뒤 다음 레벨로 나아가는 탐색 방법이다. 깊이 우선 탐색이 레벨 끝까지 깊게 파고 내려갔다 다시 돌아오는 것과 달리 루트에서 가까운 노드들부터 우선으로 탐색하게 되는 차이가 있다.

위 그림과 같이 탐색하게 되며, 루트와 가까운 노드부터 탐색해 나간다는 특성 때문에 주로 최단 거리를 구하는 문제에서 유용하게 쓰인다.

🔍 BFS와 큐

BFS를 구현하기 위해 왜 큐가 필요한지, 간단한 미로 탐색 예제를 통해 살펴보자.

파란색 칸은 이동할 수 있는, 주황색 칸은 이동할 수 없는 벽이다. (0, 0) 칸에서 출발하여 탈출구인 초록색 칸(3, 5)에 도달하는 것이 목표이다. BFS로 탐색해 나가는 일련의 과정을 보며 큐 자료구조가 쓰이는 방법을 살펴보자.

아직 방문하지 않은 이동 가능한 길을 상하좌우를 시계방향으로 확인하며, 거리 확인을 위해 방문 표시는 본인의 칸 방문 표시 + 1로 할 것이다.

1. (0, 0)에서 시작, (0, 0)을 push하고, 방문 표시를 한다.

2. 큐에서 pop하여 (0, 0)이 현재 대상 노드가 되고 주변을 탐색한다.

3. 아직 방문하지 않았으면서 이동할 수 있는 칸(1, 0)이 있다면 큐에 push하고 방문 표시를 한다.

4. (0, 0)에서 탐색을 마쳤으므로, 다음 탐색할 노드를 큐에서 pop하여 현재 대상 노드로 두고 주변 탐색을 진행한다. (그림에는 오른쪽과 아래만 탐색하지만, bfs에서 위쪽도 일단 탐색한다. 다만 이미 방문한 칸이기 때문에 큐에 추가하지 않는다.)

5. 아직 방문하지 않았으며 이동 가능한 칸 (1, 1)과 (2, 0)이 큐에 push되고 방문 표시를 남긴다.

6. (0, 0)에서 탐색을 마쳤으므로, 다음 탐색할 노드를 큐에서 pop하여 현재 대상 노드로 두고 주변 탐색을 진행한다. (역시 상하좌우를 모두 탐색하지만, 벽인 (0, 1)과 (2, 1) 그리고 이미 방문한 (1, 0)은 큐에 추가하지 않게 된다.)

7. 아직 방문하지 않았으며 이동할 수 있는 칸인 (1, 2)가 큐에 push되고 방문 표시를 남긴다.

8. (1, 1)에서 탐색을 마쳤으므로, 다음 탐색할 노드를 pop하여 현재 대상 노드로 두고 주변 탐색을 진행한다. (역시 상하좌우를 모두 탐색한다.)

9. 아직 방문하지 않았으며 이동할 수 있는 칸인 (3, 0)이 큐에 push되고 방문 표시를 남긴다.

...

이러한 일련의 과정을 거쳐 초록색 탈출구 칸까지 도착하게 되며, 미로에 표시한 값을 통해 최단 거리가 얼마인지 얻을 수 있다.

요약

BFS는 다음과 같은 과정을 거쳐 탐색한다.

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다.
2. 큐에서 원소를 꺼내어 그 칸에 인접한(문제의 기준마다 다를 수 있음.) 칸에 대해 탐색을 진행한다.
3. 탐색이란, 해당 칸을 이전에 방문했거나 방문할 수 없는 조건(미로 문제에서는 벽에 해당)이라면 아무것도 하지 않고, 처음으로 방문한 방문 가능한 칸이라면 방문 표시를 남기고 해당 칸을 큐에 삽입한다.
4. 큐가 빌 때까지 혹은 탈출구에 도착할 때까지 2번을 반복한다.

모든 칸이 큐에 한 번씩만 들어가므로, 시간복잡도는 칸의 수와 같은 O(N)이다.

구현 시 주의점

처음 BFS를 구현할 때 자주 하는 실수로

1. 시작점, 다음 탐색 노드 등을 큐에 넣을 때 방문했다는 표시를 하기. 2. 탐색할 노드의 좌표가 인덱스 범위를 벗어났는지 체크하기.

등이 있다. BFS가 시간 초과가 나거나 - 메모리 초과가 난다면 1번을 제대로 처리하지 못해 같은 칸이 계속 큐에 다시 들어가지는 않는지 확인해 보자. 만약 인덱스 오류가 난다면, 2번을 다시 점검해 보자.

큐의 선입 선출 방식 그대로 BFS가 작동하는 것을 볼 수 있다. 이처럼 BFS를 구현하는 데 큐가 필수적인데, Swift에는 기본 제공 큐가 없으므로 다른 방법을 통해 BFS를 구현해야 한다.

다음 글에서는 Swift로 BFS를 구현하는 세 가지 방법을 소개한다!

References

바킹독 블로그 - BFS KKS227 블로그 - 너비 우선 탐색 Do it! 자료구조와 함께 배우는 알고리즘 입문 (파이썬 편)

Part 1. 프로그래밍 언어 & 운영체제 (OS)

1.1 프로그래밍 언어와 컴파일러

컴퓨터는 0과 1로 이루어진 기계어를 사용해서 인간이 컴퓨터와 직접 소통하기는 매우 어렵다! 따라서, 이 둘간의 중간 번역기 역할을 해주는 도구가 필요한데, 그것이 바로 '컴파일러' 라는 프로그램이다.

이제 우리는 컴퓨터와 직접 소통하는 대신, 컴퓨터에게 할 일이 적힌 문서(명령)을 자바, 파이썬, 스위프트 등과 같은 프로그래밍 언어로 작성해 컴파일러로 넘겨주면 된다. 그러면 이에 따라 컴파일러가 기계어인 0과 1로 적절히 변환해 컴퓨터에게 전달을 하고, 그 결과 적절한 기능을 수행할 수 있게 된다.

1.2 개발자와 IDE

앞서 살펴본 것과 같이 컴퓨터에게 문서로 일을 시키는 사람이 바로_개발자이다. 일련의 명령들을 모두 프로그래밍 언어로 작성하게 되는데, 이 행동을 '프로그래밍' 혹은 '코딩' 이라고 한다.

프로그래밍 언어를 작성하는 것도 역시 만만치 않은 일이므로, 이를 도와주는 프로그램이 존재한다. 바로 많이 들어보았을 IDE(Integrated Development Environment), 통합 개발 환경이다.

일반적으로 문서 작업을 할 때 사용하는 한컴이나 워드 비슷한 것이라 생각하면 된다. IDE의 예로는 Android Studio, Xcode, Eclipse, PyCharm 등이 있다. 각 IDE는 안드로이드 개발, 애플 기기의 앱 개발, 웹 개발, 파이썬 개발 등으로 특화된 목적을 가지고 있다. (여러 언어와 여러 분야를 지원하는 IDE도 존재한다.)

참고

비전공자를 위한 이해할 수 있는 IT지식 - 프로그래밍 언어 & 운영체제(OS) 파트

백준 문제 풀이를 위한 기초! 입력을 읽어들이는 역할을 수행하는 readLine() 함수에 대해 알아보자

정의

readLine() 함수에 대한 애플 Documents의 간단한 설명과 정의는 아래와 같다.

readLine(strippingNewline:) 표준 입력에서 현재 줄의 끝 또는 EOF(End of File)에 도달할 때까지 읽은 문자열을 반환합니다.

func readline(strippingNewline: Bool = true) -> String?

분석

이해를 위해 다음과 같은 입력이 들어왔다고 가정해보자.

입력

1
8 2 Hello

이때 readLine() 함수를 세번 실행하면 반환값은 다음과 같다.

결과

readLine()      // Optional("1")
readLine()      // Optional("8 2 Hello")
readLine()      // nil

간단하게 보자면, 들어온 콘솔 입력을 한 줄씩 한 줄씩 읽어서 String? 타입의 값으로 반환해준다. 그렇다면 어째서 다루기 불편하게 String? 타입으로 반환하는 걸까?

그 이유 역시 간단하다. 마지막 readLine()의 반환 값을 보면 알 수 있듯이, EOF에 도달한 이후 readLine() 함수를 실행한다면 입력된 문자열이 없으므로 nil을 반환함으로써 이러한 경우를 처리하기 위함이다.

활용

여기까지 잘 이해되었다면, readLine() 함수를 이용해 입력 값을 처리하는 여러 방식들을 살펴보자. 백준 문제를 풀기 위해 제대로 알고 넘어가는 것이 좋다.

백준에서 입력받은 값은 대부분 배열에 넣어 처리하는 경우가 많다. 하나의 배열에 넣어 정리하고 싶은 경우, 이를 처리하는 방식은 다음과 같이 나뉜다.

1. 줄 바꿈을 통해 입력이 구분된 경우

readLine() 함수는 콘솔 입력을 통해 한 줄씩 읽어 들여 반환하므로, 입력이 들어오는 만큼 for문이나 while문을 이용해 반복 실행해주면 된다. 들어올 입력의 개수가 첫 번째 줄에 입력된 경우, 다음과 같이 처리할 수 있다.

입력

3   // 입력의 개수
1
7
645

결과

let N = Int(readLine()!)!     // 입력의 갯수 N
var inputs: [Int] = []        // 입력이 정리되어 들어갈 빈 배열

for _ in 0..<N {
    inputs.append(Int(readLine()!)!)
}

// inputs = [1, 7, 645]

만일 입력의 갯수를 모르는 경우는 어떻게 해야 할까?

readLine() 함수가 입력이 없는 경우, 즉 EOF 이후 실행된 경우 nil을 반환하는 것을 활용하면 된다. 이를 이용하면 EOF를 자체적으로 감지하고 읽어 들이는 것을 제때 중지할 수 있다.

입력의 개수 N이 첫째줄에 주어지지 않은 채, 입력의 개수가 모르는 채로 입력이 들어오는 경우, 다음과 같이 처리할 수 있다.

입력

17
60
24

결과

var inputs: [Int] = []        // 입력이 정리되어 들어갈 빈 배열

while let input = readLine() {
    inputs.append(input)
}

// inputs = [17, 60, 24]

백준 문제를 풀다 보면 종종 입력의 개수를 제공하지 않는 경우가 있으므로 잘 기억해두었다 필요할 때 사용하도록 하자! 또한, 특정한 값으로 EOF를 알리는 경우도 있는데, 이 때도 역시 while문을 이용해 비슷한 방식으로 처리해주면 된다.

2. 공백을 통해 입력이 구분된 경우

'3 4 5 6'과 같이 여러 입력값이 공백을 통해 구분되는 경우, readLine()은 전체를 한 번에 읽어 들이기 때문에 이를 배열로 처리해주는 과정이 필요하다.

String? 타입으로 반환하는 것을 생각하면 아래와 같은 코드를 사용해 간단하게 처리할 수 있다.

입력

3 4 5 6

결과

var inputs = readLine()!.split{$0 == " "}.map{Int(String($0))!}

// inputs = [3, 4, 5, 6]

String? 타입의 반환을 옵셔널 강제 해제 연산자 !를 통해 String 타입으로 해제한 뒤, split(seperator:) 메소드를 통해 공백마다 값을 분리해준다. (여기서는 후행 클로져를 사용하였다.) 이렇게 분리된 값은 Substring 타입으로 배열에 정리되며, 이를 우리가 사용하고자 하는 타입으로 map 함수를 통해 변환해주면 끝이 난다.

지금은 조금 어색하겠지만, 알고리즘 문제 해결을 위한 것이므로 간결하고 빠른 코드 작성을 위해 이같이 작성해주는 것이 좋다.

참고로, 백준 문제를 풀 때는 입력이 들어오는 것이 확실하므로 옵셔널 강제 해제 연산자 !를 애용하는 것이 좋다. 확실한 값을 굳이 옵셔널인 채로 다룰 필요가 없기 때문이다. 실제 개발에서는 오류처리를 위해 옵셔널 강제 해제 연산자를 잘 사용하지 않지만, 알고리즘 풀이에 한해서는 편하게 쓰자.

3. 공백 없이 입력이 구분된 경우 (각 입력이 Character 하나인 경우)

앞서 살펴본 예와 같이 한자리 숫자의 입력인데, 이번에는 공백없이 '3456'과 같이 입력된 경우, 아래와 같은 코드를 유용하게 사용할 수 있다

결과

var inputs = ArraY(readLine()!).map{ Int($0) }

// inputs = [3, 4, 5, 6]

String은 Character의 모임이므로, 이를 Array 초기화 메소드에 인자로 넣으면 ["3", "4", "5", "6"]과 같이 [Character] 타입의 배열을 얻을 수 있다. 역시 이를 원하는 타입으로 가공하기 위해 map을 사용했다.

결론

백준 문제를 풀며 다양한 방식의 입력을 접하게 될 텐데, 매 경우마다 해결 방법을 외워두기보다는 readLine() 함수 자체에 대해 잘 이해하고 있다면, 자연스럽게 해결방법을 얻을 수 있으리라 생각한다.

readLine() 함수는 한 줄씩 읽어 들이고, 그 반환 타입은 Sting? 이라는 점. 꼭꼭 기억하자!!

Reference

야곰 스위프트 프로그래밍 3판 (Swift 5) 애플 공식 문서

🛠 블로그를 시작하게 된 이유

1. 티스토리로 시작하려 했으나.. 뭔가 불편해!

생각보다 직관적이지 않고 사용이 불편한 점이 많았다. 무거운 느낌.

2. 공부 정리를 위해

노션으로 매일 공부한 것을 정리하고는 있지만, 하루에 공부한 것들이 뒤섞여 있다보니 정보정리 측면에서 좋지 않았다. 이제 슬 정리해야할 때가 왔는데, 어짜피 정리할거 블로그에 하는게 더 좋지 않을까? 하는 생각이 들었다.

또 내가 배운 것을 여러 사람이 읽고 이해할 수 있는 글을 쓴다는 것 자체가 역시 큰 공부이기 때문.

3. 마크다운

마크다운을 사용해 글을 작성한다는 것이 또 Velog만의 매력이라 생각한다. 어짜피 앱 개발을 하고, 주석을 깔끔하게 달기 위해서는 마크다운 문법을 알아야하기 때문이다. 레이텍을 배울 때 마크다운을 쓰며 재밌었던 기억이 있어서 끌리는 것도 있다.

🗓앞으로의 운영 계획

1. 하루를 정리하는 글쓰기 (22~23)

이번에 애플 아카데미를 지원하기 위해 나의 일생 항목을 고민하다 보니, 자신의 하루하루를 회고하는 것이 중요하다는 것을 느꼈다. 내가 어떤 사람인지, 오늘은 어떤것을 하고 그로 인해 어떤 감정들을 느꼈는지 등의 것을 더 잘 알기 위해서는 나를 돌아보는 시간이 필요하다.

현재 군 생활 중이므로, 점호가 끝난 22시 이후에 간단하게 하루 정리글을 규칙적으로 쓰려 한다. 내용은 하루에 대한 회고인만큼 당일 한 것, 기분, 다짐 등이 중점이 될 것이며, 다음날의 계획까지 정리하려 한다.

2. 정리글 올리기 (07~08:20)

매일 공부한 것들을 정리하는 것은 여전히 노션에서 이루어질 것이다. 공부하는 동안에는 깔끔하게 정리한 글을 쓰다가는 집중이 깨지는 편이라, 러프하게 휘갈기듯 정리하는 용도로 노션이 사용될 것이다. 마치 물건이 정리되지 않은 창고 같은 느낌.

물론 이곳도 너-무 고민하며 쓰지 않게 노력할 예정이지만, (글 쓰는데 너무 고민하면 오히려 못 쓰는 타입이다..) 하루에 공부한 내용을 정리해 글을 쓰기보다는 한가지 주제에 대해 정리하고 글을 올리는 용도로 사용할 것이다. 노션에 창고처럼 쌓인 지식들을 깔끔하게 정리하는 곳이 될 예정!

정리글은 6시 반에 기상해 노션을 보며 작성할 예정. 출근 전까지 하나씩 매일 글을 쓸 수 있도록 힘내보자. (잘 일어날 수.. 있겠지..?)

꼭 정보 정리가 아닌글일수도..(B&O 헤드폰 너무 좋아 같은 글도 올리고 싶다.)