나그네

4195번: 친구 네트워크 문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 친구 네트워크가 연결될 때마다 네트워크에 연결된 사람의 수를 출력하는 문제다. 각 이름에 대해 번호를 부여하기 위해 map 자료 구조를 사용한다. 만약 map에 이름이 없다면 맵의 사이즈를 번호로 사용하게 한다. 이러면 번호가 0번부터 붙게 된다. 또 N번의 연결이 이루어지는데 각 연결마다 두 명의 이름이 주어지므로 최대 2 × N명의 관계를 받을 ..

Round #863 (Div. 3) 대회 https://codeforces.com/contest/1811 Dashboard - Codeforces Round 863 (Div. 3) - Codeforces codeforces.com 푼 문제 A. Insert Digit 정수 n과 d를 입력받아 d를 n의 어딘가에 한 번 적절히 넣어 만들 수 있는 가장 큰 수를 출력하는 문제. 정수 n을 문자열로 받아 앞에서부터 탐색하며 각 자릿수를 x라 하면 d > x인 경우 d를 출력한 다음 x를 출력한다. 이외의 경우(d ≤ x)에는 x만 출력한다. flag를 만들어 d > x인 경우에도 이미 d를 한 번 출력했다면 x만 출력한다. #include using namespace std; int main() { ios::..

1766번: 문제집 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 여러 가지 순서를 모두 만족하며 정렬해야 하므로 위상정렬 알고리즘을 사용한다. 기본적인 위상정렬 알고리즘에 추가적인 정렬 기준이 추가된 문제다. 기본적으로 일반적인 위상정렬과 같이 indegree 배열의 값이 0인 것들을 큐에 넣는데, 가능한 쉬운(번호가 작은) 문제부터 풀어야 하므로 큐 대신 최소 힙을 사용한다. STL에서 우선순위 큐..

1516번: 게임 개발 문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 각 건물을 짓는 데는 먼저 지어져야 하는 건물이 있으므로 위상 정렬을 해야 한다. 그리고 각 건물이 완성되기까지 걸리는 최소 시간을 출력해야 하므로 위상 정렬하는 순서에 따라 시간을 계산해 주면 된다. 위상 정렬은 큐에 들어가고 나오는 순서대가 정렬된 순서이므로 차례대로 작업을 수행한다. 기본적으로 각 건물을 완성하는 데 걸리는 시간은 그 건물을 완성하..

2252번: 줄 세우기 문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 여러 가지 순서를 모두 만족하며 정렬해야 하므로 위상정렬 알고리즘을 사용한다. 기본적인 위상정렬 알고리즘을 사용하는 문제로 거저 주는 문제다. 각 순서를 입력받을 때마다 u -> v 간선을 추가하고 뒤의 인덱스의 indegree 배열의 값을 1 증가시킨다. indegree 배열의 값이 0인 정점을 모두 큐에 추가하고 차례..

2623번: 음악프로그램 문제 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 여러 가지 순서를 모두 만족하며 정렬해야 하므로 위상정렬 알고리즘을 사용한다. 기본적인 위상정렬 알고리즘을 배울 때 푸는 문제다. 각 순서를 입력받을 때마다 [앞->뒤]의 간선을 추가하고 뒤의 인덱스의 indegree 배열의 값을 1 증가시킨다. indegree 배열의 값이 0인 정점을 모두 큐에 추가하고 차례대로 front 원소에 대해 탐색..

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에 가중치를 더해주고 최소 스패닝 트리의 컴포넌트를 연결할 때마다 간선의 가중치만큼 ..