나그네

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..

1647번: 도시 분할 계획 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 가장 짧은 도로들만 가지고 모든 집이 연결되어 있어야 하므로 집을 정점, 도로를 간선이라고 생각하고 최소 스패닝 트리(MST)를 구하면 된다. 단, 도시를 두 개의 마을로 나눠야 하고 각 마을에는 집이 최소 하나는 있어야 하므로 MST의 간선 중 길이가 가장 긴 간선을 제거해 주면 된다. 코드 #include using ..

1806번: 부분합 문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 부분합이 S 이상인 부분합 중 길이가 가장 작은 것의 길이를 구하는 문제다. 시간복잡도가 O(N^2)인 알고리즘으로 풀면 시간 초과를 받는다. 따라서 O(N)인 알고리즘으로 풀어야 한다. 그중 하나가 투 포인터를 사용해서 푸는 방법이다. left와 right를 모두 0으로 두고 sum = v[0]으로 초기값을 설정한다. 합(sum)은 인덱스가 left부..

27498번: 연애 혁명 문제 https://www.acmicpc.net/problem/27498 27498번: 연애 혁명 신촌고등학교 학생회장 기령이는 최근 학생들의 복잡한 사랑관계로 인해 고민이 많다. 학생들이 공부에 집중하지 못해 전반적인 성적이 하락하고 있는 것이다. 이에 기령이는 학생들의 복잡한 www.acmicpc.net 풀이 이미 성사된 사랑 관계는 포기하도록 하지 않아야 하기 때문에 반드시 포함되는 간선이 있어야 한다. 그리고 사랑 관계가 K 각 관계를 이루지 않아야 하므로 사이클이 없다(트리). 즉, 반드시 포함되어야 하는 간선이 있는 최소 스패닝 트리(MST)를 구현하는 문제다. 이 문제에선 포기하도록 만든 애정도의 합이 최소가 되어야 하므로 최대 스패닝 트리를 구하고 가중치의 합을 모..

11780번: 플로이드 2 문제 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 제목부터 노골적으로 플로이드-워셜 알고리즘을 사용하는 문제임을 보여준다. 그리고 각 정점에서 다른 정점으로 갈 때 최단 경로 중 하나를 출력해줘야 하므로 path 배열을 만들어 최단 경로가 갱신될 때마다 i -> k의 경로, k -> j의 경로를 중복되는 k를 제외하고 합쳐준다. 이를 vector의 insert 함수를 사용해서 합쳐서 만들어줬다. 그리고 p..

5214번: 환승 문제 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 풀이 하이퍼튜브라는 간선을 통해 정점 간 최단 거리를 구하는 문제다. 각 하이퍼튜브에 포함된 간선들을 서로 이어주면 메모리 초과가 나게 된다. 따라서 M개의 하이퍼튜브 정점을 만들고 하이퍼튜브를 정점으로 생각하고 하이퍼튜브에 포함된 정점들과 이어준다. 그리고 BFS를 통해 최단 경로를 찾으면 된다. 코드 #include using namespace..

Round #859 (Div. 4) 대회 https://codeforces.com/contest/1807 Dashboard - Codeforces Round 859 (Div. 4) - Codeforces codeforces.com 푼 문제 A. Plus or Minus a, b, c를 입력받아 a+b=c가 성립하는지 여부를 출력하는 간단한 문제다. #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { int a, b, c; cin >> a >> b >> c; if (a + b == c) cout t; while (t--) { int n, a = 0,..

1937번: 욕심쟁이 판다 문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 2차원 배열에서 어느 한 점에서 출발해 상하좌우로 점차 증가하는 방향으로만 이동할 수 있을 때 가장 많이 이동할 수 있는 길이를 구하는 문제다. 따라서 dfs로 배열의 모든 점에 대해 가장 긴 이동 거리를 구하고 최댓값을 구했는데 시간초과를 받았다. 시간초과를 해결하기 위해 메모이제이션을 하는 방법밖에 없다고 생각했다. 따라서 visited 배열을 ..

3745번: 오름세 문제 https://www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 풀이 수열이 주어졌을 때 점차 증가하는 부분 수열을 오름세라 하고 가장 긴 오름세를 찾는 문제다. 즉, 가장 긴 증가하는 부분 수열을 구하는 문제다. 범위가 10^5이므로 시간복잡도가 O(NlogN)인 알고리즘을 사용해 풀어야 한다. O(NlogN)으로 푸는 법은 아래 링크에 설명되어 있다. [12015번 가장 긴 증가하는 부분 수열 2 문제] | [12015번 가장 긴..