2024 카카오 겨울 인턴십 코딩테스트 후기

이전 블로그에 작성했던 글을 옮깁니다. 본 작성일은 2023.12.06 입니다. 

 

개요

오랜만에 코딩테스트를 응시했습니다. 알고리즘 공부를 관둔 지 1년 정도 흘렀는데요, 하루하루 실력에 하락을 느끼고 있었습니다. 그래서 어려운 코테로 분류되는 카카오 코테를 응시하고 실력을 가늠하고 싶었습니다.

 

결과는 5솔로 모두 해결했습니다. 주관적으로 이번 코딩테스트는 쉬웠습니다. 이전에 카카오 공채 코테를 응시한 적이 있는데, 구현 난이도가 어려운 문제가 다수 출제됐습니다. 그때는 7개의 문제로 구성되어 있었는데, 이번엔 5개로 시간도 널널했습니다.

 

다만, 해결하는 과정에서 이전보다 실력이 떨어졌다는 생각이 여러 번 들었습니다. 응시 환경에서는 아무래도 긴장할 수밖에 없지만,, 사실 긴장하지 않았습니다. 그럼에도 1번 문제에서 사소한 실수 때문에 몇십분을 허비하고, 4번 문제도 금방 구현할 수 있는 로직을 꼬아서 구현하느라 시간이 오래 걸렸습니다. 

 

해결 과정

아직 문제가 공개되지 않은 이유로, 최대한 기억을 더듬어 문제와 해결 과정을 서술했습니다.

 

1번

문제

지난달에 친구에게 선물 준 기록을 바탕으로 다음 달 선물 줄 친구를 선택하는 문제입니다.

 

해결 방법

굉장히 친절한 문제입니다. '누가 누구에게 선물을 주는가?'에 대한 조건이 문제에 잘 정리되어 있고, 이를 성실하게 구현한다면 무난하게 해결할 수 있습니다.

 

전체 코드

friends_map = {}
gift_table = [[0]*51 for __ in range(51)]
result = [0] * 51

def solution(friends, gifts):
    for i in range(len(friends)):
        friends_map[friends[i]] = i
    
    for i in range(len(gifts)):
        giver, receiver = gifts[i].split()
        gift_table[friends_map[giver]][friends_map[receiver]] += 1

    for i in range(len(friends)):
        cnt = 0
        for j in range(len(friends)):
            given_amount, receive_amount = gift_table[i][j], gift_table[j][i]
            my_cal = sum(gift_table[i]) - sum([gift_table[k][i] for k in range(len(friends))])
            your_cal = sum(gift_table[j]) - sum([gift_table[k][j] for k in range(len(friends))])

            if given_amount > receive_amount:
                cnt += 1
            elif given_amount < receive_amount:
                continue
            elif my_cal > your_cal:
                cnt += 1
        result[i] = cnt

    answer = max(result)
    return answer

 

2번

 

간단한 문제 설명

여러 개의 그래프가 주어집니다. 각 그래프는 도넛, 바, 꽈배기 모양 중 하나의 모습을 띠고 있습니다. 여기에 1개의 개별 노드가 추가되는데, 이 노드는 다른 모든 그래프와 1개의 간선으로 이어져 있습니다. 이 입력 정보를 바탕으로 각 모양의 그래프 개수를 각각 구하고 추가된 개별 노드의 번호를 알아내야 하는 문제입니다.

 

접근 방식

그래프의 모양이 난해해서 풀이를 생각하는 것이 어려웠습니다. 저는 복잡한 그래프를 단순화하기 위해 노드를 적절하게 소거해 나갔습니다. 도넛과 꽈배기 그래프의 특징은 사이클이 존재한다는 점입니다. 그래프에 존재하는 사이클을 모두 찾고, 사이클 내부에 존재하는 모든 노드를 소거하면 바 그래프와 추가된 노드만 남습니다. 남은 노드와 간선 정보로 적절하게 가공하면 원하는 정보를 얻을 수 있을 것입니다.

 

그럼 여기서 할 일은 크게 2가지입니다.

1. 사이클을 이용해서 도넛과 꽈배기 그래프를 소거하기
2. 남은 그래프 정보로 바 그래프와 추가된 노드 찾기

사이클을 이용해서 도넛과 꽈배기 그래프를 소거하기

