알고리즘/백준 문제 풀이 (338) 썸네일형 리스트형 [Python] 32612번 Expected Eyes https://www.acmicpc.net/problem/32612 24/11/15 두 가지 방법으로 풀 수 있다. 둘다 소개해보려고 한다. 문제 접근 방식: 1. 파이썬의 itertools모듈의 product함수를 이용한다. 직접 모든 가능한 경우의 수를 조사하면서 기댓값을 구한다. 이 접근방식의 시복도는 최대 $\mathcal{O}(8^8)$이다. 따라서 파이썬3로는 통과하기 힘들고 파이파이로 하면 통과된다. 2. 기댓값의 선형성 이용 전체 기댓값은 선형성에 의해 각 주사위의 기댓값의 합과 같다. 이를 이용하면 한줄로 코딩할 수 있다.아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.더보기# 32612번 Expected Eyes# 1. 나이브한 반복 풀이.. [Python] 1178번 간선 추가 https://www.acmicpc.net/problem/1178 24/09/02 몇 번 잘못된 접근을 한 문제였기 때문에 어떻게 잘못된 접근을 했는지를 중심으로 적어보겠다. 문제 접근 방식: 먼저 한붓그리기라는 점에서 오일러 경로 문제임을 파악했다. 오일러 경로가 존재하려면 그래프 정점의 차수를 모두 센 다음에, 차수가 홀수인 정점이 0개 혹은 2개 있어야 한다.이러한 사실을 기반으로, 처음에는 다음과 같은 접근 방식을 세웠다. 먼저, 한붓그리기를 하려면 모든 정점이 서로 이어져 있어야 한다. 따라서, 정점의 차수가 0이라면 그 누구와도 이어져 있지 않으므로, 이것을 고려해주었다. 그리고 오일러 경로가 존재하려면 차수가 홀수인 정점이 0개 혹은 2개 있어야 한다는 사실에 기반하여, 정점의 차수가 홀.. [Python] 2418번 단어 격자 https://www.acmicpc.net/problem/2418 24/11/14 예전에 북마크 해뒀다가 지금 해결한 문제다. 해결 방식은 어제 해결했던 내리막길 문제와 유사하다. 문제 접근 방식: 탑다운 DP로 접근했다. DP상태는 다음과 같이 정의했다. DP[i][j][k] = 지금까지 단어에서 k번째 글자까지 읽었고, (i, j)에 위치한 글자가 단어에서 k번째 글자일 때, 단어를 읽을 수 있는 방법의 수 이후, 모든 격자 칸을 조사하며, 이 격자 칸에 적힌 글자가 단어의 첫 글자와 일치한다면, 즉, (i, j)에 위치한 글자가 단어의 0번째 글자라면 DP[i][j][0] = 1로 초기화 해주었다. 이후 dfs를 통해 주변 8방향을 조사하며 구현했다. 우리가 원하는 값은 단어의 마지막 글자와 (.. [Python] 1520번 내리막 길 https://www.acmicpc.net/problem/1520 24/11/13 무난한 DP이다. 처음에는 바텀업으로 생각했으나, 잘 생각나지 않아서 탑다운으로 짰다. 문제 접근 방식: DP식을 다음과 같이 정의하자. DP[i][j] = $(i, j)$번째 칸에 왔을 때 항상 내리막 길로만 오는 경우의 수. 우리의 목적은 $DP[N-1][M-1]$의 값을 구하는 것이다. 또한, $DP[0][0] = 1$임을 알고 있다. 내리막 길로 간다는 것은 현재 칸보다 이전의 칸에 쓰여있는 숫자가 더 크다는 뜻이다. 따라서, 기본적으로 현재 칸을 둘러싸고 있는 4개의 주변 칸, 즉, 이전의 칸에 쓰여있는 숫자가 더 크다면, 그 칸을 통해 현재 칸으로 올 수 있다. 따라서, 4개의 주변 칸에 대해서 DP값을 찾아.. [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.. 이전 1 2 3 4 5 6 7 ··· 43 다음