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

문제 설명

주어진 N명의 학생이 서로 친구 관계를 맺고 있습니다. 친구 관계는 쌍으로 주어지며,
두 명의 학생 A와 B가 친구이면, A는 B의 친구이고 B는 A의 친구입니다.
이제, 여러분은 특정 학생의 친구의 친구를 모두 파악하고,
그 수를 반환하는 함수를 구현해야 합니다.

예를 들어, 친구 관계가 다음과 같이 주어진다면:

• (1, 2)
• (1, 3)
• (2, 4)
• (3, 5)

학생 1의 친구는 2와 3이며, 이 친구들의 친구는 4와 5가 됩니다.
따라서 학생 1의 친구의 친구는 총 4명입니다.

입력 형식

friends: List>, target: Int

– friends: 친구 관계를 나타내는 튜플의 리스트,
– target: 친구의 친구를 찾고 싶은 학생

출력 형식

– 친구의 친구 수를 나타내는 정수

문제 해결 과정

친구 관계를 파악하기 위해 우리는 그래프 이론을 적용할 수 있습니다.
각 학생은 노드가 되며, 친구 관계는 경계로 나타낼 수 있습니다.
이를 통해 주어진 학생과 그 친구들의 친구를 탐색하는 방식으로 문제를 해결할 수 있습니다.

1. 그래프 구성

먼저 친구 관계를 그래프 형태로 변환해야 합니다.
각 학생을 키로 하고, 그 친구들을 값으로 하는 맵을 만들어 보겠습니다.

fun buildGraph(friends: List>): Map> {
    val graph = mutableMapOf>()
    for ((a, b) in friends) {
        graph.computeIfAbsent(a) { mutableListOf() }.add(b)
        graph.computeIfAbsent(b) { mutableListOf() }.add(a)
    }
    return graph
}
            

2. 친구의 친구 찾기

그래프가 구성된 이후, 특정 학생의 친구를 찾고,
그 친구의 친구 목록을 구해야 합니다.
이 때, 친구 목록이 중복되지 않도록 주의해야 합니다.

fun findFriendsOfFriends(friends: List>, target: Int): Int {
    val graph = buildGraph(friends)
    val directFriends = graph[target] ?: return 0
    val friendsOfFriends = mutableSetOf()
    
    for (friend in directFriends) {
        val friendsOfCurrentFriend = graph[friend]
        if (friendsOfCurrentFriend != null) {
            for (fof in friendsOfCurrentFriend) {
                if (fof != target && !directFriends.contains(fof)) {
                    friendsOfFriends.add(fof)
                }
            }
        }
    }
    return friendsOfFriends.size
}
            

3. 전체 코드

이제 전체 코드를 정리해보겠습니다.

fun main() {
    val friendsList = listOf(Pair(1, 2), Pair(1, 3), Pair(2, 4), Pair(3, 5))
    val targetStudent = 1
    val result = findFriendsOfFriends(friendsList, targetStudent)
    println("학생 $targetStudent의 친구의 친구 수: $result")
}
            

복잡도 분석

이 알고리즘의 시간 복잡도는 O(N + M)입니다.
여기서 N은 학생 수, M은 친구 관계의 수를 의미합니다.
공간 복잡도 또한 O(N + M)입니다.
이는 각각의 학생과 친구 관계를 그래프 형태로 저장하기 때문입니다.

예제 및 테스트 케이스

다양한 예제를 통해 함수가 올바르게 작동하는지 확인해보겠습니다.

• 예제 1:
  
  입력:

  
                      friendsList = listOf(Pair(1, 2), Pair(1, 3), Pair(2, 4), Pair(3, 5))
                      targetStudent = 1
                      

  출력: “학생 1의 친구의 친구 수: 2”

• 예제 2:
  
  입력:

  
                      friendsList = listOf(Pair(1, 2), Pair(1, 3), Pair(2, 3))
                      targetStudent = 1
                      

  출력: “학생 1의 친구의 친구 수: 0”

• 예제 3:
  
  입력:

  
                      friendsList = listOf(Pair(1, 2), Pair(3, 4), Pair(4, 5))
                      targetStudent = 1
                      

  출력: “학생 1의 친구의 친구 수: 0”

결론

친구 관계를 파악하는 문제는 알고리즘 문제 중에서도 자주 출제되는 유형입니다.
그래프 구조를 통해 효과적으로 해결할 수 있으며,
각 단계에서 주의할 점을 잘 고려해야 합니다.
이 강좌를 통해 코틀린의 기능을 활용하여 문제를 해결하는 방법을 익혔기를 바랍니다.
앞으로 더 많은 알고리즘 문제를 다루며 코딩 실력을 쌓아가시길 바랍니다.