이 작업을 위해서 많은 역할을 수행해야 합니다. 단순히 노드만 소거하는 것이 아니라 도넛과 꽈배기 그래프의 개수를 카운트해야 합니다. 이 작업은 상당히 복잡합니다. 하나의 사이클을 찾았다고 가정해 봅시다. 이 사이클이 하나의 그래프라고 할 수 있을까요? 아닙니다. 꽈배기 그래프의 경우에는 그래프 내부에 여러 사이클이 있기 때문입니다. 우리는 도넛과 꽈배기 그래프를 정확하게 판별하고 카운트한 후 소거해야 합니다.

 

저는 여기에서 SCC 알고리즘가 떠올랐습니다. SCC 알고리즘은 '가장 큰 사이클'을 판별하는 알고리즘입니다. 그리고 문제의 요구 사항을 완전히 충족합니다. 다른 레퍼런스를 참고한다고 해도 된다는 규정이 있어서 ICPC 용으로 만들어둔 템플릿 중 타잔 알고리즘을 사용했습니다.

 

타잔 알고리즘은 가장 큰 사이클을 모두 판별해서 각 사이클을 하나의 그룹으로 묶어서 던져줍니다. 문제에서 주어진 그래프에 대해 알고리즘을 돌리면 도넛과 꽈배기 그래프는 하나의 그룹으로, 바 그래프는 노드 단위로 쪼개져서 추가된 노드와 함께 단일 노드 그룹으로 반환됩니다. 이제 도넛 그래프와 꽈배기 그래프를 카운트하고 소거하면 됩니다.

 

도넛 그래프 소거

사이클을 구성하는 간선과 노드의 개수 특징을 이용하면 쉽게 판별할 수 있습니다. 도넛 그래프는 1개의 노드에 1개의 간선이 있습니다. 사이클을 구성하는 노드의 개수와 각 노드가 갖고 있는 간선의 총합이 동일하면 도넛 그래프입니다. 위 로직은 한 가지 예외가 있는데, 사이클의 크기가 1인 경우에 바 그래프의 단일 노드와 도넛 그래프를 판별할 수 없습니다. 이때는 노드에 연결된 다음 노드가 자기 자신이면 도넛 그래프라는 특징을 이용해서 판별하면 됩니다.

def isDonut(arr):
    edge_count = 0
    node_count = len(arr)
    for edge in arr:
        edge_count += len(graph[edge])

    if node_count != edge_count:
        return False

    if len(arr) == 1:
        return graph[arr[0]][0] == arr[0]

    return True

 

꽈배기 그래프 소거

꽈배기 그래프는 3개 이상의 노드로 구성됩니다. 그리고 간선의 개수가 노드보다 1개 많습니다. 꽈배기 그래프는 특이한 유형이라 이 특징들만 이용하면 충분히 판별할 수 있습니다.

def isEight(arr):
    if len(arr) < 3:
        return False

    edge_count = 0
    node_count = len(arr)
    for edge in arr:
        edge_count += len(graph[edge])

    return node_count + 1 == edge_count

 

남은 그래프 정보로 바 그래프와 추가된 노드 찾기

이제 모든 사이클이 걸러지고 단일 노드만 남았습니다. 바 그래프는 노드 단위로 쪼개져서 추가된 노드와 함께 뒤섞여 있습니다. 이제 아주 간단하게 걸러낼 수 있습니다. 바 그래프를 구성하는 모든 노드는 1개의 간선을 갖습니다. 반면, 마지막에 추가된 노드는 2개 이상의 그래프와 연결되어 있기 때문에 2개 이상의 간선을 갖고 있습니다. 이 특징을 이용하면 추가된 노드는 쉽게 판별할 수 있습니다.

 

여기까지 진행하면 바 그래프의 개수만 구하면 됩니다. 이것 역시도 바 그래프의 마지막 그래프는 간선을 갖지 않다는 특징으로 쉽게 카운트할 수 있습니다.

for x in target:
    if len(graph[x[0]]) > 1:
        answer[0] = mapper.index(x[0])
    if len(graph[x[0]]) == 0:
        answer[2] += 1

 

전체 코드

import sys
sys.setrecursionlimit(10 ** 6)

