복습 정리 노트

백준 BOJ 25711번 : 인경산 문제 난이도 : Gold V 알고리즘 분류 : 누적 합 2차원 좌표 상의 N개의 점이 주어지고, 어떤 인접한 구간의 두 점 사이를 이동할 때 필요한 에너지는 내리막길일 경우 거리에 해당, 평지일 경우 거리의 2배, 오르막길일 경우 거리의 3배라고 할 때 M개의 쿼리에 대해 두 지점 사이의 필요한 에너지들을 구하는 문제이다. 쿼리 문제이므로 O(1)이나 O(log N)과 같이 짧은 시간에 쿼리를 처리할 수 있어야 한다. 이 문제에서는 누적 합을 이용하여, 맨 왼쪽 지점에서부터 특정 지점까지 이동하는데 필요한 에너지들의 목록을 구해둔다. 반대로, 맨 오른쪽 지점에서부터 특정 지점까지 이동하는데 필요한 에너지들의 목록도 구해둔다. 각각의 값들은 위에서 정의한 식대로 구해주면..

풀이한 문제들 중에서 인상적인 문제만 몇 개 뽑아서 정리한다. 문제 알고리즘은 무작위로 선정하였다. 백준 BOJ 25569번 : My뷰 꾸미기 문제 난이도 : Platinum IV 알고리즘 분류 : 조합론, 분할 정복을 이용한 거듭제곱 N개의 (a, b)쌍에 대해 min(a, b) = c라고 할 때, (a C 1 x b C 1) + (a C 2 x b C 2) + ... + (a C c x b C c)의 합을 구하는 문제이다. N과 a, b는 30만 이하이다. 각 항을 팩토리얼과 분모는 페르마의 소정리 + 분할 정복을 이용한 거듭제곱으로 계산이 가능하나, 항이 매우 많아 시간 초과에 걸리게 된다. 이 경우 항을 줄여주어야 하는데, (a C 1 x b C 1) + (a C 2 x b C 2) + ... +..

삼분 탐색 알고리즘(Ternary Search Algorithm)이란 말 그대로 구간에서 1/3 지점과 2/3 지점의 함수값의 크기 비교를 기반으로 탐색을 해나가는 알고리즘이다. 이분 탐색 알고리즘은 그래프가 단조 증가 또는 단조 감소한다는 조건 하에서만 사용이 가능하지만, 삼분 탐색은 극값이 최대 1개 이하로 있는 모든 그래프에 대하여 사용 가능하다. (즉, 단순히 극값을 갖는 그래프 뿐만이 아닌 단조 증가, 감소 그래프에서도 사용이 가능하다.) 1개의 최솟값을 갖는 y = x^2 꼴의 그래프를 [l, r]의 구간에서 삼분 탐색하는 상황에 대해 생각해보자. (물론 극값을 구간에 포함하고 있다고 가정한다.) 1/3 지점을 x = m1, 2/3 지점을 x = m2라고 하며, 우리는 극값의 x 좌표 x_mi..

백준 BOJ 25513번 : 빠른 오름차순 숫자 탐색 문제 난이도 : Gold V 알고리즘 분류 : BFS 주어진 5 x 5 크기의 배열에서, 특정 위치에서 시작하여 1, 2, 3, 4, 5, 6을 순서대로 방문하는 최소 경로의 길이를 구하는 문제이다. (이 때, -1은 지나갈 수 없는 칸이며 만약 순서대로 방문하는 것이 불가능하다면 -1을 출력해야 한다.) BFS를 반복문으로 여러 번 사용하는 문제이다. 초기 위치에서 cur(1 ~ 6으로 반복문을 돌려준다.)를 방문하는 BFS를 구현하고, 방문이 되었다면 초기 위치를 해당 칸의 위치로 바꿔주고 다음 루프를 돌면 된다. 만약 방문이 불가능하다면 -1을 출력해주고 즉시 종료해주면 된다. 더보기 #include #define int long long usi..

백준 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를 잇는 선분이 있..