알고리즘 (364) 썸네일형 리스트형 [Befunge] 2380번 Star https://www.acmicpc.net/problem/2380 24/11/12 오랜만에 파이썬 외의 다른 언어로 풀어보는 문제다. Isolang 중 하나인 Befunge언어를 사용하여 주어진 그림을 출력하면 되는 문제다. 문제 접근 방식: 문제는 간단하다. 주어진 Output을 비펀지언어로 구현하면 끝. 처음에는 귀찮아서 GPT한테 맡겼더니 해결을 못했다. 모델을 바꿔서 해도 해결이 안되길래, GPT한테 해당 언어의 주요 기능을 알려달라고 했다. 비펀지는 2차원 그리드 위에서 실행되는 스택기반 언어로, 공백이 더 들어가거나 탭이 잘못들어가면 이상하게 꼬인다. 주요기능은 다음과 같다. 1. 숫자(0~9)해당 숫자를 스택에 넣는다. 2. 산술연산자(+,-,*,/,%)스택에 들어있는 두 숫자를 pop하.. [Python] 32645번 동까뚱뽭 게임 https://www.acmicpc.net/problem/32645 24/11/11 간단한 게임이론 + 트리 DP문제이다. 문제 접근 방식: DP상태 식을 다음과 같이 정의해보자. DP[i] = $i$번째 노드에서 게임을 진행할 때 누가 이기는 지에 대한 여부 DP[i] = 0이라면 후공이 이긴다고 하고, 1이라면 선공이 이긴다고 하자. 뭐, 게임이론 많이 한 사람들이라면 스프라그-그런디로 생각해서 mex때릴 수도 있는데, 사실 게임이 하나 뿐이라서 선후공 승패 여부만 따지면 되기 때문에 간단한 게임 DP로도 풀린다. $i$번째 노드에서 밑으로 갈 수 있는 노드를 below라고 한다면, DP[below]가 모두 1이라면, 즉, 선공이 이기는 노드라면 현재 노드는 후공이 이기는 노드(즉, 선공이 지는 .. [Python] 32299번 게임을 만들어요 https://www.acmicpc.net/problem/32299 24/11/10 전형적인 게임이론 문제다. 문제 접근 방식: $N=3$인 경우를 제외하면 항상 후공이 이긴다. 그 이유는 게임 판을 도넛 모양으로 분리하면, 한 도넛에서 다른 도넛으로 움직일 때마다 선공과 후공의 유리한 정도가 달라지는데, 다른 도넛으로 움직일 때 후공이 유리하다면 후공은 그냥 그 방향으로 움직이면 되고, 다른 도넛으로 움직일 때 선공이 유리하다면, 후공이 현재 도넛에서 빙빙 돌면서 선공이 다른 도넛으로 넘어가도록 만들 수 있기 때문이다. 게임이론에서 자주 나오는 테크닉인데, 핵심은 후공이 항상 선공이 불리하도록 게임판을 "조정"할 수 있다는 것이 핵심이다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다... [Python] 4354번 문자열 제곱 https://www.acmicpc.net/problem/4354 24/09/26 KMP로 유명한 문제다. 근데 이 문제는 KMP로 안풀어도 된다. 사실 이 방법이 더 쉽다. 문제 접근 방식: 엥 그러면 어떻게 접근하는 거야, 라고 생각하겠지만, 그냥 나이브하게 풀린다. 문자열의 길이를 $N$이라고 하면, $N$의 약수가 반복되는 문자열의 길이가 될 수 있다. 따라서 $N$의 약수 $i$에 대해서, 기존 문자열 $S$를 슬라이싱한 부분 문자열, $S[:i]$가 $S$에서 몇 번 반복되는지 count함수를 통해 확인한다. 그 반복 횟수*부분문자열의 길이가 원래 문자열의 길이 $N$이 된다면 바로 종료하면 된다.(가장 짧은 부분 문자열을 찾는 것이므로) 그렇다면 이게 왜 되는지 궁금할텐데, 파이썬에서 s.. [Python] 32518번 대충 블록에서 영혼 탈출시키는 게임 https://www.acmicpc.net/problem/32518 24/11/08 간단한 탑다운 DP다. 바텀업으로는 해결할 수 없다. 문제 접근 방식: 처음에는 $N$의 제한이 $10^{18}$인 것을 보고 DP가 아니라 하나의 완성된 수식으로 나올 줄 알고 100까지의 바텀업 DP를 돌렸다. 뚜렷한 규칙이 보이지 않아서, 수학적으로 해결하는 것은 그만두고, 다른 해결방법이 있는지 모색하기 위해 어떤 경우에 최댓값이 나오고, 그때 분할되는 경우가 어떤 경우인지를 모두 찾는 코드를 작성했다. $N-2$가 3으로 나눠진다면, $((N-2)//3, (N-2)//3, (N-2)//3)$과 같이 분할된다. 예를 들어, 8과 같은 경우, 들어내는 블록을 기준으로 3개의 체인이 나오는데, 각 체인의 길이는 .. [Python] 32387번 충전하기 https://www.acmicpc.net/problem/32387 24/10/06 KCPC 당시, 파이썬으로 검수했던 문제다. 다양한 풀이가 있어서 나름 연습해보기 적절한 문제라고 생각한다. 문제 접근 방식: 문제의 요구 사항은 다음과 같다. 크기가 $N$인 Bool 배열 $A$가 주어지고, 두 종류의 쿼리가 주어진다. 쿼리의 개수는 최대 $10^6$개이며, 배열의 최대 크기는 $10^6$이다. 또한, 배열의 초기 상태는 모두 False로 초기화되어있는 상황이다. 1번 쿼리는 인덱스 $i$가 주어진다. $i$보다 크거나 같은 인덱스 $k$중에서, $A[k]$ = False로 되어있는 가장 작은 인덱스를 True로 바꾸는 것이다. 만약 이것이 불가능하다면 $-1$을 출력한다. 2번 쿼리는 인덱스 $.. [랜덤 마라톤] 랜덤 마라톤 코스 16 랜덤 마라톤 문제를 한두 문제 풀어본 적은 있는데, 제대로 다 풀기 시작한 것은 이번이 처음인 것 같아서 정리해서 올려본다. A. Divide the Cash해결 : 24/09/18전체 금액을 문제에서 주어진 비율대로 비례 배분하는 문제. 간단하다.# 25858번 Divide the Cash# 사칙연산N, D = map(int, input().split())A = list(int(input()) for _ in range(N))T = sum(A)for i in A: print(i*D//T) B. Going to the Movies해결 : 24/09/18제한 $C$를 넘지 않으면서 합을 최대로 만드는 문제. 제한이 커지면 냅색으로 해결할 수 있을 것 같다.여기에서는 $N$이 최대 $16$이어서, 브루.. [Python] 32228번 등차수열 만들기 https://www.acmicpc.net/problem/32228 24/09/15 맷코컵 당시 검수했던 문제 중 하나이다. 알면 보자마자 떠오르는 낚시 문제다. 문제 접근 방식: 문제에서는 주저리 주저리 적혀져 있는데, 오일러 파이 함수의 값을 출력하면 끝이다. 그러면, 결론이 왜 그렇게 나오는지에 대해 알아야 한다. 문제에서 주어진 것 처럼 mod $M$에서의 등차수열을 직접 구하는 방식으로 $K$값을 짜내려고 한다면 곤란하다. $N$의 제한과 $M$의 제한이 꽤나 크기 때문이다. $A_i$와 $M$이 서로소라는 조건, 모두 같은 $K$제곱을 하여 $A_{i}^{K}$로 만들고 mod $M$과 엮는다는 점을 유의깊게 생각하면 쉽게 파악할 수 있다. 이 $K$의 값이 $\varphi (M)$이 된다.. 이전 1 2 3 4 5 6 7 ··· 46 다음
