https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이과정 처음 풀어본 map 문제라 조금 헤맸던 문제이다. mp1은 string-key 값을 넣으면 int-value값이 나오는 맵이며, mp2는 int index 값을 넣으면 string이 나오는 기본적인 배열이다. #include #include #include #include using namespace std; int N, M; string str, quest;..

https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 풀이과정 string을 key로 하고, int를 value로 한다. 팔린 책의 개수인 second 개수가 가장 큰 값을 res에 넣는다. 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력해야 되니 팔린 책의 개수인 second 개수가 res일 경우에 first인 key를 출력해주고 함수를 끝낸다. (map은 삽입이 되면서 오름차순으로 자동 정렬된다.) 반복문 데..

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이과정 기본 문제인 것 같았지만, 생각해야 될 것이 많았던 문제이다. 입력을 받고 나서, 두 노드의 부모가 다른 집합일 때와 같은 집합일 때로 나눈다. 다른 집합일 때는 부모의 노드를 통일시켜주고, 만약에 두 부모 중 한 집합이라도 사이클이 존재한다면 두 집합 모두 사이클로 변경해준다. 같은 집합일 때는 시작 노드를 사이클로 변경해준다. 만약 사이클이 존재한다면 넘어가주고, 사..

https://www.acmicpc.net/problem/15809 15809번: 전국시대 첫 번째 줄에 국가의 수를 나타내는 N과 기록의 수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 두 번째 줄 부터 N개의 줄에 걸쳐 i번째 국가의 병력 Ai (1 ≤ i ≤ N)가 자연수로 주어진다. (1 ≤ Ai ≤ 10,000) 다 www.acmicpc.net 풀이과정 #include #include #include using namespace std; int N, M, op, P, Q; int parent[100001], res[100001]; int getParent(int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent..

https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이과정 이 문제는 이분 탐색, BFS, 유니온 파인드 3개의 알고리즘이 섞인 문제여서 매우 어려웠던 문제이다. #include #include #include #include #include using namespace std; int n, m, A, B, cost, s, e; bool c[10001]; vector v[10001]; b..

https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이과정 이 문제는 유니온 파인드와 map 알고리즘이 섞인 문제이다. 유니온 파인드 알고리즘을 하려면, 처음에 parent 배열에 각자 자신의 번호로 초기화시켜준다. 한 줄에 2명씩 입력되므로 최대 노드 개수는 2 * F 개가 된다. 입력을 받을 때, 만약 map.count가 0이라면 idx를 넣어주고 1씩 플러스 해준다. 그다음 unionParent 함수를 실행하고, 다른 집합일 경우..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이과정 bool 함수의 장점을 느꼈던 문제이다. #include #include #include using namespace std; int n, m, x, y; int parent[500001]; // 부모 노드를 찾는 함수 int getParent(int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent[x])..

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 풀이과정 연결되어 있는 노드들 중에 친구비가 작은 친구가 있다면 부모 노드를 바꿔준다. #include #include #include using namespace std; int N, M, k, v, w; int f[10001], parent[10001]; // 부모 노드를 찾는 함수 int getParent(int x) { i..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이과정 1이면 도시들이 연결된 것을 의미하므로 unionParent(i, j) 함수를 실행시켜준다. 그럼 연결된 도시들은 가장 작은 부모 노드를 가지고 있을 것이다. 여행 계획에 있는 도시들을 두 개씩 findParent에 넣어보고 만약에 다른 것이 있다면 연결되지 않은 도시라는 뜻이므로 res를 false로 변경한다. #include #include #include using namespace..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이과정 이 문제는 벨만 포드의 대표적인 기본 문제이다. 그 이유는 타임머신으로 시간을 되돌아가는 경우가 있으므로 가중치가 음수가 될 수 있기 때문이다. 가중치에 음수가 있다면 다익스트라가 아닌, 벨만 포드 알고리즘을 생각해야 한다. 문제에 있는 '시간을 무한히 오래전으로 되돌릴 수 있다면'이라는 말은 '음의 사이클이 존재한다면' 뜻이다..