나그네

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로 쌓는다. 이 과정이 모두 끝나고 나면 올바른 괄호 문자열을 이루지 못..

16398번: 행성 연결 문제 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 풀이 입력 행렬이 각 정점 간 간선의 가중치이므로 i행 j열의 값은 i번째 행성과 j번째 행성 간에 플로우를 설치하는 비용이다. 이를 가지고 최소 스패닝 트리(MST)의 가중치를 구하면 된다. 행성의 수가 최대 1,000개이고 각 가중치의 최댓값이 100,000,000 이므로 최소 스패닝 트리의 가중치의 자료형은 long long 이어야 한다. 코드 #include ..

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) 최소 스패닝 트리에 대한 내용과 크루스칼 알고리즘..

16940번: BFS 스페셜 문제 https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 풀이 스페셜 저지 문제는 답이 여러 개가 가능한 문제다. 이런 경우 답이 맞는지 확인하는 코드가 필요하다. BFS의 결과가 가능한지 구하는 문제다. BFS는 간선의 순서에 따라 이동하는 순서가 바뀐다. 그래서 간선의 순서를 유저가 입력한 답과 같이 이동하도록 재정렬 해줘야 한다. 어떤 순서로 정점을 방문하는지를 저장하는 order 배열을 만들고 먼저 방문해야 하는 정점과 연결된 간선이 앞으로 오도록 간선들을 재정렬 한다. 그리고 BFS를 진행하며 탐색 경로를 구한다. 이 경로가 ..

10423번: 전기가 부족해 문제 https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 풀이 이렇게 하면 될까? 했는데 돼서 푼 다음에 이해를 했다. 여러 발전소에서 전력 공급이 가능하기 때문에 프림 알고리즘을 사용하는 최소 스패닝 트리(MST)에서 우선순위 큐에 발전소와 연결된 모든 간선을 넣어줬다. 그리고 MST의 가중치를 구하면 끝! 이를 개념적으로 이해를 해보자면, 결국 최소 스패닝 트리를 만들기 위..

4386번: 별자리 만들기 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 각 별의 2차원 좌표가 주어지고 별들을 모두 직/간접적으로 최소한의 거리로 이었을 때 거리를 구하는 문제다. 흔한 MST 문제와 달리 약간 생각을 해야한다. 정점 간 가중치가 주어지는 것이 아니기 때문에 각 정점 간 가중치를 직접 구해줘야 한다. 마침 정점의 수 N도 최대 100이므로 모든 정점 간 거리를 구해 간선으로 삼아 MST의 가중치를 구하면 된다. 자료..

11659번: 구간 합 구하기 4 문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 기본적인 누적합 배열을 통해 구간 합을 구하는 문제다. 누적 합 배열은 0번 인덱스의 값은 0이고 각 인덱스의 값이 현재까지 입력받은 수의 합인 배열이다. 예를 들어 입력받는 수가 1 2 3 4 5 라면 누적합 배열은 [0, 1, 3, 6, 10, 15]가 된다. 여기서 i번째 원소부터 j번째 원소까지의 합을 구하기 위해서는 ar..

16964번: DFS 스페셜 문제 https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 풀이 스페셜 저지 문제는 답이 여러 개가 가능한 문제다. 이런 경우 답이 맞는지 확인하는 코드가 필요하다. DFS의 결과가 가능한지 구하는 문제다. DFS는 간선의 순서에 따라 이동하는 순서가 바뀐다. 그래서 간선의 순서를 유저가 입력한 답과 같이 이동하도록 재정렬 해줘야 한다. 어떤 순서로 정점을 방문하는지를 저장하는 orde..