복습 정리 노트

백만년만에 문제 풀이 정리를 한다. 물론 시간 날 때마다 문제는 꾸준히 풀어오고 있다. 그동안 정리 안 한 것은 브론즈 문제들을 굳이 풀이를 정리하기에는 불필요하다고 느껴서였고, 가끔 약간의 메모가 필요한 문제들이 있으면 정리해보려고 한다. 백준 BOJ 8120번 : Coding of Permutations 문제 난이도 : Gold I 알고리즘 분류 : 세그먼트 트리 길이 N인 수열로 a_i = i번째 위치의 왼쪽에 있는 더 큰 수의 개수가 주어질 때, N에 대한 순열을 찾는 문제이다. 예를 들어 (0, 0, 1, 0, 2, 0, 4)가 주어진다면 (1, 5, 2, 6, 4, 7, 3)이 답인데 왜냐하면 1의 왼쪽에 더 큰 수가 0개, 5의 왼쪽에 더 큰 수가 0개, 2의 왼쪽에 더 큰 수가 1개, 6의..

백준 BOJ 1185번 : 유럽여행 문제 난이도 : Platinum IV 알고리즘 분류 : 최소 스패닝 트리 (MST) 트리 형태의 그래프가 주어지고, 한 지점에서 시작하여 어떤 노드와 간선을 지나갈 때의 비용이 모두 주어질 때, 최소 비용으로 모든 노드를 순회할 때 드는 최소 비용을 구하는 문제이다. 경로를 생각해보면, 시작점을 제외하고 어떤 경로든 지나갔다가 다시 돌아와야 하므로, 간선의 시작점 → 간선 → 간선의 끝 점 → 간선 순서로 반드시 지나가게 된다. 따라서 간선의 비용 자체를 (간선의 시작점의 비용 + 간선의 끝 점의 비용 + 간선의 비용 x 2)로 설정해주고, 여기에 시작점으로 설정할 최소 비용인 노드의 비용을 더해주면 된다. #include #define int long long usi..

과거에 풀어놨던 최대 유량 알고리즘 문제들의 풀이들이 더럽기도 하고 설명도 깔끔하지 못해서 다시 한 번 풀면서 풀이 코드만 비교적 간단하게 정리해보려고 합니다. 푸는 순서의 기준은 최대 유량 알고리즘에 속해 있는 문제들 중 푼 사람 수가 많은 문제부터 내림차순입니다. 각 문제의 풀이 코드는 문제 설명 바로 아래 접은 글에 정리되어 있습니다. 참고로 문제 풀이에 대한 간략한 설명은 있으나 최대 유량 알고리즘 자체에 대한 설명이나 코드에 대한 구체적인 작동 방식의 설명은 없습니다. 이 블로그 내 검색(지금 보시는 페이지 상단에 검색 창이 있습니다.)을 통해 문제 번호만 숫자로 입력하면 알고리즘과 코드에 대한 구체적인 설명이 정리되어 있습니다. 백준 BOJ 6086번 : 최대 유량 문제 난이도 : Platin..

길이가 N인 수열에서 등차수열 관계를 가지는 세 수를 뽑는 경우의 수는 어떻게 구할 수 있을까요? 당연히 N과 원소의 크기 a_i의 범위가 모두 크다면 풀이할 수 없겠지만, 특정 제한이 있다면 풀이할 수 있습니다. 이 포스트에서는 세 가지의 경우에 따라 풀이 방법을 다르게 하여 푸는 방법을 소개합니다. (참고로 이 문제들은 제가 나중에 따로 볼 일이 있을 것 같아 포스트를 분리하여 작성합니다.) 백준 BOJ 13558번 : 등차수열의 개수 문제 난이도 : Gold III 알고리즘 분류 : 브루트포스 (와 비슷한..) 길이가 10만 이하의 N이고 각 원소가 1 ~ 30,000 사이인 수열이 있을 때 a_j - a_i = a_k - a_j이고 i < j < k를 만족하는 순서쌍의 수를 구하는 문제입니다. 공..

백준 BOJ 14958번 : Rock Paper Scissors 문제 난이도 : Diamond V 알고리즘 분류 : FFT (고속 푸리에 변환) 배열이 2개가 주어지고, 각각의 배열의 값들이 가위바위보에 해당하는 Rock, Paper, Scissors라고 할 때, 아래의 배열이 이동하면서 매칭되는 칸끼리 가위바위보를 수행하여 위치에 따라 가장 많이 이길 수 있는 횟수를 구하는 문제입니다. 이 문제의 상황과 같이 배열과 배열을 일대일로 비교를 여러 번 해야하는 경우 FFT를 활용해볼 수 있습니다. 한 쪽의 벡터를 뒤집은 뒤 이산 합성곱을 수행해주면 항마다 일대일로 매칭되어 곱해진 값이 더해지므로, 이를 활용하기 위해 적절히 벡터의 값을 1 또는 0으로 세팅해주어야 합니다. 문제 상황에 대해 생각해보면 N칸..

