복습 정리 노트

Mo's 알고리즘이란 오프라인 쿼리(= 원소의 업데이트가 없어야 함)를 특정한 순서로 배치하여 효율적으로 처리하는 알고리즘이다. 보통 제곱근 분할법(= 루트 N개의 버킷으로 나누어, 원소들을 버킷 단위로 다루다가 필요할 때 원소 단위로 들어가 값을 다룸)을 활용하여 하나의 쿼리를 O(√N) 시간에 처리할 수 있다는 점에서 특이한 시간 복잡도를 갖는다. ** kks227님의 블로그를 통해 공부하였다. 문제도 거기서 소개한 문제들을 공부했다. 백준 BOJ 11659번 : 구간 합 구하기 (연습용) 문제 난이도 : Silver III 알고리즘 분류 : 누적 합 (..이지만? Mo's 알고리즘으로 풀어보았다.) 굳이 Mo's 알고리즘까지 필요하지는 않지만, 쿼리들을 재배치하여 풀어볼 수 있는 문제라는 점에서 한..

백준 BOJ 18017번 : 총알의 속도 문제 난이도 : 난이도를 매길 수 없음 알고리즘 분류 : 물리학 A m/s로 달리며 B m/s로 총알을 발사했을 때 총알의 속력을 구하는 문제이다. 이 때 A, B는 10^8 이하이며, 10^(-9) 이내의 오차로 답을 구해야 한다. 상대성 이론을 사용하는 문제이다. 왜냐하면 속력이 10^8 수준까지 매우 커지면 빛의 속력을 고려할 필요가 있기 때문이다. 따라서 다음의 공식을 사용한다. 더보기 #include #define int long long using namespace std; main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); double a, b; cin >> a >> b;..

오늘은 백준 브론즈 브루트포스 알고리즘 문제들을 밀어볼 것이다. 참고로 3,000문제를 넘게 풀면 나머지 브론즈 문제들은 솔직히 문제를 풀기보다 번역기에 돌린 문제의 지문을 "해석"하는 과정이 더 어렵다. (말 그대로 문장 구조의 앞뒤가 안 맞아서 대충 그동안 푼 문제들의 경험으로 문제의 지시를 끼워맞춰야 한다.) 백준 BOJ 9703번 : Anti-Arithmetic Permutation 문제 난이도 : Bronze II 알고리즘 분류 : 브루트포스 N개의 수가 주어졌을 때, 순서를 뒤집지 않고 어떤 3개의 수를 선택해도 그 세 수가 등차수열을 이루지 않도록 하는 수열을 Anti-Arithmetic Permutation이라고 할 때, 주어진 수열이 Anti-Arithmetic Permutation인지를..

