복습 정리 노트

백준 BOJ 10482번 : Goldbach's Conjecture 문제 난이도 : Silver III 알고리즘 분류 : 에라토스테네스의 체 N이 주어졌을 때, N을 두 소수의 합으로 나타내는 방법의 수를 구하고 그 쌍을 모두 출력하는 문제이다. 에라토스테네스의 체로 N 이하의 소수들을 모두 구해놓은 뒤 1부터 N/2에 대해 모두 검사해보면 된다. N이 32,000 이하이므로 브루트포스로 확인해도 시간 초과에 걸리지 않는다. #include #define int long long using namespace std; main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); int Max = 32001; vector p(Max, t..

백준 BOJ 12199번 : Password Attacker (Large) 문제 난이도 : Gold III 알고리즘 분류 : 조합론 (+ 포함-배제의 원리) N자리 비밀번호를 M종류 문자를 모두 사용하여 만들 수 있는 조합의 수를 구하는 문제이다. 위와 같이 먼저 N자리 비밀번호를 M종류 이하의 문자들을 사용하여 만드는 경우의 수에서, M-1종류 이하의 문자들을 사용하여 조합할 수 있는 경우의 수를 빼고, 또 M-2종류 이하의 문자들을 조합하여 만들 수 있는 경우를 더해주고, ...를 반복해주면 된다. (by 포함과 배제의 원리) 다만 이 문제에서 거듭 제곱과 모듈로 처리가 귀찮은데, 특히 모듈로의 경우 반복문 중간에 값이 음수로 넘어갈 수 있으므로 이를 적절히 처리해주어야 한다. #include #de..

백준 BOJ 6185번 : Clear And Present Danger 문제 난이도 : Gold V 알고리즘 분류 : 플로이드-워셜 노드와 노드 사이의 거리로 구성된 인접 행렬이 주어질 때 1번 노드들을 거쳐 주어지는 M개의 노드들을 순서대로 방문하는 경로의 최단 거리를 구하는 문제이다. 플로이드-워셜 알고리즘을 사용하여 노드 간 최단 경로를 구하고, M개의 이동에 대해 경로의 합을 구해주면 된다. #include #define int long long using namespace std; main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); int N, M; cin >> N >> M; vector v(M); for(int i..

백준 BOJ 24935번 : Travelling Caterpillar 문제 난이도 : Silver I 알고리즘 분류 : 그래프 탐색 그래프가 주어지고, 루트 노드에서부터 주어진 몇 개의 리프 노드를 방문하고 돌아온다고 할 때, 순회하는 경로의 최소 길이를 구하는 문제이다. 경로를 예시로 하나 그려보면, 트리에는 사이클이 없기 때문에 한 번 지나간 경로는 반드시 다시 되돌아올 때 사용해야 한다. 따라서 사용되는 간선을 구하고 그 간선들의 길이의 합의 2배를 답으로 구해주면 된다. 사용되는 간선은 bool 벡터로 체크해주면 된다. 그렇다면 사용되는 간선은 어떻게 구할까? 간선을 리프 노드쪽에서부터 루트 노드 방향으로 단방향으로 연결하여 M개의 리프 노드에서부터 루트 노드까지 탐색을 해주며 사용되는 간선을 기..

백준 BOJ 17199번 : Milk Factory 문제 난이도 : Silver I 알고리즘 분류 : DFS 그래프가 주어질 때 모든 지점에서 모일 수 있는 어느 한 점이 존재하는지를 구하고 존재한다면 그러한 가장 작은 노드 번호를 구하는 문제이다. 노드 수가 최대 100개밖에 되지 않으므로, 모든 노드에 대해 다른 모든 노드에서 방문이 가능한지 검사해주면 된다. 즉, DFS를 대략 N^2회 수행해주어 체크해주면 된다. #include #define int long long using namespace std; vector adj; vector vis; void f(int x) { vis[x] = true; for(int i=0; i> N; adj.resize(N+1); for(int i=0; i> a ..