MAX = 1_010_101
graph = [[] for __ in range(MAX)]
reverse_graph = [[] for __ in range(MAX)]
stack = []

mapper = [-1] * MAX

def solution(edges):
    answer = [0] * 4

		# 노드의 숫자가 너무 큰 경우를 대비해서 좌표 압축
    v = 0
    visited = [0] * MAX
    for edge in edges:
        a, b = edge
        if not visited[a]: 
            v += 1
            mapper[a] = v
            visited[a] = 1
        if not visited[b]: 
            v += 1
            mapper[b] = v
            visited[b] = 1

    for i in range(len(edges)):
        edges[i][0], edges[i][1] = mapper[edges[i][0]], mapper[edges[i][1]]

		# 코사라주 알고리즘 적용
    for edge in edges:
        a, b = edge
        graph[a].append(b)
        reverse_graph[b].append(a)

    stack = []
    visited = [0] * (v + 1)
    for i in range(1, v + 1):
        if visited[i] == 0:
            dfs(i, visited, stack)

    visited = [0] * (v + 1)
    result = []
    while stack:
        ssc = []
        node = stack.pop()
        if visited[node] == 0:
            reverse_dfs(node, visited, ssc)
            result.append(sorted(ssc))

		# 문제 핵심 로직
    target = []
    for x in result:
        if isDonut(x):
            answer[1] += 1
        elif isEight(x):
            answer[3] += 1
        else:
            target.append(x)

    for x in target:
        if len(graph[x[0]]) > 1:
            answer[0] = mapper.index(x[0])
        if len(graph[x[0]]) == 0:
            answer[2] += 1

    return answer

def isDonut(arr):
    edge_count = 0
    node_count = len(arr)
    for edge in arr:
        edge_count += len(graph[edge])
    if node_count != edge_count:
        return False
    if len(arr) == 1:
        return graph[arr[0]][0] == arr[0]
    return True

def isEight(arr):
    if len(arr) < 3:
        return False
    edge_count = 0
    node_count = len(arr)
    for edge in arr:
        edge_count += len(graph[edge])
    return node_count + 1 == edge_count

def dfs(node, visited, stack):
    visited[node] = 1
    for ne in graph[node]:
        if visited[ne] == 0:
            dfs(ne, visited, stack)
    stack.append(node)

def reverse_dfs(node, visited, stack):
    visited[node] = 1
    stack.append(node)
    for ne in reverse_graph[node]:
        if visited[ne] == 0:
            reverse_dfs(ne, visited, stack)

 

3번

 

문제

최대 10개의 주사위가 주어집니다. 일반적인 주사위와 다르게 주사위 눈이 무작위 수로 주어집니다. 예를 들면, [1, 2, 3, 45, 46, 47]과 같은 눈을 가진 주사위가 존재합니다. 주어진 주사위들을 정확히 반씩 친구와 나눠 갖고 동시에 주사위를 굴립니다. 굴린 주사위 눈들의 합을 계산하고 친구와 비교한 결과가 더 크다면 승리합니다.

 

접근 방식

단순하게 브루트포스를 진행하면 될 것 같지만, 높은 확률로 시간 초과가 뜰 것입니다. 10개의 주사위를 친구와 나눠 갖는 경우의 수는 10C5 입니다. 모든 주사위를 굴렸을 때 발생하는 경우의 수는 6^10입니다. 두 수를 곱하면 252 * 60,466,176 = 15,237,476,352 가지의 경우의 수가 있습니다. 문제의 시간 제한이 10초로 널널하지만 단순하게는 통과하기 어려울 것 같습니다.

 

최적화

최적화가 필요합니다. 우선, 10개의 주사위를 친구와 나눠 갖는 경우를 고려해 보겠습니다. "주사위를 나눠 갖는 로직"을 생략하거나, 경우의 수를 줄일 수 있을까요? 수학적으로 증명하진 않았지만 자명하게 불가능하다는 생각이 듭니다. 이 로직은 필수 불가결합니다.

 

