라이브스마트

코딩테스트에서는 알고리즘과 자료구조에 대한 깊은 이해가 요구됩니다. 이번 강좌에서는 “내림차순으로 자릿수 정렬하기”라는 알고리즘 문제를 해결하면서 코틀린의 특성과 유용한 기능들을 살펴보겠습니다.

문제 설명

주어진 정수 N의 각 자릿수를 내림차순으로 정렬하여 그 수를 재구성하라. 자릿수를 정렬한 후의 숫자를 반환하라. 단, 정수 N은 0 이상 2³¹-1 이하이다.

예를 들어:

• 입력: 118372 → 출력: 873211
• 입력: 2143 → 출력: 4321
• 입력: 0 → 출력: 0

해결 과정

1단계: 문제 이해하기

문제를 해결하기 위해 첫 번째로 할 일은 주어진 문제를 정확하게 이해하는 것입니다. 입력값은 정수 형태이며, 우리가 해야 할 일은 이 정수를 자릿수별로 분리한 후 내림차순으로 정렬하는 것입니다. 정렬이 완료된 자릿수를 다시 조합하여 정수 형태로 반환해야 합니다.

2단계: 각각의 자릿수 추출하기

정수를 문자열로 변환하여 각 자릿수를 쉽게 접근할 수 있습니다. 문자열의 각 문자는 원래 정수의 자릿수를 나타내며, 이를 이용해 자릿수를 추출할 수 있습니다.

3단계: 자릿수 정렬하기

자릿수를 정렬하기 위해 코틀린의 기본 제공 기능을 사용할 수 있습니다. sortedDescending() 함수를 이용하여 자릿수를 내림차순으로 정렬할 수 있습니다.

4단계: 정렬된 자릿수 조합하기

정렬된 자릿수를 이용해 최종 결과를 다시 정수로 변환하는 작업이 필요합니다. 각 자릿수를 이어붙여 하나의 문자열로 만든 후 이를 다시 정수로 변환하여 반환하면 됩니다.

5단계: 최종 코드 구현

fun solution(N: Int): Int {
    // 정수 N을 문자열로 변환
    val strN = N.toString()
    
    // 자릿수를 내림차순으로 정렬
    val sortedDigits = strN.toCharArray().sortedDescending()
    
    // 정렬된 자릿수를 다시 합쳐 하나의 문자열로 만들기
    val resultStr = sortedDigits.joinToString("")
    
    // 문자열을 정수로 변환하여 반환
    return resultStr.toInt()
}
            

예제 테스트

작성한 솔루션을 테스트하기 위해 각 테스트 케이스를 실행해보겠습니다.

fun main() {
    println(solution(118372)) // 873211
    println(solution(2143))   // 4321
    println(solution(0))      // 0
}
            

위 코드를 실행하면 예상한대로 각 정수가 내림차순으로 정렬되어 출력됩니다.

시간 복잡도 및 공간 복잡도

여기서 사용된 알고리즘의 시간 복잡도는 O(d log d)입니다. 여기서 d는 자릿수의 수입니다. 자릿수를 정렬해야 하므로 로그 시간의 복잡도가 생깁니다. 공간 복잡도는 O(d)로, 자릿수를 저장하기 위한 배열을 사용하였습니다.

결론

이번 강좌를 통해 알고리즘 문제 해결에 있어 코틀린의 강력한 기능과 간결한 문법을 활용하는 방법을 배웠습니다. 자릿수 정렬 문제는 다른 알고리즘 문제로 확장할 수 있는 좋은 출발점입니다. 더 많은 문제를 풀어보면서 다양한 알고리즘과 자료구조를 익히는 것이 중요합니다.

코딩테스트 준비에 많은 도움이 되길 바랍니다. 다음 강좌도 기대해 주세요!

1. 문제 설명

이번 문제는 주어진 그래프에서 두 노드 사이의 최단 경로를 찾는 것입니다. 그래프는 인접 리스트 형태로 주어지며, 노드의 개수와 각 노드에 연결된 노드 정보가 제공됩니다. 여러분의 목표는 특정 시작 노드에서 특정 목표 노드까지의 최단 경로를 출력하는 것입니다.

문제

입력:
- 첫 번째 줄: 정점의 개수 N (1 ≤ N ≤ 1000)
- 두 번째 줄: 간선의 개수 M (0 ≤ M ≤ 10000)
- 다음 M개의 줄: 간선 정보 (A B) - A와 B는 각각 연결된 두 노드를 나타냄

