자바소스: http://bit.ly/3OWdATb
문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/118670
2024년 1월 29일 월요일
2024년 1월 26일 금요일
2024 KAKAO WINTER INTERNSHIP 산 모양 타일링
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/258705
파이썬 소스: https://bit.ly/4b8Gquj이 문제를 보면, 정삼각형 1개의 오른쪽에 계속 붙여 나가는 문제입니다.
이 때, 붙이는 종류가 2가지 입니다. 정삼각형 3개를 붙일 수도 있고, 정삼각형 2개를 붙일 수도 있습니다.
이런 문제를 풀 때는, 문제에서 요구하는 것을 한번에 해결하기 보다는 문제를 조금 간소화 시켜서 풀어본 뒤에, 전체 문제를 푸는 것을 추천드립니다.
이 문제에서는 정삼각형 2개 or 3개를 붙일 수 있기 때문에, 간소화 시킨 문제는 정삼각형 2개만을 붙인다고 생각해 보는 것입니다.
그러면 첫 시작은 정삼각형을 4개 붙여 놓은 아래 모양입니다. 바로 n = 0 일 때 라고 할 수 있습니다.
정삼각형과 사다리꼴을 사용해서 채우는 방법은 모두 3가지로 아래와 같습니다.
이것만 가지고는 문제를 푸는 힌트를 얻기가 어렵습니다.
삼각형 2개를 더 붙였을 때, 정삼각형과 사다리꼴을 사용해서 채우는 방법을 알아 보겠습니다.
전체 8가지 경우로 아래와 같습니다. n = 1 일 때 라고 할 수 있습니다.
이제 n = 0인 경우와 n = 1인 경우를 비교 하여, 점화식을 만들어야 이 문제를 풀 수 있습니다.
2개의 그룹으로 나눠서 n=0 3가지경우와, n=1 8가지 경우의 관련성을 알아보겠습니다.
우선 아래 f, g, h 는 \ 모양의 마름모로 끝나는 경우입니다. 모두 n=0 의 경우에 \ 모양의 마름모를 붙였 다는 것을 알 수 있습니다.
여기서 n=1 일 때, \ 마름모 끝나는 경우는 n=0 일 때 모든 경우의 수의 합과 같다는 것을 알 수 있습니다.
2차원 배열 dp를 선언하고, row값이 n, column 값이 1이 \ 마름모로 끝나는 경우라고 정의 한다면, 아래와 같이 점화식의 일부를 완성할 수 있습니다.
dp[n][1] = n-1 번째의 모든 경우의 수의 함
이와는 반대로, \ 마름모로 끝나지 않는 모든 경우, 즉 / 마름모로 끝나거나, 삼각형으로 끝나는 경우를 모아 보면 아래와 같습니다.
a 는 왼쪽 n=0 모양에서, 삼각형으로 채운 경우 입니다.
b 는 왼쪽 n=0 모양에서, / 마름모로 채운 경우 입니다.
c 는 왼쪽 n=0 모양에서, 삼각형으로 채운 경우 입니다.
d 는 왼쪽 n=0 모양에서, / 마름모로 채운 경우 입니다.
e 는 왼쪽 n=0 모양에서, \ 마름모로 끝나서, 삼각형으로 채운 경우입니다.
\ 마름모로 끝나지 않는 모든 경우, 즉 / 마름모로 끝나거나, 삼각형으로 끝나는 경우를 dp[n][0] 으로 정의 한다면 아래와 같이 점화식을 작성할 수 있습니다.
dp[1][0] = dp[0][0] * 2 + dp[0][1]
dp[n][0] 은 ‘\ 마름모로 끝나지 않는 모든 경우, 즉 / 마름모로 끝나거나, 삼각형으로 끝나는 경우’ 로 정의 하고, dp[n][1] 은 ‘\ 마름모로 끝나는 경우’ 로 정의 하였으므로, dp[n][0] dp[n][1]의 점화식은 아래와 같습니다.
dp[n][0] = dp[n-1][0] * 2 + dp[n-1][1]
dp[n][1] = dp[n-1][0] + dp[n-1][1]
위의 점화식을 사용해서 입출력 예#3 번을 풀어 보려면, dp[0]의 값을 아래와 같이 셋팅합니다.
dp: List[List[int]] = [[0, 0] for _ in range(n)]
MOD = 10007
dp[0][0] = 2
dp[0][1] = 1
for idx in range(1, n):
dp[idx][0] = dp[idx - 1][0] * 2 + dp[idx - 1][1]
dp[idx][1] = dp[idx - 1][0] + dp[idx - 1][1]
dp[idx][0] %= MOD
dp[idx][1] %= MOD
range()함수의 인자가, 1, n 인 것을 확인해주시구요, 매번 MOD 값의 나머지를 저장하는 해야 합니다. 뒤로 갈 수록 큰 숫자가 나오기 때문에, 매전 MOD 값의 나머지를 계산하지 않으면, 잘 못 된 결과를 얻을 수 있습니다.
이렇게 코딩한 후에, 마지막에 리턴한 answer 값은 아래와 같이 계산합니다.
answer = (dp[n - 1][0] + dp[n - 1][1]) % MOD
여기서도 마찬가지로, MOD 값의 나머지를 계산합니다. 이렇게 문제를 풀면 입출력 예#3
의 답 7704를 얻을 수 있습니다.
이제 tops[n] 이 0인 경우의 정답은 찾을 수 있으니, tops[n] 이 1인 경우를 고려해 보겠습니다.
tops[0] 이 1이라면, dp[0] 초기값도 달라지게 됩니다.
if tops[0] == 1:
dp[0][0] = 3
dp[0][1] = 1
else:
dp[0][0] = 2
dp[0][1] = 1
dp[0][0] 은 3이 됩니다. / 마름모, 삼각형으로 채우는 경우 이외에, 윗쪽으로 향하는 마름모 경우의 수가 생겼기 때문에 1증가한 3이 됩니다.
dp[idx][0] = dp[idx - 1][0] * 3 + dp[idx - 1][1] * 2
**dp[idx - 1][0]**을 계산하는 방식도 곱하기 2에서 곱하기 3으로 1 증가 합니다. 윗쪽으로 향하는 마름모의 경우의 수를 고려해서, 2에서 1증가한 3이 됩니다.
dp[idx - 1][1] 즉, 직전 단계에서 \ 마름모로 끝난 경우도, 곱하기 2를 해야 합니다. \마름모로 끝날 수도 있고, 윗쪽으로 향하는 마름모로 끝날 수도 있기 때문입니다.
2024년 1월 25일 목요일
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가지 경우의 수가 있다고 볼 수 있습니다.
300 x 300 은 90000 으로 그렇게 큰 숫자는 아닙니다. 하지만 여기에 주사위 숫자의 길이를 곱해야 합니다.
주사위 숫자의 길이는 알 수 없지만, run-length encoding 으로 길이를 줄였기 때문에 시간안에 문제를 풀 수 있을 것으로 예상해 봅니다.
피드 구독하기:
글 (Atom)