하지만, 모든 주사위를 굴리는 경우는 다릅니다. 모든 경우의 수를 고려하는 과정에서 무수한 중복되는 연산이 발생합니다. 문제 단순화를 위해서 4개의 주사위가 주어졌다고 가정하겠습니다. 친구와 나는 각각 2개의 주사위를 선택합니다. 친구가 주사위를 굴려서 나올 수 있는 주사위 눈의 조합의 수는 36가지입니다. 그중 하나의 경우인 (1, 4)이 나온 경우를 생각해 봅시다. 친구 주사위의 합은 5입니다. 이제 제가 주사위를 굴릴 차례입니다. 저 역시도 36가지의 조합이 나올 수 있습니다. 그리고 각 조합의 합이 36개 나올 것입니다. 조합의 합이 중복될 수 있다는 사실에 유의해야 합니다.

친구 주사위 눈의 합: 5 내 주사위 눈의 합 36개: [2, 3, 3, 4, 4, 5, 5, 5, 5, 5, 6, 6, 7, 8, 9, 10, 11, ..]

 

내 주사위 눈의 합 36개를 친구 주사위 눈의 합과 비교하여 내가 이길 수 있는 경우의 수를 구해야 합니다. 단순하게 비교하면 36번의 연산이 필요하지만, 내 주사위 눈의 합을 정렬한다면 이진 탐색으로 log_2{36} 의 연산으로 구할 수 있습니다. 친구가 주사위를 굴려서 나오는 주사위 조합의 수는 36가지입니다. 36가지 모든 조합에 대한 각각의 합을 내 주사위 눈의 합과 비교하면 됩니다.

 

여기까지 정리해 보겠습니다.

1. 친구와 내가 주사위를 나눠 갖는다.
2. 내가 가진 주사위로 만들 수 있는 모든 경우에 대해 주사위 눈의 합을 계산하고 배열 형태로 저장한다.
3. 2에서 생성한 배열을 정렬합니다.
4. 친구가 가진 주사위로 만들 수 있는 모든 경우에 대해, 내 주사위 눈의 합 배열과 비교한다. 이때, 이진 탐색을 진행합니다.

2n개의 주사위가 주어졌을 때, 각 로직에 필요한 시간 복잡도는 다음과 같습니다.

1. 2n개 중에 n개를 선택하므로 2n_C_n
2. n개의 주사위를 던져서 발생하는 경우의 수는 6^n
3. 2번에서 발생한 경우의 수를 정렬하므로 k * log k, (k = 6^n)
4. n개의 주사위를 던져서 발생하는 경우의 수는 6^n에 매번 이진 탐색을 진행하므로 6^n * log k, (k=6^n)

총 시간복잡도는 (2n_C_n) * 2 * 6^n * log_6^n이고 최악의 경우인 n에 5를 대입하면 50,948,352의 연산이 발생합니다. 그리고 이는 10초 안에 충분히 들어오는 경우의 수입니다.

 

from itertools import combinations as comb, product as perm
from bisect import bisect_left as bis

