나그네

27930번: 당신은 운명을 믿나요? 문제 https://www.acmicpc.net/problem/27930 27930번: 당신은 운명을 믿나요? 민지는 11번째 글자까지 읽었을 때 각각 1,3,5,7,9번째의 글자를 제거하고 YONSEI를 찾을 수 있다. www.acmicpc.net 풀이 주어진 문자열을 차례대로 탐색하며 KOREA와 YONSEI 중 먼저 완성되는 문자를 출력하는 문제다. 따라서 주어진 문자열의 각 문자에 대해 KOREA와 YONSEI에 포함된 문자라면 작업을 수행한다. KOREA와 YONSEI가 몇 번째 글자까지 완성되었는지 나타내는 변수 k와 y에 대해 k 또는 y가 (이번 글자가 들어있어야 할 위치 - 1)인 경우 1 증가시켜 줬다. 예를 들어 K는 KOREA의 1번째에만 쓰이므..

16566번: 카드 게임 문제 https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 풀이 철수가 낸 카드보다 숫자가 큰 카드 중 가장 작은 카드를 민수가 내도록 하면 된다. 즉, 사용할 수 있는 카드를 오름차순 정렬한 다음 upper_bound 함수를 사용하면 된다. (upper_bound 함수는 찾고자 하는 값을 초과하는 값 중 가장 작은 값의 iterator를 반환한다.) 그러나 같은 카드는 ..

20040번: 사이클 게임 문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 집합 내의 두 정점을 이어주면 같은 컴포넌트(집합)에 속하게 되고 같은 컴포넌트끼리 연결을 해줄 때 사이클이 생긴다. 유니온 파인드 알고리즘을 사용해 해결할 수 있다. 연결할 두 정점을 입력받고 두 정점이 같은 컴포넌트인지만 확인하면 된다. 만약 이미 같은 컴포넌트라면 해당 연결에서 사이클이 생성되므로 몇 번째 연결인지 출력하고 프로그램을 종료하면 된다...

1414번: 불우이웃돕기 문제 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 풀이 최소 스패닝 트리(MST) 변형문제 중 하나로 간선의 가중치가 알파벳으로 입력된다. 문제 조건에 따라 ascii 코드를 기준으로 연산하여 간선을 저장한다. 기부할 수 있는 랜선의 길이는 최소 스패닝 트리의 가중치를 제외한 모든 가중치의 합이므로 간선을 저장할 때마다 cost에 가중치를 더해주고 최소 스패닝 트리의 컴포넌트를 연결할 때마다 간선의 가중치만큼 ..

1854번: K번째 최단경로 찾기 문제 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 풀이 다익스트라 알고리즘과 우선순위 큐(최대 힙)를 사용해 풀 수 있는 문제다. 시작 지점이 1로 고정되어 다른 모든 정점까지의 거리를 구하는 문제이므로 다익스트라 알고리즘을 쓸 수 있다. 원래 다익스트라 알고리즘은 최단 거리를 저장하는 dist 배열의 값을 비교해 갱신해 나간다. 하지만 이 문제에서는..

1833번: 고속철도 설계하기 문제 https://www.acmicpc.net/problem/1833 1833번: 고속철도 설계하기 첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에는 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다. 이 비용은 각각 10,000을 넘지 않는 자연수이다. 만약 비용이 음 www.acmicpc.net 풀이 최소 스패닝 트리(MST) 응용문제다. 주어진 인접 행렬에 따라 (i, j)의 값이 양수이면 간선을 추가하고, 음수라면 이미 연결되어 있는 간선이므로 i와 j를 union 해주고 전체 비용에 비용의 절댓값을 추가해 준다. 그리고 인접 행렬은 같은 값이 2번씩 입력되므로 ÷2를 해주어 미리 연결되어 있는 간선들의 가중치를 구해준다. 이제 크루스칼..

14621번: 나만 안되는 연애 문제 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 풀이 최소 스패닝 트리(MST) 응용문제로 남초 대학교와 여초 대학교를 연결하는 도로로만 이루어져 있으므로 간선을 입력받을 때 한 학교는 남초, 나머지 학교는 여초이면 된다. 따라서 배열을 만들어 각 학교가 남초인지 여초인지 저장하고 간선을 입력받을 때 조건문만 추가해 주면 된다. 그리고 모든 학교를 연결할 수 없는 경..

1185번: 유럽여행 문제 https://www.acmicpc.net/problem/1185 1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 풀이 모든 나라를 방문해야 하고 길은 N-1개만 남겨야 하므로 최소 스패닝 트리(MST) 알고리즘을 사용한다. 보통 최소 스패닝 트리 문제는 간선의 가중치가 이동 거리, 시간, 비용 등인데 이 문제에서는 방문한 나라에 도착한 시점에 내는 비용도 고려해야 한다. 따라서 도착한 지점의 비용을 어떻게 처리할 것인지가 문제를 푸는 핵심이다...

4792번: 레드 블루 스패닝 트리 문제 https://www.acmicpc.net/problem/4792 4792번: 레드 블루 스패닝 트리 무방향, 무가중치, 연결 그래프가 주어진다. 그래프의 각 간선은 빨간색 또는 파란색으로 색칠되어져 있다. 이 그래프의 스패닝 트리 중 파란색 간선이 정확히 k개인 것이 있는지 없는지 알아내 www.acmicpc.net 풀이 파란색 간선의 가중치를 1, 빨간색 간선의 가중치를 0으로 해서 간선을 추가한다. 간선을 가중치를 기준으로 오름차순 정렬하여 파란색 간선의 수를 최소로 한 스패닝 트리의 가중치(파란색 간선의 수)를 minBlue, 내림차순 정렬하여 최대로 한 스패닝 트리의 가중치를 maxBlue로 저장한다. minBlue ≤ K ≤ maxBlue를 만족하면 1..

1368번: 물대기 문제 https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 풀이 최소 스패닝 트리(MST) 응용문제로 물을 끌어오는 비용과 우물을 파는 비용을 비교해야 한다. 따라서 가상의 정점을 만들고 i번째 우물을 파는 비용을 가상의 정점과 i번째 정점을 잇는 간선으로 추가해 주면 된다. 그리고 인접 행렬에서 각 정점 간 물을 끌어오는 비용을 간선으로 추가한다. 이제 크루스칼 알고리즘을 사용해 최소 스패닝 트리의..