백준 BOJ 13306번 : 트리 문제 난이도 : Platinum IV 알고리즘 분류 : 오프라인 쿼리, 분리 집합 트리와 쿼리가 주어질 때, 각 쿼리에 대해 특정 간선을 지우거나 두 정점이 연결 상태인지를 구하는 문제이다. 오프라인 쿼리 문제인데, 오프라인 쿼리 문제는 주어진 쿼리 순서대로 처리를 하는 것이 아니라 문제를 효율적으로 풀 수 있게끔 쿼리의 순서를 재배치하여 풀이하는 방식의 문제를 말한다. 예를 들어 이 문제에서는 쿼리를 역순으로 배치한 뒤 분리 집합으로 노드들을 연결해가면서 풀어주면 아주 쉽게 풀 수 있다. 역순 배치가 아닌 다른 순서대로 푸는 문제도 있는 것 같던데 조만간 공부할 것이다. (예를 들면 mo's 알고리즘. 지금 제곱근 분할법 문제 몇 개는 풀어봤는데 mo's를 공부 안해서..

백준 BOJ 20149번 : 선분 교차 3 문제 난이도 : Platinum IV 알고리즘 분류 : 기하학, 선분 교차 판정 두 선분의 끝 점의 좌표가 주어질 때, 두 선분의 교차 여부를 구하고, 만약 한 점에서만 교차한다면 그 좌표를 오차 범위 1e-9 이내로 구하는 문제이다. CCW 값들을 가지고 잘 푸는 것인지는 당연히 아는데, 케이스를 어떻게 나눠야 깔끔하게 정리되는지 도저히 구상이 안 되어서 다른 블로그를 보고 공부했다. 개인적으로는 이 링크에 설명이 가장 잘 되어있다고 생각하고 또 여기서 대부분의 코드를 참고했다. (20220829 수정 : 링크가 잘못 걸려 있었다;;) 일단 교차 판정을 먼저 해보자. 점은 a, b, c, d의 네 점이 주어지고 a, b를 잇는 선분과 c, d를 잇는 선분이 있..

백준 BOJ 11281번 : 2-SAT - 4 문제 난이도 : Platinum III 알고리즘 분류 : SCC, 2-SAT 2-SAT에 맞는 식이 주어질 때 x1 ~ xN에 참 또는 거짓을 넣어 식 전체가 참이 되도록 만들 수 있는지 판별하고, 만약 가능하다면 식을 참으로 만드는 각 변수 x1 ~ xN의 값으로 가능한 것을 하나 구하는 문제이다. 식을 참으로 만들 수 있는지 여부의 판별은 2-SAT - 3의 풀이와 동일하다. 이제 식을 만족시키는 각 변수의 참/거짓 값을 찾아야하는데, 그리디하게 접근해보자. x → y라는 식이 거짓이 되는 경우는 x = true, y = false인 경우뿐이다. x = false이면 y는 true든 false든 관계없다. 식을 최대한 참으로 만들기 위한 최선의 전략은 노..

백준 BOJ 11280번 : 2-SAT - 3 문제 난이도 : Platinum IV 알고리즘 분류 : SCC, 2-SAT bool 변수 x1, ... , xn에 대해서 F = (xi ∨ xj) ∧ (xk ∨ xl) ∧ ... 와 같은 꼴의 식이 주어질 때, 변수들의 참 거짓을 적절히 설정하여 F의 값이 참이 되게 할 수 있는지 판별하는 문제이다. (a ∨ b)와 같은 식이 있을 때 a가 거짓이면 b가 참, b가 거짓이면 a가 참이라는 두 개의 식을 얻을 수 있고 이렇게 2M개의 식을 얻은 뒤 x와 ~x가 모두 참인 식이 하나라도 나오면 불가능, 나머지 경우는 가능이다. 이것은 SCC로 풀이 가능한데, 2N개의 노드에 대해 2M개의 간선을 모두 연결한 그래프를 만든 후 a와 ~a가 같은 scc에 속해있는 ..

백준 BOJ 13904번 : 과제 문제 난이도 : Gold III 알고리즘 분류 : 그리디, 우선순위 큐 N개의 과제들의 남은 날짜 수와 그 과제의 점수가 주어질 때, 하루에 하나씩 과제를 하여 얻을 수 있는 점수의 최댓값을 구하는 문제이다. 먼저 문제들을 남을 일 수를 기준으로 오름차순 정렬해준 뒤, 우선순위 큐에 할 과제들만 남겨보자. 우선순위 큐에 과제를 하나씩 넣고 만약 우선순위 큐의 size가 방금 넣은 날짜 수보다 많다면 같아질 때까지 빼주면 된다. i번째 과제를 넣는 과정을 통해 i일까지 할 과제들을 우선순위 큐에 남긴다고 생각하면, 하루에 한 개씩 과제를 할 수 있으므로 i보다 많은 수의 과제가 들어있으면 안되기 때문이다. 더보기 #include #define int long long us..

백준 BOJ 1477번 : 휴게소 세우기 문제 난이도 : Gold IV 알고리즘 분류 : 이분 탐색 길이가 K인 도로 위에 N개의 휴게소가 있고, 여기에 M개의 휴게소를 더 지어 휴게소 간 거리의 최댓값이 최소가 되도록 할 때, 그 최솟값을 구하는 문제이다. 이분 탐색을 이용하여 풀이할 수 있다. 답을 m으로 두고 l ~ r 범위 내에서 이분 탐색을 하면서 휴게소 간의 거리를 m으로 두고 휴게소를 설치했을 때 휴게소가 M개 이하로 설치되었는지 확인하면서 값을 갱신해주면 된다. 주의할 점은 두 휴게소 사이의 거리가 x라면, 휴게소는 max(x-1, 0) / m개 설치된다. 왜냐하면, 예를 들어서 생각해보면 휴게소 사이의 거리가 100인데 거리 50으로 휴게소를 설치한다고 하여 휴게소가 2개 설치되지는 않기..

백준 BOJ 2150번 : Strongly Connected Component 문제 난이도 : Platinum V 알고리즘 분류 : 강한 결합 요소 (SCC) 방향 그래프가 주어질 때, 이들을 SCC로 나누어 출력하는 문제이다. 여기서 말하는 SCC(Strongly Connected Component)란, 한 Component 내의 어떤 두 점 사이에도 이동이 가능한 요소를 말한다. (SCC를 나눌 때는 당연히 한 Component의 크기가 최대가 되도록 나누어야 한다.) 그래프를 입력받고 adj 벡터에 간선들을 저장해주는 부분은 기본적이므로 설명을 생략한다. 이제 DFS 방식으로 노드들을 탐색하며, 노드 번호를 방문하는 순서대로 오름차순으로 매긴다. (nnum 벡터에 저장) 즉, 번호를 먼저 매기는 것..