복습 정리 노트

백준 BOJ 2934번 : LRH 식물 문제 난이도 : Platinum IV 알고리즘 분류 : 느리게 갱신되는 세그먼트 트리 (Lazy Propagation of Segment Tree) 매일 높이가 1씩 높아지는 선분들을 위와 같이 그린다고 할 때, 매일 발생하는 새로운 교차점의 수를 구하는 문제입니다. 이 때 중요한 점은 두 선분이 완전히 교차하지 않거나 이미 교차가 발생했던 지점은 교차점으로 세지 않는다는 것입니다. 상황을 바꾸어 생각해보면, 매 쿼리마다 L ~ R 구간에 높이가 1인 블럭들을 쌓고, 이 때 L 지점과 R 지점의 높이를 구하면 어느 정도 비슷하게 해결이 될 것 같습니다. 그런데 문제는 위에서 말한 두 선분이 완전히 교차하지 않는 지점과 교차가 발생했던 지점의 처리입니다. 먼저 두 선..

백준 BOJ 12844번 : XOR 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net 문제 난이도 : Platinum III 알고리즘 분류 : 느리게 갱신되는 세그먼트 트리 (Lazy Propagation of Segment Tree) 느리게 갱신되는 세그먼트 트리 문제답게 역시 구간 업데이트 + 구간 대푯값 구하기 쿼리 문제입니다. 1번 쿼리에 대해서는 특정 구간의 모든 원소들에 대해 어떤 값을 XOR 하여 업데이트 해주어야 합니다. 2번 쿼리에 대해서는 특정..