백준 BOJ 13055번 : K-Inversions 문제 난이도 : Diamond V 알고리즘 분류 : FFT (고속 푸리에 변환) B가 A보다 먼저 나오는 쌍을 inversion이라고 할 때, B와 A 사이의 거리가 K일 때 그 쌍을 K-Inversion이라고 정의합시다. A와 B로만 이루어진 문자열에 대해 0 ~ N-1사이의 모든 K-inversion의 수를 구하는 문제입니다. 예를 들어 문제에서 예시로 든 BABA를 가지고 설명하자면, 앞의 BA와 뒤의 BA는 모두 B → A 순서대로 나타나며 B와 A 사이의 거리가 1이므로 1-inversion이고, 이는 총 2회 나옵니다. 그리고 맨 앞의 B와 맨 뒤의 A 역시 inversion에 해당되고, 두 문자 사이의 거리는 3이므로 3-inversion은..

백준 BOJ 13575번 : 보석 가게 문제 난이도 : Platinum I 알고리즘 분류 : FFT (고속 푸리에 변환), 분할 정복을 이용한 거듭 제곱 N개의 값 중에서 K개를 중복을 허용하여 선택할 때, 얻어질 수 있는 합의 가짓수를 구하는 문제입니다. 예를 들어 N = 3, 주어진 배열 A = { 1, 2, 3 }, K = 2라고 할 때 1 + 1 = 2, 1 + 2 = 3, 1 + 3 = 2 + 2 = 4, 2 + 3 = 5로 총 4가지 합을 얻을 수 있어서 답은 4가 됩니다. (문제 조건에 따라 다른 조합으로 같은 합을 얻더라도 하나의 합으로 카운트 해주어야 합니다.) FFT를 이용하면 두 집합의 합으로 얻어질 수 있는 값들의 종류와 그 가짓수를 구할 수 있으므로, FFT를 활용하여 풀이하는 방..

백준 BOJ 13279번 : 곱의 합 쿼리 문제 난이도 : Platinum IV (FFT로 해결할 시 체감 난이도 Platinum I, 그러나 O(N^2) 풀이가 통과되어 하향 조정) 알고리즘 분류 : FFT (고속 푸리에 변환) N개의 수로 이루어진 수열 A에서, 쿼리 K가 주어지면 A의 길이 K인 부분 수열들의 곱의 합을 구하여 출력하는 문제입니다. 이 때 쿼리 문제이므로 쿼리의 수는 최대 N개가 주어질 수 있습니다. 예를 들어 N = 3이고 A = { 1, 2, 3 }이라면, K = 2가 주어졌을 때 길이가 2인 부분 수열은 { 1, 2 }, { 1, 3 }, { 2, 3 }이 있으므로 이들의 곱의 합을 구하면 11이 됩니다. 문제 조건을 보면 쿼리는 최대 N개 들어올 수 있고 이는 결국 1 ~ N..

백준 BOJ 20176번 : Needle 문제 난이도 : Platinum I 알고리즘 분류 : FFT (고속 푸리에 변환) 3개의 직선이 있고 3개의 직선 위에 점들의 좌표가 주어질 때 서로 다른 직선 위의 3개의 점이 일직선에 있는 쌍이 몇 개나 있는지를 구하는 문제입니다. 입력은 3개의 직선에 대해 직선 위의 점의 수 N, 점의 x 좌표 N개가 순서대로 주어집니다. 2 1 2 3 0 1 2 2 2 3 예를 들어 입력이 위와 같이 주어졌다고 가정하면, 맨 위에서 좌표 1, 중간에서 좌표 2, 맨 아래에서 좌표 3을 선택하면 하나의 직선을 만들 수 있습니다. 또한 맨 위에서 좌표 2, 중간에서 좌표 2, 맨 아래에서 좌표 2를 선택해도 역시 직선 하나를 만들 수 있습니다. 따라서 위의 입력에 대한 답은 ..

이 포스트에서는 지난 포스트에서 다룬 고속 푸리에 변환(FFT, Fast Fourier Transform) 알고리즘을 직접 백준 BOJ 문제들에 응용하는 풀이들에 대해 다루어볼 것입니다. 사실 저는 아직 FFT의 응용에 익숙하지 않기 때문에 쉬운 문제들부터 풀어보도록 하겠습니다. 백준 BOJ 1067번 : 이동 문제 난이도 : Platinum I 알고리즘 분류 : 고속 푸리에 변환 (FFT) 길이 N인 수열 X와 Y가 있을 때, 수열들을 적당히 순환시켜 순서를 바꾼 뒤 문제에서 주어진 식 S를 계산했을 때 그 최댓값을 구하는 문제입니다. 식 S의 꼴을 보면 원소 순서대로 곱하는, 즉 내적 형태의 식을 가지고 있습니다. 따라서 FFT에서 수행되는 이산 합성 곱의 형태를 적절히 변형하면 문제에서 요구하는 식..