- 이어서 마지막 줄에, 시작 노드 S와 목표 노드 T가 주어짐.

출력:
- S에서 T까지 가는 경로의 노드 목록을 출력하시오. 만약 경로가 없다면 "PATH NOT FOUND!"를 출력하세요.

2. 문제 접근 방식

이 문제는 전형적인 BFS 알고리즘을 사용하여 해결할 수 있습니다. BFS는 너비 우선 탐색 방법으로, 시작 노드에서 가까운 노드부터 탐색해 나아가는 방식입니다. 이를 통해 최단 경로를 찾는 것이 가능합니다. BFS 알고리즘의 주요 특징은 다음과 같습니다:

• 모든 노드를 동일한 깊이로 탐색하므로, 최단 경로를 보장합니다.
• 큐(Queue)를 사용하여 구현하며, 이론적으로 O(V + E)의 시간 복잡도를 가집니다. 여기서 V는 노드의 개수, E는 간선의 개수입니다.

BFS 알고리즘 단계

• 초기화: 시작 노드에 대한 방문 표시 및 거리 초기화. 큐에 시작 노드를 삽입.
• 탐색 과정: 큐가 비어 있지 않은 동안 반복. 큐에서 노드를 꺼내고, 해당 노드의 인접 노드들 중 방문하지 않은 노드를 큐에 추가.
• 경로 추적: 각 노드의 부모 노드를 기록해 놓아 나중에 경로를 추적할 수 있도록 함.

3. 코틀린 코드 구현

이제 위의 접근 방식에 따라 코틀린으로 BFS를 구현해 보겠습니다. 아래 코드를 참조하여 주어진 문제를 해결하는 방법을 확인하세요.

import java.util.*

data class Edge(val to: Int, val weight: Int)

fun bfs(graph: List>, start: Int, target: Int): List? {
    val queue: Queue = LinkedList()
    val visited = BooleanArray(graph.size)
    val parent = IntArray(graph.size) { -1 }  // 부모 노드 추적
    queue.add(start)
    visited[start] = true

    while (queue.isNotEmpty()) {
        val current = queue.poll()

        // 목표 노드를 찾으면 경로 추적
        if (current == target) {
            return tracePath(parent, start, target)
        }

        for (edge in graph[current]) {
            if (!visited[edge.to]) {
                visited[edge.to] = true
                parent[edge.to] = current // 부모 노드 설정
                queue.add(edge.to)
            }
        }
    }
    return null // 경로가 없을 경우
}

fun tracePath(parent: IntArray, start: Int, target: Int): List {
    val path = mutableListOf()
    var current = target

    while (current != start) {
        path.add(current)
        current = parent[current]
    }
    path.add(start)
    path.reverse()  // 역순으로 추가되어 있으므로 반전
    return path
}

fun main() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
    val m = scanner.nextInt()
    val graph = List(n) { mutableListOf() }

    // 그래프 생성
    for (i in 0 until m) {
        val a = scanner.nextInt() - 1
        val b = scanner.nextInt() - 1
        graph[a].add(Edge(b, 1)) // 방향이 없는 그래프이므로 양쪽 다 추가
        graph[b].add(Edge(a, 1))
    }

    val start = scanner.nextInt() - 1
    val target = scanner.nextInt() - 1
    val result = bfs(graph, start, target)

    if (result != null) {
        println(result.joinToString(" "))
    } else {
        println("PATH NOT FOUND!")
    }
}

4. 예시 입출력

예시 1

입력:
5 4
1 2
1 3
2 4
3 5
1 5

출력:
1 3 5

예시 2

입력:
5 3
1 2
2 3
4 5
1 4

출력:
PATH NOT FOUND!

5. 마무리

이번 강좌에서는 너비 우선 탐색(BFS)을 활용하여 그래프에서 두 노드 사이의 최단 경로를 찾는 문제를 다뤘습니다. BFS는 탐색의 용이함 덕분에 많은 알고리즘 문제에서 유용하게 사용됩니다. 실제 시험이나 코딩테스트에서 BFS를 적절히 활용하여 문제를 해결하는 능력을 기르는 것이 중요합니다.

이제 여러분도 BFS을 활용해 다양한 문제를 풀어보시길 바랍니다. 코틀린으로 구현해 보며 알고리즘의 이해도를 높이고, 현업에서도 사용할 수 있는 능력을 키워보세요!

들어가며