백준 BOJ 16975번 : 수열과 쿼리 21 16975번: 수열과 쿼리 21 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다. www.acmicpc.net 문제 난이도 : Platinum IV 알고리즘 분류 : 느리게 갱신되는 세그먼트 트리 (Lazy Propagation of Segment Tree) 1번 쿼리에 대해서는 구간의 모든 원소에 특정 값을 더해주고, 2번 쿼리에 대해서는 특정 주소의 원소를 출력해야한다고 할 때 최대 10만개의 쿼리를 처리하는 문제입니다. (참고로 이 문제는 1번 쿼리는 구간 쿼리이지만 2번 쿼리는 구간에 대한 쿼리가 아..

백준 BOJ 1395번 : 스위치 문제 난이도 : Platinum III 알고리즘 분류 : 느리게 갱신되는 세그먼트 트리 (Lazy Propagation of Segment Tree) 0번 쿼리에 대해서는 특정 구간의 모든 스위치를 toggle 해주고, 1번 쿼리에 대해서는 특정 구간의 스위치 중 켜져있는 스위치의 개수를 출력하는 문제입니다. 즉, 구간에 대한 업데이트와 구간에 대한 대푯값을 구하는 쿼리를 모두 수행하는 문제이므로 느리게 갱신되는 세그먼트 트리를 활용하여 문제를 풀이해야 합니다. #include #define int long long using namespace std; vector u, w; // u : tree, w : lazy void lazy(int n, int b, int e) ..

백준에서 나름 재미있게 푼 문제가 있어서 정리해봅니다. "런타임 전의 전처리"와 "구성적" 태그가 둘 다 달려있는 문제였는데, 각 태그는 다음과 같은 조건에 의해 분류됩니다. 런타임 전의 전처리 : 제출한 프로그램이 작동하면서 문제를 푸는 것 외에, 풀이를 얻기 위해 미리 다른 프로그램을 작성하여 계산하는 방식으로 다른 전략을 취하여 푸는 문제입니다. 15698번: Uncrossed Knight’s Tour A well-known puzzle is to “tour” all the squares of an 8 × 8 chessboard using a knight, which is a piece that can move only by jumping one square in one direction and t..

제곱근 분할법을 이용하여 쿼리들을 처리하는 문제들을 풀이해봅시다. 참고로 다음에 다룰 두 문제는 쿼리의 순서, 변수의 범위만 다르고 풀이 방법은 거의 동일한 문제입니다. (시간 제한의 차이가 존재하긴 합니다.) 백준 BOJ 14504번 : 수열과 쿼리 18 위와 같이 특정 원소를 바꾸거나, 주어진 구간에서 특정 값보다 큰 원소의 개수를 구하는 쿼리들을 처리하는 문제입니다. 원소의 개수와 쿼리의 개수 모두 10만이므로, O(N^2)에는 당연히 풀이가 불가능합니다. 제곱근 분할법(Square-root Decomposition)을 사용하면 O(M√N log √N) 시간에 모든 쿼리를 처리할 수 있으므로 대략 1억번 정도의 연산으로 풀이할 수 있고, C++은 연산 속도가 빠른 편이므로 제한 시간 2초 안에 충분..

이 포스트에서는 Problem Solving에서 가끔 등장하는 인터랙티브 문제에 대해 설명하고 푸는 방법을 간단하게 정리해보겠습니다. 인터랙티브(Interactive) 문제란 제출 코드에 따라 입력 데이터가 결정되는 문제입니다. 이름 그대로 채점 프로그램과의 상호 소통하는 방식을 통해 풀이해야 하는 문제 유형이라고 할 수 있습니다. 예를 들어 여러분이 다른 사람과 스무고개를 한다고 가정하면 상대방은 여러분이 어떤 질문을 하느냐에 따라 다른 답을 할 것이고, 그렇게 되면 얻은 답을 기반으로 내용을 유추하여 최종 답을 찾아야 합니다. 이러한 방식으로 문제를 풀이하는 것이 인터랙티브 문제라고 보시면 됩니다. 설명만으로는 이해하기 부족하기 때문에 인터랙티브 문제를 하나 풀이해보겠습니다. 적절한 난이도로 백준 O..

백준 BOJ 2098번 : 외판원 순회 Solved.ac 난이도 : Gold I 알고리즘 분류 : 비트필드를 이용한 다이나믹 프로그래밍 외판원 문제란, 도시의 수 N(≤ 16)에 대해 도시에서 도시로 가는 비용들이 주어질 때, 모든 도시를 순회하고 돌아오는데 필요한 최소 비용을 구하는 문제입니다. dp를 이용하여 이 문제를 해결하기 위해서는, 각 도시에 대한 방문 여부를 저장해야 합니다. 따라서 메모리를 효율적으로 사용하기 위해 비트필드를 사용한 다이나믹 프로그래밍으로 문제를 해결해야 합니다. dp[i][j]를 현재 도시가 i이고 j의 방문 상태를 가질 때, 최소 비용으로 정의합니다. 이 때 방문 상태 j란 각 비트에 대해 해당 비트가 1이라면 해당 번호의 도시를 방문한 것이고 0이라면 방문하지 않은 것..

백준 BOJ 1963번 : 소수 경로 Solved.ac 난이도 : Gold IV 알고리즘 분류 : 에라토스테네스의 체, BFS 주어진 네 자리 소수 A를 다른 소수 B로 바꿀 때, 한 자리씩 바꾸는 동시에 소수임을 유지하면서 B로 바꾸기 위해서는 최소 몇 번의 자리 교체가 이루어져야 하는지를 구하는 문제입니다. 네 자리 수의 개수는 9000개 정도 밖에 되지 않으므로, 당연히 완전 탐색이 가능한 문제입니다. 다만 "최소" 교체 수를 구하기 위해서 BFS를 이용하여 구현을 해주면 됩니다. 소수 판별을 여러 번 해야하기 때문에 에라토스테네스의 체를 활용하여 소수를 미리 구해놓으면 편합니다. 또한 string과 int 사이의 변환이나 맨 앞 자리 수가 0이 나와서 세 자리 수가 되지 않는지 체크를 해주면서 코..

백준 BOJ 13701번 : 중복 제거 Solved.ac 난이도 : Gold III 알고리즘 분류 : 비트마스킹, 비트 집합 이 문제는 조건이 중요하기 때문에 정확히 적어두겠습니다. (비트마스킹을 반드시 이용해야만 풀 수 있는 문제이기 때문) N개의 정수가 순서대로 입력될 때, 중복되어 나오는 수를 제외하고 출력하는 문제입니다. 이 때 N ≤ 500만이며, 입력되는 각 정수 A_i < 2^25입니다. 그리고 가장 강력한 조건은 메모리 제한인데, 이 문제에서는 메모리 제한이 8MB밖에 되지 않습니다. 따라서 저장 공간을 최대한으로 아끼기 위해 비트를 이용해 데이터를 저장하는 방식을 사용합니다. 각 A_i는 2^25 미만의 크기를 가지지만 용량을 위와 같이 계산해보면 int 배열은 최대 2^21칸 미만으로 ..