복습 정리 노트

백준 BOJ 12041번 : Password Security (Small 2) 문제 난이도 : Gold III 알고리즘 분류 : 무작위화, 구성적 모든 대문자 알파벳을 하나씩 사용하여 26자리 비밀번호를 만들 때, 해당 비밀번호가 N개의 주어진 문자열을 포함하지 않도록 만드는 문제이다. 1 ~ 26으로 이루어진 순열을 무작위로 만든 뒤, 이 순열에 해당하는 문자열이 N개의 문자열을 포함하지 않을 때까지 돌리면 된다. 문제는 아예 불가능한 경우가 있는데, 이를 해결하기 위해 1만번까지는 돌려보고, 그래도 해당하는 정답이 없으면 impossible로 간주해주면 모든 테스트케이스를 통과할 수 있다. (참고로 1천번은 넉넉하지 않아 WA를 받을 확률이 높다.) 더보기 #include #define int lon..

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개 설치되지는 않기..