백준 BOJ 3264번 : ONE 문제 난이도 : Silver I 알고리즘 분류 : 그래프 탐색 트리 그래프와 출발점이 주어질 때, 출발점에서 모든 노드를 방문하는 최단 경로의 길이를 구하는 문제이다. 사이클이 존재하지 않으므로, 어떤 말단 노드로 들어가면 다시 되돌아와야 한다. 되돌아올 필요가 없는 경우는 해당 노드들을 마지막으로 방문하는 경우이다. 최단 경로는 다시 되돌아오는 경로가 최대한 긴 경로이므로, 출발 노드에서 가장 먼 노드의 거리를 구해서 모든 노드의 합의 2배에서 빼주면 된다. #include #define int long long using namespace std; vector adj; vector dis; int Max = 0; void f(int x) { Max = max(Max,..

백준 BOJ 15558번 : 점프 게임 문제 난이도 : Silver I 알고리즘 분류 : BFS 1초마다 1번부터 한 칸씩 없어지는 두 개의 다리가 있고, 각 다리의 값이 1이면 지나갈 수 있는 칸이라고 할 때, 1초마다 같은 다리에서 +1, -1 또는 다른 다리로 +M만큼 이동하는 선택지들을 통해 N보다 큰 거리를 이동할 수 있는지 구하는 문제이다. 매번 선택지가 3개라는 점에서 BFS를 생각할 수 있으나 조건문 설정이 나름 까다로워 보인다. (x, y)를 x번 다리(x = 0 또는 1)의 y번째 칸(y = 1 ~ N)이라고 할 때 dis[x][y]를 최단 거리라고 두자. 뒤로 가는 경우 다리가 1초마다 한 칸씩 사라지기 때문에, dis[x][y] < y-2를 만족해야 뒤로 갈 수 있다. (0초일 때 ..

백준 BOJ 5017번 : 마니또 문제 난이도 : Silver I 알고리즘 분류 : 해시를 사용한 집합과 맵, 그래프 이론 N개의 이름 쌍이 주어질 때, 쌍을 연결하면서 생기는 고리의 수를 구하는 문제이다. 우선 입력이 번호가 아닌 이름으로 주어지므로 해시를 사용한 집합과 맵을 활용해야 한다. 그 다음 고리의 형성은 여러 가지로 판단이 가능하겠지만, 나는 나한테 익숙한 방법인 분리 집합을 활용했다. 간선을 하나씩 추가하다가 두 이름이 같은 그룹에 속한 이름이라면, 간선을 연결하면서 새로운 고리가 하나 생기게 된다. 이런 식으로 카운트 해줘서 답을 구해주면 된다. #include #define int long long using namespace std; vector v; int f(int x) { if(..

백준 BOJ 11514번 : Refract Facts 문제 난이도 : Gold V 알고리즘 분류 : 이분 탐색, 물리학 비행기의 고도, 잠수함의 깊이, 비행기와 잠수함의 x축 거리, 공기와 물의 굴절률이 주어졌을 때 특정 각도를 구하는 문제이다. 각도를 알기 위해 알아야 하는 변수는 굴절 지점의 위치이다. 스넬의 법칙에 따르면 빛의 굴절 각도의 sin값의 비가 두 매질의 굴절률의 비와 같다. 따라서 이를 이용하여 다음과 같이 수식을 정리해줄 수 있다. 이제 a에 대한 이분 탐색을 수행해서 답을 구해주면 된다. 사실은 a 값에 따른 수식의 값이 극값을 가지지 않음을 보여야 하는데, 문제만 풀 거라면 사실 큰 의미 없다. #include #define int long long using namespace s..

백준 BOJ 14746번 : Closest Pair 문제 난이도 : Gold V 알고리즘 분류 : 두 포인터 y = c1 위의 N개의 점과 y = c2 위의 M개의 점의 x 좌표가 주어지고 두 직선에서 점을 하나씩 고를 때 유클리드 거리가 가장 가까운 두 점의 거리를 구하고 그러한 쌍의 개수를 구하는 문제이다. 먼저 두 점 set들을 정렬해주고 투 포인터 알고리즘으로 최소 거리를 구해줄 수 있다. 최소 거리를 구한 이후에는 다시 투 포인터 알고리즘으로 최소 거리와 동일한 쌍들을 모두 count 해줄 수 있다. 탐색 자체는 투 포인터 알고리즘으로 O(N)에 되지만 어쨌든 초기에 정렬을 해줘야 하므로 최종 시간복잡도는 O(N log N)이다. #include #define int long long using..