글 (489) 썸네일형 리스트형 [C++] 17104번 골드바흐 파티션 2 https://www.acmicpc.net/problem/17104 26/01/31 르모앙의 추측 문제를 약간 변형시킨 문제이다. 문제 접근 방식: 짝수 $N$을 두 소수 $p+q$로 나타내는 경우의 수를 세는 문제다.얼핏보면 르모앙의 추측 문제를 해결했을 때와 똑같은 방법으로 해결할 수 있을 것이라고 생각할 수 있겠지만, 문제는 $p+q$와 $q+p$를 같은 경우의 수로 취급한다는 점이다.Sieve를 곱한 결과는 $(p, q)$와 $(q, p)$를 다른 경우의 수로 취급한다.따라서, 기본적으로 나온 결과에서 중복된 경우의 수를 빼줘야만 한다.$N \neq 2p$인 경우, $p+q = N$을 만족시키는 $(p, q)$ 순서 쌍은 항상 $p\neq q$이다.즉, Sieve끼리 곱한 결과(중복을 포함한 .. [C++] 17134번 르모앙의 추측 https://www.acmicpc.net/problem/17134 26/01/30 Golf Bot문제의 아이디어를 사용하면 쉽게 해결할 수 있다. 문제 접근 방식: 홀수 소수를 $p$, 짝수 세미소수를 $q$라고 한다면 $p+q = N$을 만족하는 경우의 수를 구하는 문제이다.결국 Golf Bot문제와 동일한 아이디어로 풀리는데, $A[p] = 1$인 배열 $A$와 $B[q] = 1$인 배열 $B$를 만들어서, 두 배열 $A, B$를 FFT로 곱하면 된다.배열 $A$는 에라토스테네스의 체를 통해 구할 수 있고, 그렇게 구한 $A$를 통해 $B$또한 만들 수 있다.아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.더보기// 17134번 르모앙의 추측// FF.. [C++] 20176번 Needle https://www.acmicpc.net/problem/20176 26/02/01 Golf Bot문제와 동일한 아이디어로 해결할 수 있다. 문제 접근 방식: 문제의 요구 사항을 잘 읽어보면, 결국 바늘이 3개의 벽을 통과하기 위해선 벽의 구멍의 위치가 서로 등차수열을 이루고 있어야 함을 확인할 수 있다.즉, 벽 구멍의 위치를 맨 윗 벽부터 순서대로 $x_{1}, x_{2}, x_{3}$이라고 하면, $x_{1}+x_{3}=2x_{2}$를 만족시키는 경우의 수를 찾는 문제로 바뀐다.결국 두 수의 합을 물어보는 문제로 바뀌게 된다. 그리고 이는 10531번 Golf Bot문제를 해결했을 때의 아이디어와 동일하다고 할 수 있다.하지만 여기서는 주어지는 $x_{i}$들이 음수가 될 수 있다.이를 막기 위.. [C++] 10531번 Golf Bot https://www.acmicpc.net/problem/10531 26/01/29 FFT의 기본 활용 방법을 배울 수 있는 문제이다. 해당 문제를 잘 익히면 이후의 FFT 활용 문제들도 해당 아이디어를 사용하여 해결할 수 있다. 문제 접근 방식: 골프 봇이 칠 수 있는 거리들 $k_{i}$가 크기 $N$짜리 리스트로 주어지고, 각 코스의 거리들 $d_{j}$가 크기 $M$짜리 리스트로 주어진다.문제에서 요구하는 것은 골프 봇이 최대 $2$번까지 칠 수 있을 때, 몇 개의 코스를 골프 봇이 정복할 수 있냐를 물어보고 있다.골프 봇이 $1$번만 칠 때 각 코스를 정복할 수 있는지의 여부는 금방 판별할 수 있다.문제는 골프 봇이 $2$번을 칠 때 각 코스를 정복할 수 있는지의 여부이다.수학적으로 문제를 .. [C++] 25456번 궁금한 시프트 https://www.acmicpc.net/problem/25456 26/02/11 1067번 이동 문제와 매우 유사하다. 문제 접근 방식: 문제에서 주어진 코드를 잘 보면, 두 문자열 $S, T$를 각각 $s, t$만큼 offset을 두고, $S[(s+i)\text{mod }N] = T[(t+i)\text{mod }N] = 1$인 경우 cnt값에 1을 더해주는 코드이다.문제의 요구사항은 cnt의 최댓값을 찾는 것인데, 결국 이것도 1067번 이동 문제와 똑같은 흐름으로 흘러간다.크기가 $N$으로 같은 두 배열이 주어졌을 때의 최댓값을 구하는 것인데, 여기선 문자열로 주어진 것만 다르다.이동문제와 마찬가지로, 배열 $S$를 2배 길이로 만들어주고, 배열 $T$를 뒤집어서 FFT한번 수행하면 충분하다... [C++] 1067번 이동 https://www.acmicpc.net/problem/1067 26/01/27 FFT/NTT 기초문제이다. 이 문제의 아이디어를 잘 익혀두면 관련된 문제들도 쉽게 해결할 수 있을 것이다. 문제 접근 방식: 고속 푸리에 변환의 정의를 잘 생각해보자.PS에서 사용되는 고속 푸리에 변환은 엄밀하게 따지면 이산 푸리에 변환(DFT)이다.이는 어떤 두 다항식 $A(x), B(x)$가 주어져 있을 때, 두 다항식의 곱 $A(x)B(x)$를 $\mathcal{O}(N^{2})$이 아닌 $\mathcal{O}(N\log N)$의 시간 복잡도로 빠르게 구할 수 있는 알고리즘으로, 분할 정복의 아이디어에 기반을 두고 있다.두 다항식을 곱한 다항식 $C(x)$의 $x^{k}$의 계수 $\displaystyle c_.. [26/02/13] 기습 발행 최근이라고 하긴 좀 그렇지만 몇개월 전부터 글 몇개를 제외하고 모두 회고록을 보호글처리했다. 개인적인 사생활이 너무 드러나는 것 같아서 다 보호글로 지정했고, 앞으로 이 티스토리 블로그는 백준 문제풀이 + 공부용 블로그로 남길 생각이다.(대회 후기는 그대로 남길 것이다.) 개인적인 글을 남기고 싶긴 한데... 너무 많이 검색되는건 싫다...(아이러니하게도) 보호글 처리된 내용을 보고싶다고 하면 아래 글에 비밀댓글로 남겨주길 바란다.(적어도 누가 보는지는 알고싶다) [Python] 1165번 단어퍼즐 https://www.acmicpc.net/problem/1165 26/01/06 파이썬의 lzma라이브러리 사용법을 안다면 난이도에 비해 비교적 쉽게 해결할 수 있다. 문제 접근 방식: 먼저 어떻게든 단어 목록을 전처리로 하나 만들어놓는다면 단순한 백트래킹 문제가 된다. 당연히 단어 목록을 전부 복붙하면 바이트가 너무 커진다. 이제 전처리로 단어 목록을 "압축"하는 법을 알아보자. 나의 접근 방식은 다음과 같다. 1. 먼저 단어 리스트들을 쭉 봤다.AARGHAARONABABAABACKABANDONABANDONEDABANDONINGABANDONMENTABATEMENTABBERLEY ...사전 순으로 정렬이 되어 있음을 확인했다. 2. 이 리스트를 그대로 lzma라이브러리로 압축 후, readable한.. 이전 1 2 3 4 ··· 62 다음