def solution(dice):
    answer = []
    mmm = 0

    choice = list(range(len(dice)))
    for my_dice in comb(choice, len(choice)//2):
        your_dice = []
        for x in choice:
            if x not in my_dice:
                your_dice.append(x)
        
        a = [dice[i] for i in my_dice]
        b = [dice[i] for i in your_dice]

        ret = solve(a, b)
        if mmm < ret:
            mmm = ret
            answer = my_dice

    
    answer = [x+1 for x in answer]

    return answer

def solve(my_dice, your_dice):
    a = generate_possible(your_dice)
    a.sort()
    ret = 0

    choice = list(range(6))
    for idx in perm(choice, repeat=len(my_dice)):
        p = []
        for i in range(len(my_dice)):
            p.append(my_dice[i][idx[i]])
        
        r = max(0, bis(a, sum(p)))
        ret += r

    return ret

def generate_possible(dices):
    arr = []

    choice = list(range(6))
    for idx in perm(choice, repeat=len(dices)):
        p = 0
        for i in range(len(dices)):
            p += dices[i][idx[i]]
        arr.append(p)
    return arr

 

4번

 

이 문제 구현을 굉장히 난해하게 했습니다.

 

문제

m개의 코인과 n개의 카드가 주어집니다. 카드는 1부터 n의 수가 적힌 무작위 순서의 카드 뭉치로 주어집니다. 아마, n은 6의 배수였을 겁니다. 처음에 플레이어는 맨 위에서 n/3개의 카드를 손에 들고 시작합니다. 턴마다 행동 요령은 다음과 같습니다.

1. 덱 위에서 2개의 카드를 갖고 옵니다.
2. 카드는 1장에 1코인으로 구매할 수 있습니다. 구매하지 않는다면, 버립니다.
3. 합이 n+1이 되도록 2장의 카드를 버립니다. 버릴 카드가 없다면, 게임을 종료합니다.

위 행동을 반복했을 때, 최대로 도달할 수 있는 턴을 구하는 문제입니다.

 

접근 방식

처음에는 브루트포스로 생각했습니다. 현재 턴의 카드를 산다 안 산다는 것으로 구분하면, 한 턴에 4가지의 경우의 수가 발생합니다. 그럼 시간 복잡도는 4의 지수꼴인데 n이 컸고, 이 로직은 시간 초과를 유발했습니다. n이 굉장히 컸던 것으로 기억해서 O(n)의 시간 복잡도를 갖는 알고리즘을 적용해야 했습니다. 그럼, 선형 탐색밖에 없다고 생각 들어서 문제에 따라 시뮬레이션을 돌렸습니다.

 

단순하게 시뮬레이션을 돌리면 발생하는 문제는 '현재 상태에서 카드를 구매해야 하는가?'를 결정하는 것입니다. 플레이를 진행하면서 당장 사야 하는지는 알 수 없습니다. 하지만, 반드시 사야 하는 타이밍이 존재합니다. 바로 '낼 카드가 없을 때'는 반드시 카드를 구매해야 합니다. 그럼 어떤 카드를 사야 할까요? 현재 갖고 있는 카드와 n+1을 만들 수 있는 카드 한 장, 또는 n+1을 만들 수 있는 두 장을 사면 됩니다.

 

이제, 우리는 필요한 카드를 사야 합니다. 여기에서 발상의 전환이 필요합니다. 실제 게임에서는 현재 뽑은 카드만 살 수 있지만, 우리가 필요한 카드가 과거에 지나갔다면 어떻게 해야 할까요? 과거에 샀다 치고 코인을 내서 사면 됩니다. 또는 우리가 '카드를 뽑는 행위'를 '카드를 살 기회'를 얻었다고 생각하면 됩니다. 기회는 소멸되지 않고 남아 있습니다.

 

로직을 정리해 보겠습니다.

 

1. 카드 2장을 뽑습니다. 뽑은 카드에 대해 살 기회를 얻었다는 기록을 합니다.
2. 짝이 맞는 카드 2장을 냅니다. 낼 카드가 있다면, 1번으로 돌아갑니다.
3. 낼 카드가 없다면, 카드를 구매합니다.
   1. 갖고 있는 카드와 짝이 맞는 카드를 1장 구매합니다. 구매했다면, 1번으로 돌아갑니다.
   2. 갖고 있는 카드와 짝이 맞는 카드가 없다면, 짝이 맞는 2장을 구매합니다. 구매했다면, 1번으로 돌아갑니다.
4. 위 로직에서 조건을 충족하지 않는다면, 게임을 종료합니다.

이 문제에서 핵심은 특정 카드에 대해 짝이 맞는 카드는 오로지 1장 존재합니다. 짝을 맞추는 로직은 다양하게 구현할 수 있습니다. 관리해야 하는 상태는 '갖고 있는 카드', '살 기회가 있는 카드'입니다. 단순하게 리스트에 넣고 관리할 경우 탐색하는 시간이 최악의 경우에 $O(n)$이 될 수 있습니다. 따라서, 인덱스를 활용해서 해당 숫자의 카드가 존재하는지 여부를 flag 배열로 관리했습니다.

 

def solution(coin, cards):
    past = [0] * 1001
    get = [0] * 1001
    pay = 0

    n = len(cards)
    
    for i in range(n//3):
        x = cards[i]
        get[x] = 1
        if get[n+1 - x] == 1:
            pay += 1
            get[x] = 0
            get[n+1 - x] = 0

    answer = 0
    idx = n//3

    while idx < n:
        answer += 1
        
        a, b = cards[idx:idx+2]  # 카드 뽑기
        idx += 2
        
        past[a], past[b] = [1]*2  # 과거에 뽑은 카드라는 것을 표시

        if pay: # 낼 수 있는 카드가 있다면 
            pay -= 1
            continue

        if coin == 0:  # 낼 수 있는 카드가 없고, 돈도 없다면 종료
            break
				
				# 카드를 사야 하는 타이밍
        for i in range(n+1):
						# 현재 갖고 있는 카드 1장과 짝이 맞는 카드를 탐색
            if get[i] and past[n+1 - i]:
                past[n+1 - i] = 0
                get[i] = 0
                coin -= 1
                break
        else:   # 현재 갖고 있는 카드와 맞는 짝이 없어서 새로운 카드 2장을 사야 한다 
            if coin < 2: break

            for i in range(n+1):
                if past[i] and past[n+1 - i]:
                    past[i] = 0
                    past[n+1 - i] = 0
                    coin -= 2
                    break
            else:
                break
    else:
        answer += 1
    return answer

 

5번

 

문제

해당 문제에 대한 설명은 생략하겠습니다. 추후, 카카오에서 공식적으로 올라오면 참고 부탁드립니다.

 

사고 흐름

가장 단순한 접근은 현재 상태에서 삼각형을 두거나 사각형을 두는 것입니다. 이렇게 해결하면 모든 경우의 수는 2^n입니다. 하지만, n이 굉장히 컸던 것으로 기억합니다. 최적화가 필요합니다.

 

동적 계획법

우선은 경우의 수와 무관한, 놓는 순서를 특정해 보겠습니다. 저는 왼쪽에서부터 순서대로 놓겠습니다. 그리고 특정 위치를 X라고 하겠습니다. X 위치는 바닥과 맞닿아 있고 오른쪽 마지막 위치입니다. X 위치를 포함한 영역에 블록을 놓는 경우를 생각해 봅시다.

1. X 위치에만 삼각형을 둔다.
2. X 위치를 포함한 왼쪽 영역까지 사각형을 둔다.

1번 경우에, 전체 블록을 놓을 수 있는 경우의 수는 X - 1 위치까지 블록을 놓는 경우의 수와 일치합니다. 2번 경우에, 전체 블록을 놓을 수 있는 경우의 수는 X - 2 위치까지 블록을 놓는 경우의 수와 일치합니다.

 

이번에는 바닥과 맞닿지 않는 Y 위치를 고려해 보겠습니다. 동일하게 Y 위치를 포함한 영역에 블록을 놓는 경우를 생각해 봅시다.

1. Y 위치에만 삼각형을 둔다.
2. Y 위치를 포함한 왼쪽 영역까지 사각형을 둔다.
3. Y 위치 위에 영역이 존재한다면 해당 영역까지 사각형을 둔다.

1번 경우에, 전체 블록을 놓을 수 있는 경우의 수는 Y - 1 위치까지 블록을 놓는 경우의 수와 일치합니다. 2번 경우에, 전체 블록을 놓을 수 있는 경우의 수는 Y - 2 위치까지 블록을 놓는 경우의 수와 일치합니다. 3번의 경우에, 전체 블록을 놓을 수 있는 경우의 수는 Y - 1 위치까지 블록을 놓는 경우의 수와 일치합니다.

 

위에서 정리한 내용에서 X 또는 Y 위치까지 블록을 놓을 수 있는 경우의 X - 1, X - 2, Y - 1, Y - 2 위치까지 블록을 놓는 경우의 수의 연산 결과입니다. 그리고 각 경우의 수를 계산하기 위해서는 이전 위치까지의 경우의 수를 계산해야 합니다. 가장 단순하게 계산한다면 이전 위치까지의 경우의 수를 반복해서 계산해야 하지만, 한 번만 계산하고 메모리에 저장해두는 DP를 사용하면 반복된 계산을 줄일 수 있습니다.

 

전체 코드

def solution(n, tops):
    MOD = 10_007
    
    dp = [0] * (2*n+1)
    dp[0] = 1
    dp[-1] = 1

    for i in range(1, 2*n):
        if i % 2 == 0:
            dp[i] = dp[i-1] + dp[i-2]
        elif tops[i//2] == 0:
            dp[i] = dp[i-1] + dp[i-2]
        else:
            dp[i] = dp[i-1] * 2 + dp[i-2]
        dp[i] %= MOD

    dp[-1] = dp[-2] + dp[-3]
    return dp[-1] % MOD