1. 서론

알고리즘 문제 해결의 핵심은 다양한 문제를 이해하고 해결하는 능력을 기르는 것입니다. 그 중에서도 최장 공통 부분 수열(Longest Common Subsequence, LCS) 문제는 여러 알고리즘 시험에서 자주 등장하는 기본적인 문제입니다. 이 글에서는 코틀린을 이용하여 LCS 문제를 해결하는 과정을 자세히 살펴보겠습니다.

2. 문제 설명

주어진 두 문자열이 있을 때, 이들 문자열에서 각각의 문자를 삭제하지 않고 공통으로 나타나는 가장 긴 부분 수열의 길이를 구하는 문제입니다. 다시 말해, 두 문자열에서 문자의 순서를 유지하면서 공통으로 찾아낼 수 있는 가장 긴 서브 시퀀스를 찾는 것이죠.

예제

• 문자열1: “ABCBDAB”
• 문자열2: “BDCAB”
• 최장 공통 부분 수열: “BCAB” (길이: 4)

3. 문제 해결의 접근법

LCS 문제를 해결하기 위한 일반적인 접근법은 동적 프로그래밍(Dynamic Programming)입니다. 동적 프로그래밍은 복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 방법론입니다. 여기에선 두 문자열의 각 문자를 비교하며, 최대 길이를 계산해 나갑니다.

3.1. 동적 프로그래밍 테이블 정의

먼저, 두 문자열의 길이를 각각 m, n이라고 할 때, dp[i][j]를 문자열1의 처음 i글자와 문자열2의 처음 j글자까지의 LCS의 길이로 정의합니다. 이 테이블의 크기는 (m+1) x (n+1)입니다. 테이블의 첫 번째 행과 열은 0으로 초기화합니다.

3.2. 점화식 설정

두 문자열의 마지막 문자까지 비교하며 다음의 규칙으로 테이블을 채워 나갑니다:

• 문자가 같을 경우: dp[i][j] = dp[i-1][j-1] + 1
• 문자가 다를 경우: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3.3. 결과 추출

이 과정을 통해 완성된 dp 테이블의 마지막 셀 dp[m][n]에는 두 문자열의 LCS 길이가 저장됩니다.

4. 코틀린 구현

이제 이론적인 설명을 바탕으로 코틀린을 이용해 실제로 LCS를 계산해보겠습니다.

fun longestCommonSubsequence(s1: String, s2: String): Int {
    val m = s1.length
    val n = s2.length
    val dp = Array(m + 1) { IntArray(n + 1) }

    for (i in 1..m) {
        for (j in 1..n) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])
            }
        }
    }

    return dp[m][n]
}

fun main() {
    val s1 = "ABCBDAB"
    val s2 = "BDCAB"
    println("최장 공통 부분 수열의 길이: ${longestCommonSubsequence(s1, s2)}")
}
            

5. 분석

위의 코드는 O(m * n)의 시간 복잡도와 O(m * n)의 공간 복잡도를 가집니다. 따라서 문자열의 길이가 길어질수록 성능이 감소할 수 있습니다. 그러나 LCS 문제는 다양한 최적화 기법을 통해 개선될 수 있습니다.

5.1. 공간 효율성 개선

현재는 2D 배열을 사용했지만, 실제로는 이전 행의 값만 필요하므로 1D 배열로도 해결 가능합니다. 이를 통해 공간 복잡도를 O(n)으로 줄일 수 있습니다.

fun longestCommonSubsequenceOptimized(s1: String, s2: String): Int {
    val m = s1.length
    val n = s2.length
    val dp = IntArray(n + 1)

    for (i in 1..m) {
        val prev = IntArray(n + 1)
        for (j in 1..n) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[j] = prev[j - 1] + 1
            } else {
                dp[j] = maxOf(dp[j - 1], prev[j])
            }
            prev[j] = dp[j]
        }
    }
    return dp[n]
}
            

6. 결론

최장 공통 부분 수열 문제는 알고리즘 공부와 코드 테스트에서 매우 중요한 문제입니다. 동적 프로그래밍을 활용하여 문제를 효율적으로 해결할 수 있으며, 여러 최적화 기법이 있음을 알게 되었습니다. 이 문제를 통해 알고리즘적 사고를 발전시키고 코틀린 프로그래밍을 연습할 수 있는 기회가 되길 바랍니다.