코데풀 - 코딩 테스트 함께 풀어봐요

2024년 1월 24일 수요일

2024 KAKAO WINTER INTERNSHIP 도넛과 막대 그래프

Vertex와 directed edge를 사용해서 graph를 구현하는 방법을 알아야 풀 수 있는 문제입니다.

class Vertex와 Edge를 사용해서 graph를 구현할 수 있구요.
Vertex으로 들어오는 edge가 incoming edge
Vertext에서 다른 Vertex로 나가는 edge가 outgoing edge 입니다.

이제, graph를 코드로 표현할 수 있게 되었구요,

문제에서 말하는 아래 문장을 잘 이해해야 문제를 풀 수 있습니다.

도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프가 여러 개 있습니다. 이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결했습니다.

첫번째로 해야할 일은 임의의 정점을 우선 찾아야 합니다.

문제입력으로는 edge만 주어지고, 정점이 주어지지 않습니다.

정점의 특징이 있는대요

incoming edge가 없다는 것이죠.

이것 만으로는 정점을 특정할 수 있습니다.

정점을 찾았으니, sub graph가 그래프가 도넛, 막대기, 8자, 그래프 중에 어떤 종류의 그래프인지 판단하는 로직이 필요합니다.

정점에서 outgoing 에지를 하나 선택하고, 에지의 to 에 해당하는 vertex를 선택합니다.

이번 풀이에서는 DFS 방식으로 edge를 탐색하겠습니다.

도넛 subgraph를 DFS로 계속 탐색해보면, 어떤 vertex에서 시작하던지, 방문했던 vertex로 되돌아 오게 됩니다. 따라서, visited vetex를 다시 방문했다면, subgraph가 도넛 모양인 것을 알 수 있습니다.
막대 subgraph incoming edge만 있고, outgoing edge가 없는 vertex가 반드시 있음
8자 subgraph는 visited vertex를 만나기 전에, incoming edge가 2개, outgoing edge가 2개인 vertex를 travel 하게 됩니다.

2024 KAKAO WINTER INTERNSHIP 주사위 고르기

주사위의 개수가 최대 10개 입니다. 10개의 주사위로 A와 B가 승부를 한다면, 이중에 5개를 고를 수 있죠. 우선은 2개의 주사위를 사용해서, 나올 수 있는 모든 경우의 수를 구하는 방법을 알아 보겠습니다.

[1, 2, 3, 4, 5, 6] [1, 2, 3, 4, 5, 6] 이렇게 2개의 주사위가 있구요.

첫번째 주사위의

1을 [1, 2, 3, 4, 5, 6]에 모두 더하면, [2, 3, 4, 5, 6, 7]

2를 [1, 2, 3, 4, 5, 6]에 모두 더하면, [3, 4, 5, 6, 7, 8]

3를 [1, 2, 3, 4, 5, 6]에 모두 더하면, [4, 5, 6, 7, 8, 9]

4를 [1, 2, 3, 4, 5, 6]에 모두 더하면, [5, 6, 7, 8, 9, 10]

5를 [1, 2, 3, 4, 5, 6]에 모두 더하면, [6, 7, 8, 9, 10, 11]

6을 [1, 2, 3, 4, 5, 6]에 모두 더하면, [7, 8, 9, 10, 11, 12]

2개의 주사위로 나올 수 있는 경우의 수를 모두 모아 보면

[2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12] 가 됩니다.

이런식으로 5개의 주사위를 고름으로서, 나오는 숫자의 총 길이는 5 x 5 x 5 x 5 x 5가 되구요,

$$ 5^5 = 3125 $$ 길이는 3125 입니다. A가 가진 숫자의 총 길이는 3125이고, B도 3125 이구요, 서로 비교해서 이긴 경우의 수를 찾는 다고 하면 3125의 3125제곱 입니다. 엄청 나게 큰 숫자가 나오기 때문에, 시간안에 문제를 풀 수 없습니다.

숫자의 길이를 줄여야만 이 문제를 시간안에 풀 수 있습니다.

2개의 주사위로 나올 수 있는 경우의 수로 돌아가 보겠습니다.

[2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12]

같은 숫자가 반복되는 것을 볼 수 있습니다. 따라서, 숫자를 적고, 이 숫자의 길이를 적는 방법으로 길이를 줄 일 수 있습니다.

2(1개), 3(2개), 4(3개), 5(4개), 6(5개), 7(6개) ... 이런식으로 표현하는 것 입니다.

이런 방법을 run-length encoding 이라고 합니다.

A가 4(3개) 있고, B는 3(2개) 있다고 가정하고, 이기는 수를 계산해 보겠습니다.

4 > 3 이기 때문에 A 가 이기는 것이 구요, 3개 x 2개 = 6개 해서, A가 6번 이기게 됩니다.

이런 방식으로 이기는 횟수를 계산하게 되면, 보다 빠르게 계산 할 수 있습니다.

이제 주사위를 고르는 방법을 알아보겠습니다. 최대 10개의 주사위가 있으므로, 5개까지 고를 수 있습니다. 그러면 주사위를 고르는 경우의 수는 조합으로는 아래와 같이 표시 할 수 있습니다.

$$ _{10}C_{5} = \frac{10!}{(10-5)!5!} = 252 $$

주사위의 조합은 252개 입니다. O(n)을 계산하기 편하게 300 으로 좀 크게 잡고, 대략 A 가 300가지 경우의 수, B 가 300가지 경우의 수가 있다고 볼 수 있습니다.