나그네

27889번: 특별한 학교 이름 문제 https://www.acmicpc.net/problem/27889 27889번: 특별한 학교 이름 GEC에는 여러 학교가 있다. 각 학교의 약칭과 정식 명칭은 다음과 같다. NLCS: North London Collegiate School BHA: Branksome Hall Asia KIS: Korea International School SJA: St. Johnsbury Academy 학교 이름을 좋아하는 규빈이 www.acmicpc.net 풀이 문제에 주어진 약칭을 각각 조건문에 넣어 정식 명칭을 출력하도록 하면 되는 문제다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); c..

13975번: 파일 합치기 3 문제 https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 풀이 두 개의 파일을 합치는데 드는 비용은 두 파일의 크기의 합이다. 합친 파일을 다른 파일과 또 합칠 수 있고 하나의 파일을 만들기 위해 필요한 비용의 최솟값을 구하는 문제다. 각 파일의 크기가 최대 10,000이고 파일의 수가 최대 1,000,000 이므로 long long 자료형을 사용해야 한다. 작은 두 파일을 합치면 비용이 적게 들고 그 파일을 합칠..

17425번: 약수의 합 문제 https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 풀이 예전에 모든 수의 약수의 합을 에라토스테네스의 체를 사용해 구하는 법을 9213번 문제를 통해 만들어봤다. [9213 꽤 좋은 수 해설] 링크를 참고해 주길. 어떤 수 A은 A의 배수의 약수다. 범위 내 모든 A의 배수에 A을 더해준다. 그러면 sieve의 A번 인덱스에는 A의 모든 약수의 합을 값으로 가..

1197번: 최소 스패닝 트리 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 최소 신장 트리(Minimun Spanning Tree, MST)의 개념을 알고 있으면 풀 수 있는 standard 문제다. 최소 스패닝 트리는 주어진 정점을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소가 되는 트리다. 우선순위 큐를 사용하는 프림 알고리즘과 크루스칼 알고리즘으로 구현한 MST 알고리즘을..

3803번: Networking 문제 https://www.acmicpc.net/problem/3803 3803번: Networking You are assigned to design network connections between certain points in a wide area. You are given a set of points in the area, and a set of possible routes for the cables that may connect pairs of points. For each possible route between two points, you a www.acmicpc.net 풀이 여러 테스트 케이스에 대해 MST를 구하는 문제다. 최소 스패닝 트리(MST)는 주..

23034번: 조별과제 멈춰! 문제 https://www.acmicpc.net/problem/23034 23034번: 조별과제 멈춰! 교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net 풀이 처음에는 X, Y 정점부터 시작하는 최소 스패닝 트리(MST)를 구해줬는데 당연히 시간초과를 받았다. 그래서 생각한 다음 방법은 처음부터 MST를 구해놓은 다음 X와 Y 사이의 가장 큰 가중치를 가지는 간선을 제거해 주는 방법이었다. 처음에는 MST의 간선을 이을 때마다 어느 정점에서 이어졌는지를 기록하고 역추적하는 방식으로 구현했다. 그러나 여..

13274번: 수열 문제 https://www.acmicpc.net/problem/13274 13274번: 수열 지훈이는 수열을 좋아한다. 지금 지훈이는 size 가 N 인 수열을 가지고 놀고 있다. 지훈이는 K 개의 쿼리에 따라 수열을 변화시킬 것인데, 쿼리의 형식 및 작업 과정은 다음과 같다. L R X : 수열을 www.acmicpc.net 풀이 단순한 구현 문제다. 하지만 정렬을 매번 하게 되면 시간초과가 난다! 따라서 정렬을 최소한으로 해야 한다. 그래서 STL sort 함수의 시간복잡도도 찾아보고,, 최악일 때도 O(N log N)인 머지 소트로 해도 안되더라.. 결국 찾은 해결법은 L, R, X를 입력받았을 때 이미 수열은 정렬되어 있다. 그리고 L부터 R까지 X를 더했을 때, 이를 제외한 ..

2887번: 행성 터널 문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 최소 스패닝 트리(MST)를 구현하기 위해 프림 알고리즘을 사용했다. 각 정점의 3차원 좌표가 주어지고 각 정점 간 실제 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 하지만 모든 정점 사이의 |xA-xB|, |yA-yB|, |zA-zB|를 구하게 되면 N^2의 공간복잡도를 가지게 되어 메모리초과가 난다. 따라..

15926번: 현욱은 괄호왕이야!! 문제 https://www.acmicpc.net/problem/15926 15926번: 현욱은 괄호왕이야!! 첫 번째 입출력에서, 맨 처음 위치부터 4개를 잘라낸 (())가 가장 긴 올바른 괄호 문자열이다. 두 번째 입출력에서, 6번째 위치부터 8개를 잘라낸 ()((()))가 가장 긴 올바른 괄호 문자열이다. www.acmicpc.net 풀이 흔한 괄호 문제의 심화 버전으로 가장 긴 괄호 부분 문자열의 길이를 구하는 문제다. 여전히 스택을 사용해 풀 수 있다. 스택의 top의 문자가 '('이고 현재 문자가 ')'라면 top원소를 pop 해준다. 이외의 경우에는 스택에 문자와 문자의 인덱스를 pair로 쌓는다. 이 과정이 모두 끝나고 나면 올바른 괄호 문자열을 이루지 못..

1922번: 네트워크 연결 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 기본적인 최소 신장 트리(Minimun Spanning Tree, MST)를 사용하는 문제다. 프림 알고리즘으로 구현하는 MST 알고리즘을 사용했다. MST 알고리즘은 아래 글을 보고 공부했다. 아직 유니온 파인드를 모르기 때문에 크루스칼 알고리즘은 보류해놨다. https://4legs-study.tistory.com/112 최소 스패닝 트리 (MST) : 프림 알고리즘 (Prim Algorithm) 최소 스패닝 트리에 대한 내용과 크루스칼 알고리즘..