안녕하세요! 이번 포스팅에서는 깊이 우선 탐색(DFS, Depth-First Search) 알고리즘에 대해 알아보겠습니다. DFS는 그래프나 트리 구조에서 사용되는 탐색 알고리즘으로, 최대한 깊이 들어간 후 인접 노드를 탐색하는 방법입니다. 코딩테스트에 자주 출제되는 중요한 주제이니 알고리즘 이해와 문제 풀이 능력을 기르기 위해 꼭 마스터해두길 추천합니다.

문제 설명

문제 제목: 섬의 개수

주어진 2D 배열에서 ‘1’은 육지, ‘0’은 바다를 나타냅니다. 연속적으로 연결된 ‘1’들은 하나의 섬으로 간주합니다. 육지 ‘1’과 수평 또는 수직으로 연결된 모든 ‘1’은 같은 섬에 포함됩니다. 주어진 배열에서 섬의 개수를 구하세요.

입력 예시

[
    [1, 1, 0, 0, 0],
    [0, 1, 0, 0, 1],
    [1, 0, 0, 1, 1],
    [0, 0, 0, 0, 0],
    [1, 0, 1, 0, 1]
]

출력 예시

섬의 개수: 5

문제 풀이 과정

이 문제는 DFS 알고리즘을 사용하여 해결할 수 있습니다. 다음 단계를 통해 문제를 해결해보겠습니다.

1단계: 그래프 표현

문제에서는 2D 배열로 주어지는 그래프를 다루고 있습니다. 각 ‘1’은 육지를 나타내며, 문제를 해결하기 위해서는 이 육지들이 어떻게 연결되어 있는지를 파악해야 합니다.

2단계: DFS 알고리즘 구현

DFS를 사용하여 각 육지 ‘1’을 방문할 때, 그것이 속한 섬을 하나로 묶어야 합니다. 이를 위해 재귀 함수를 정의하여 인접한 육지 ‘1’들을 방문하게 만듭니다.

3단계: 코드 작성

이제 기본적인 DFS 알고리즘을 구현하는 코드를 작성해보겠습니다. 코틀린을 사용하여 다음과 같은 방식으로 구현할 수 있습니다.

fun numIslands(grid: Array): Int {
    if (grid.isEmpty()) return 0
    var count = 0

    fun dfs(i: Int, j: Int) {
        if (i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] == '0') {
            return
        }
        grid[i][j] = '0' // 방문 처리
        dfs(i - 1, j) // 상
        dfs(i + 1, j) // 하
        dfs(i, j - 1) // 좌
        dfs(i, j + 1) // 우
    }

    for (i in grid.indices) {
        for (j in grid[i].indices) {
            if (grid[i][j] == '1') {
                count++
                dfs(i, j) // 새로운 섬 발견
            }
        }
    }
    return count
}

4단계: 코드 설명

위의 코드에서 numIslands 함수는 2D 배열을 매개변수로 받고, 섬의 개수를 반환합니다.
내부의 dfs 함수는 재귀적으로 각 육지를 방문하며, 이미 방문한 육지는 ‘0’으로 변경하여 중복 방문을 방지합니다.
이중 루프를 통해 배열의 각 요소를 확인하며, ‘1’이 발견될 때마다 섬의 개수를 증가시키고 dfs를 호출합니다.

5단계: 시간 복잡도 및 공간 복잡도

DFS 알고리즘의 시간 복잡도는 O(M * N)입니다. M은 행의 개수, N은 열의 개수를 의미합니다.
공간 복잡도는 O(H)이며, H는 재귀 호출 스택의 깊이를 의미합니다. 최악의 경우에는 O(M + N)이 될 수 있습니다.

테스트 케이스 분석

위 설명으로 기본적인 코드를 작성해보았는데, 다양한 테스트 케이스를 통해 코드의 정확성을 검증하는 것이 중요합니다.
다음은 몇 가지 테스트 케이스에 대한 설명입니다.

1. 테스트 케이스 1:
   입력:

   [[1,1,0,0],[0,1,0,0],[0,0,0,1],[1,0,0,1]]

   예상 출력: 2

2. 테스트 케이스 2:
   입력:

   [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]

   예상 출력: 0

3. 테스트 케이스 3:
   입력:

   [[1,1,1,1],[1,0,0,0],[1,1,1,1]]

   예상 출력: 1

마치며

이번 포스팅에서는 깊이 우선 탐색(DFS)에 대해 설명하고, 예제 문제를 통해 알고리즘을 직접 구현해보았s습니다.
DFS는 그래프 문제를 해결할 때 매우 유용한 도구이므로, 코딩테스트에서 자주 접할 수 있습니다.
다양한 문제를 풀어보면서 DFS를 깊이 있게 이해하고 활용할 수 있도록 연습해보세요.

