코틀린 코딩테스트 강좌, 선택 정렬

작성자: 조광형 | 날짜: [날짜]

서론

코딩 테스트는 오늘날 많은 기업의 채용 과정에서 중요한 역할을 합니다. 특히, 알고리즘 문제를 해결하는 능력은
이직과 신입 채용 모두에 있어 큰 영향을 미칩니다. 이번 강좌에서는 선택 정렬(Selection Sort) 알고리즘을
코틀린으로 구현하고, 이에 대한 문제를 풀어보겠습니다.

선택 정렬이란?

선택 정렬은 간단한 정렬 알고리즘 중 하나로, 주어진 리스트에서 가장 작은 요소를 찾아 첫 번째 위치와 교환하고,
이후 남은 리스트에서 가장 작은 요소를 찾아 두 번째 위치와 교환하는 방법입니다. 이러한 과정은
리스트가 정렬될 때까지 반복됩니다.

선택 정렬의 동작 원리

리스트에서 가장 작은 원소를 찾습니다.
그 원소를 현재 정렬되지 않은 리스트의 맨 앞에 위치한 원소와 교환합니다.
정렬되지 않은 리스트의 시작을 한 칸 앞으로 이동시킵니다.
2-3 과정을 리스트의 크기 – 1만큼 반복합니다.

문제 설명

주어진 정수 배열을 오름차순으로 정렬하는 선택 정렬 알고리즘을 작성하세요. 이때 구체적인 요구 사항은 다음과 같습니다:

입력: 정수 배열 (예: [64, 25, 12, 22, 11])
출력: 정렬된 정수 배열 (예: [11, 12, 22, 25, 64])

문제 풀이 과정

1단계: 문제 이해

첫 번째 단계는 문제를 완전히 이해하는 것입니다. 선택 정렬 알고리즘이 배열을 어떻게 정렬하는지 이해하고,
입력과 출력을 명확히 하는 것이 중요합니다.

2단계: 알고리즘 설계

다음으로, 선택 정렬의 알고리즘을 설계합니다. 코틀린을 사용하여 이러한 선택 정렬 알고리즘을 구현할 것입니다.

fun selectionSort(arr: IntArray): IntArray {
    for (i in arr.indices) {
        // 현재 인덱스 i를 가진 원소를 가장 작은 원소로 가정
        var minIndex = i

        // i 다음 인덱스부터 끝까지 반복하면서 최솟값을 찾음
        for (j in (i + 1) until arr.size) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }

        // 가장 작은 원소와 현재 인덱스의 원소를 교환
        if (minIndex != i) {
            val temp = arr[i]
            arr[i] = arr[minIndex]
            arr[minIndex] = temp
        }
    }
    return arr
}

3단계: 코드 구현

위의 알고리즘을 바탕으로 코틀린 코드를 작성합니다. 아래는 해당 알고리즘의 구현 예입니다:

fun main() {
    val array = intArrayOf(64, 25, 12, 22, 11)
    val sortedArray = selectionSort(array)

    println("정렬된 배열: ${sortedArray.joinToString(", ") { it.toString() }}")
}

4단계: 코드 테스트

작성한 알고리즘을 테스트하여 잘 작동하는지 확인합니다. 배열을 가지고 실제로 프로그램을 실행하여
결과를 확인합니다.

fun testSelectionSort() {
    val testCases = arrayOf(
        intArrayOf(64, 25, 12, 22, 11) to intArrayOf(11, 12, 22, 25, 64),
        intArrayOf(5, 4, 3, 2, 1) to intArrayOf(1, 2, 3, 4, 5),
        intArrayOf(1, 2, 3, 4, 5) to intArrayOf(1, 2, 3, 4, 5),
        intArrayOf(-1, -5, 3, 0) to intArrayOf(-5, -1, 0, 3)
    )

    for ((input, expected) in testCases) {
        val result = selectionSort(input)
        assert(result.contentEquals(expected)) {
            "Test failed for input: ${input.joinToString(", ")}. Expected: ${expected.joinToString(", ")}, but got: ${result.joinToString(", ")}}"
        }
    }
    println("모든 테스트 통과!")
}

fun main() {
    testSelectionSort()
}

5단계: 최적화 및 복잡도

선택 정렬의 시간복잡도는 O(n^2)이며 최악의 경우와 최선의 경우 모두 동일합니다. 이는 알고리즘의
비효율성으로 인해 대량의 데이터에서 성능 저하가 발생할 수 있습니다. 그러나 구현이 간단하고
데이터 양이 적을 때는 효과적으로 사용할 수 있습니다.

결론

이번 강좌에서는 선택 정렬의 이론과 코틀린으로의 구현 방법을 살펴보았습니다. 간단한 문제를 통해 알고리즘
문제를 푸는 과정을 이해하고, 실제 사용 예시를 통해 알고리즘의 동작 방식을 익힐 수 있었습니다.
다음 강좌에서는 더 효율적인 정렬 알고리즘을 다룰 예정이니 기대해 주세요.

서론