[카테고리:] 코틀린 코딩테스트 강좌

들어가며

안녕하세요! 이번 포스팅에서는 깊이 우선 탐색(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의 볼록 껍질 소개

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

안녕하세요! 오늘은 취업 준비생과 코딩테스트 준비자들이 알아야 할 기수 정렬(Radix Sort)에 대해 알아보겠습니다. 기수 정렬은 정수들을 정렬하는 데 매우 효율적인 알고리즘 중 하나로, 특히 큰 데이터셋에서 그 성능이 빛을 발합니다.

기수 정렬이란 무엇인가?

기수 정렬은 분산 정렬의 일종으로, 정렬할 값들을 개별 자리수로 나누어 처리합니다. 이 방법은 정수형 데이터에 특히 효과적이며, 안정 정렬(stable sort)입니다. 기수 정렬은 대부분의 정렬 알고리즘과 달리 비교 기반이 아니므로, O(nk)의 시간 복잡도를 가집니다. 여기서 n은 정렬할 데이터의 개수이고, k는 가장 큰 수의 자리수입니다.

문제 설명

문제: 주어진 정수 리스트를 기수 정렬 알고리즘을 사용하여 오름차순으로 정렬하라.

다음과 같은 입력이 주어질 때, 기수 정렬을 사용하여 정렬된 결과를 출력해야 합니다.

입력: [170, 45, 75, 90, 802, 24, 2, 66]

출력: [2, 24, 45, 66, 75, 90, 170, 802]

기수 정렬 알고리즘 이해하기

기수 정렬의 기본 아이디어는 각 자리를 기준으로 카운팅 정렬을 반복 사용하는 것입니다. 기수 정렬의 수행 과정을 단계별로 살펴보겠습니다.

1단계: 자리수 분리

각 숫자를 숫자의 자리수(1의 자리, 10의 자리, 100의 자리 등) 별로 나누어 처리합니다. 각 자리수를 처리할 때는 카운팅 정렬을 통해 이 숫자들을 정렬합니다.

2단계: 카운팅 정렬

카운팅 정렬은 특정 자리수를 기준으로 입력 리스트를 정렬하는 방법입니다. 이 방법은 안정성이 확보되기 때문에, 처음에 조정한 상대적인 순서를 유지할 수 있습니다.

3단계: 반복

가장 작은 자리수부터 시작하여, 가장 큰 자리수까지 반복하여 정렬한 후 최종적으로 정렬된 결과를 얻을 수 있습니다.

기수 정렬의 구현 (코틀린 예제)

다음은 코틀린을 사용하여 기수 정렬을 구현한 코드입니다:

fun countingSort(array: IntArray, place: Int) {
    val size = array.size
    val output = IntArray(size)
    val count = IntArray(10)

    for (i in 0 until size) {
        count[(array[i] / place) % 10]++
    }

    for (i in 1 until 10) {
        count[i] += count[i - 1]
    }

    for (i in size - 1 downTo 0) {
        output[count[(array[i] / place) % 10] - 1] = array[i]
        count[(array[i] / place) % 10]--
    }

    for (i in 0 until size) {
        array[i] = output[i]
    }
}

fun radixSort(array: IntArray) {
    val max = array.maxOrNull() ?: return

    for (place in 1 until max + 1 step 10) {
        countingSort(array, place)
    }
}

위 코드는 먼저 카운팅 정렬을 수행하는 countingSort 함수를 정의합니다. 그 후, 주어진 배열의 최대값을 기준으로 자리수를 반복하며 정렬을 진행하는 radixSort 함수를 구현합니다.

코드 설명

• countingSort 함수는 주어진 자리수를 기준으로 정렬을 수행합니다.
• place는 현재 정렬할 자리수를 나타내며, 1의 자리에서 시작하여 10씩 증가합니다.
• count 배열은 각 숫자(0-9)의 출현 빈도를 세는 데 사용됩니다.
• 최종적으로 output 배열에 정렬된 결과를 저장하고 입력 배열을 업데이트합니다.

기수 정렬의 시간 복잡도

기수 정렬의 시간 복잡도는 O(nk)입니다. 여기서 k는 자리수이며 n은 배열의 크기입니다. 대부분의 다른 비교 기반 정렬 알고리즘은 평균적으로 O(n log n)의 시간 복잡도를 가지므로, 기수 정렬이 훨씬 더 빠른 성능을 보일 때가 많습니다. 특히, 입력 데이터의 크기가 많고 자리수가 적을 때 효과적입니다.

기수 정렬의 한계

기수 정렬은 몇 가지 한계점을 가지고 있습니다:

• 정수형 데이터에 적합: 이 알고리즘은 정수형 데이터에 특화되어 있으며, 문자열이나 부동 소수점 수에 대해서는 변형된 버전을 필요로 합니다.
• 범위 제한: 큰 값의 범위를 가지는 정수에 대해서는 메모리 사용량이 증가할 수 있으므로 주의해야 합니다.
• 메모리 사용: 중간 단계에서 임시 배열을 생성하므로, 메모리 사용량이 많을 수 있습니다.

결론

이번 강좌에서는 기수 정렬에 대해 자세히 알아보았습니다. 기수 정렬은 안정성이 뛰어나고 특정 상황에서 매우 효과적인 정렬 알고리즘입니다. 코딩테스트에서 기수 정렬을 이해하고 올바르게 적용하는 것은 많은 도움이 될 것입니다. 다음에는 다른 정렬 알고리즘에 대해서도 다루어보겠습니다. 감사합니다!