파이썬 소스: http://bit.ly/3zJ8vH3
문제 링크: http://bit.ly/3mkbhzu
2024년 1월 28일 일요일
2024 KAKAO WINTER INTERNSHIP n + 1 카드게임
문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/258707
이 문제를 풀기 위해서, 매 라운드 마다 일어 나는 일을 정리해 보겠습니다.
- 카드 뭉치에서 2장씩 뽑 습니다.
- 코인으로 카드를 1 또는 2장 교환할 수도 있고, 안할 수도 있습니다.
- 2장의 카드에 적힌 수의 합이 n+1 이 되도록 카드 두장을 냅니다.
1번, 2번을 모두 할수 있어야 다음 라운드로 진행합니다.
2번의 조건과 3번의 조건이 문제의 진행에 서로 영향을 준다고 생각하게 되면, 이문제를 매우 복잡하게 접근해서, 문제를 풀 수 없는 경우가 많을 것 같습니다.
이 문제를 단순하게 만들어주는 아래 조건을 잘 활용해야 합니다.
cards의 원소는 중복되지 않습니다.
그러면 위의 조건을 고려해서, n+1 이 되는 2개의 카드를 선택하는 방법을 알아 보겠습니다.
a 카드 + b 카드 = n + 1 입니다.
따라서, n + 1 - a = b 카드에는 중복이 없기 때문에, b 카드를 가지고 있지 않다면, a 카드를 낼 수 있는 경우는 없습니다.
따라서, 루프 1개로, a, b 카드를 고를 수 있습니다.
for card1 in my_cards:
if N + 1 - card1 in my_cards:
#2개의 카드를 찾았습니다,
이제 가장 고민되는 부분인 코인으로 카드를 받아야 하나? 말아야 하나? 이 부분을 알아보겠습니다.
매 라운드 마다, 카드를 안받는 경우, 첫번째 카드를 받는 경우, 두번째 카드를 받는 경우, 카드를 2개 받는 경우 이렇게 4개의 분기를 만들게 되면, 대충 계산해도 아래와 같이 엄청 나게 큰 숫자가 나오게 됩니다. 카드의 최대 숫자가 1000임으로 모든 경우의 수는 대략 아래와 같습니다.
$$ 4^{(1000/2)} = 4^{500} $$
4의 5제곱이 1024 인대, 4의 500 제곱이면, 21억이나 10억 보다 매우 큰 숫자 입니다.
즉, 이문제를 시간안에 풀기 위해서는, 카드를 받는 경우의 수를 분기하지 않고, 문제를 풀어야 합니다.
분기를 하지 않으려면, 아래 4가지 경우를 한번에 처리할 수 있는 방법을 고민해 봐야 합니다.
- 카드를 안받는 경우
- 첫번째 카드를 받는 경우
- 두번째 카드를 받는 경우
- 카드를 2개 받는 경우
카드를 받는다 안 받는다 이거를 꼭 매 라운드에 결정을 해야 되는가? 라는 의문가질 수 있습니다.
카드를 매라운드에서 버리지 않고, 어딘가에 모아 둔다면 나중에 카드가 필요할 때, 이전 라운드에서 카드를 뽑은 것으로 치고, 카드가 필요한 라운드에 가서, 모아둔 곳에서 카드를 받아 올 때, 코인을 소모하는 것입니다.
이렇게 하면 문제의 규칙을 어기지 않고, 규칙을 약간 변형해서 아래와 같이 문제를 푸는 것이 가능합니다.
- 카드 뭉치에서 항상 2장을 뽑아서, available_cards 에 넣어 둡니다.
- 2장의 카드에 적힌 수의 합이 n+1 이 되도록 카드 두장을 냅니다.
- 카드 두장을 낼 수 없는 상황이 생기면
- 코인이 1이상인 경우에, 내가 가지고 있는 카드에서 1장을 선택하고, available_cards 카드에서 1장을 선택하여 n+1이 되는 카드 2장을 냅니다. 코인이 1개 감소합니다.
- 코인이 2개 이상인 경우에, available_cards 에서 n+1이 되는 카드 2장을 선택합니다. 코인이 2개 감소합니다.
위와 같이 문제를 접근하면, 1000/2 횟수 안에 문제를 풀 수 있습니다.
$$ 1000 / 2 = 500 $$
코데풀 유튜브 구독 부탁드립니다.
https://www.youtube.com/@codapul
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일 목요일
[22주차 1월 28일] 코데풀 유튜브 채널과 함께하는, 코딩테스트 준비 스터디 문제
https://www.youtube.com/@codapul
코딩테스트문제, 알고리즘문제 함께 풀어보는, 코데풀 채널입니다.
궁금한 내용은 여기로 메일 주세요 → coding.data.pul@gmail.com
스터디에서 알고리즘 문제 함께 풀어보실 분들 여기로 → https://cafe.naver.com/dremdeveloper
코데풀 유튜브 채널과 함께하는, 코딩 테스트 준비 스터디 입니다.
일요일 8시에 모여서 문제 풀이,토론 하구요, 1분만 더 받습니다.
참여하실분은 요기로 메일 주세요 -> coding.data.pul@gmail.com
leetcode.com 543. Diameter of Binary Tree
https://leetcode.com/problems/diameter-of-binary-tree/description/
파이썬 소스: https://bit.ly/47MHvFC
leetcode.com 110. Balanced Binary Tree
https://leetcode.com/problems/balanced-binary-tree/description/
파이썬 소스: https://bit.ly/46Qefgc
leetcode.com 1448. Count Good Nodes in Binary Tree
https://leetcode.com/problems/count-good-nodes-in-binary-tree/description/
파이썬 소스: https://bit.ly/472Orh7
leetcode.com 98. Validate Binary Search Tree
https://leetcode.com/problems/validate-binary-search-tree/description/
파이썬 소스: https://bit.ly/4aPKrDU
leetcode.com 124. Binary Tree Maximum Path Sum
https://leetcode.com/problems/binary-tree-maximum-path-sum/description/
파이썬 소스: https://bit.ly/47v7MYm
2024 KAKAO WINTER INTERNSHIP 도넛과 막대 그래프
https://school.programmers.co.kr/learn/courses/30/lessons/258711
피드 구독하기:
글 (Atom)