나그네

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

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번 가장 긴..

1818번: 책정리 문제 https://www.acmicpc.net/problem/1818 1818번: 책정리 동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고 현재 뒤죽박죽 되어있는 순서를 왼쪽부터 www.acmicpc.net 풀이 책 번호를 오름차순으로 정렬하고자 하므로 가장 긴 이미 정렬되어 있는 책들은 놔두고 나머지 책들만 재배치를 하면 된다. 따라서 가장 긴 증가하는 부분 수열(LIS) 알고리즘을 사용해 LIS의 길이를 구하고, 책 수에서 LIS의 길이를 뺀 개수를 출력하면 된다. N의 범위는 2 × 10^5이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 시간초과가 나므로 시간복잡도가 O(NlogN..

3066번: 브리징 시그널 문제 https://www.acmicpc.net/problem/3066 3066번: 브리징 시그널 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에 포트의 개수 N(1 ≤ N ≤ 40000)이 주어지고, 두 번째 줄부터는 왼쪽 블록의 포트와 연결되어야 하는 오른쪽 www.acmicpc.net 풀이 최대한 많은 시그널을 교차하지 않도록 연결해야 하므로 연결되는 포트의 번호가 증가하는 순서대로 많이 연결할 수 있도록 해야 한다. 따라서 이 문제는 가장 긴 증가하는 부분 수열의 크기를 구하는 문제다. N의 범위는 4 × 10^4이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 시간초과가 나므로 시간복잡도가 O(NlogN)인 알고리즘으로 풀어야 ..

12014번: 주식 문제 https://www.acmicpc.net/problem/12014 12014번: 주식 입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두 www.acmicpc.net 풀이 주가가 올랐을 때만 주식을 사고, 그리고 구매는 하루에 1번만 가능하고 최대 K번만 살 수 있다. 따라서 가장 긴 증가하는 부분 수열의 길이가 K 이상이면 조건을 만족하며 주식을 구매할 수 있다. N의 범위는 10^4이지만 테스트 케이스의 수가 10^2 이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 최대 시간복잡도가 10^10이 되므로 시간복잡도가 O(Nl..