기하학은 컴퓨터 과학에서 많은 분야에서 활용되며, 코딩테스트에서도 자주 출제되는 주제입니다.
이번 포스팅에서는 기하 사용자 문제를 다루고, 코틀린을 사용하여 효율적으로 해결하는 방법을
설명하겠습니다.

문제 설명

문제: 주어진 N개의 점이 2차원 평면에 있을 때, 이들 점 중에서 볼록 껍질(Convex Hull)을
이루는 점들의 좌표를 시계 방향으로 출력하시오.

볼록 껍질이란, 평면상의 점들 중에서 모든 점을 포함하는 가장 작은 볼록 다각형을 의미합니다.
이 문제는 흔히 알고리즘 문제로 자주 출제되며, 효율적인 알고리즘으로는 그레이엄 스캔(Graham’s scan)
이나 잔디밭 방식(Jarvis March) 등이 있습니다.

입출력 형식

입력: 첫 번째 줄에 정수 N(1 ≤ N ≤ 100,000)이 주어지고,
다음 N개의 줄에 각 점의 x, y 좌표가 주어진다.
(x, y는 -10^9 이상, 10^9 이하의 정수다.)

출력: 볼록 껍질을 구성하는 점들의 좌표를
시계 방향으로 출력하고, 각 좌표는 공백으로 구분한다.

문제 풀이 과정

문제를 풀기 위해서는 다음과 같은 단계들을 거쳐야 합니다:

1. 입력 데이터 처리:
   점의 좌표를 입력받아 리스트에 저장합니다.
   이때, 각 점을 Pair 객체로 저장하면 편리합니다.
2. 좌표 정렬:
   극각도를 기준으로 점들을 정렬합니다.
   가장 왼쪽 아래(또는 위) 점을 기준으로 삼고, 나머지 점들을 극각도에 따라 정렬합니다.
3. 볼록 껍질 생성:
   그레이엄 스캔 알고리즘을 사용하여 볼록 껍질의 점들을 찾습니다.
4. 출력 형식에 맞게 포맷팅:
   결과를 시계 방향으로 정리하고, 요구하는 형식으로 출력합니다.

코드 구현

        
            import kotlin.math.atan2
            
            data class Point(val x: Int, val y: Int)
            
            fun convexHull(points: List): List {
                val sortedPoints = points.sortedWith(compareBy({ it.x }, { it.y }))
                val hull = mutableListOf()
                
                // 아래쪽 부분
                for (point in sortedPoints) {
                    while (hull.size >= 2 && cross(hull[hull.size - 2], hull[hull.size - 1], point) <= 0)
                        hull.removeAt(hull.size - 1)
                    hull.add(point)
                }
                
                val lowerSize = hull.size
                
                // 위쪽 부분
                for (i in sortedPoints.size - 1 downTo 0) {
                    val point = sortedPoints[i]
                    while (hull.size > lowerSize && cross(hull[hull.size - 2], hull[hull.size - 1], point) <= 0)
                        hull.removeAt(hull.size - 1)
                    hull.add(point)
                }
                
                hull.removeAt(hull.size - 1) // 마지막 점은 중복되므로 제거
                
                return hull
            }
            
            fun cross(o: Point, a: Point, b: Point): Int {
                return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x)
            }
            
            fun main() {
                val n = readLine()!!.toInt()
                val points = List(n) {
                    val (x, y) = readLine()!!.split(" ").map { it.toInt() }
                    Point(x, y)
                }
                val hull = convexHull(points)
                hull.forEach { println("${it.x} ${it.y}") }
            }
        
    

결론

이번 포스팅에서는 볼록 껍질을 구하는 문제에 대해 설명하였습니다.
기하학적인 문제는 실전 코딩테스트에서 자주 출제되므로
충분히 연습하고 다양한 유형의 문제를 풀어보는 것이 중요합니다.
이 외에도 다른 기하학적 문제를 통해 문제 해결 능력을 키워나가시기 바랍니다.

추가 학습 자료

코틀린을 더 깊이 있게 배우고 싶으시다면 다음의 자료들을 추천드립니다:

• Kotlin 공식 문서
• Kotlin 예제 코드
• GeeksforGeeks의 볼록 껍질 소개

코딩 테스트 준비 잘 하시고, 좋은 결과 있기를 바랍니다!