알고리즘/알고리즘 문제 풀이

(JAVA) 백준 2805번 - 나무 자르기

문제 링크: https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 처음에는 브루트 포스를 사용하여 아래와 같이 풀이해 보았다. import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { public static void main(String[] a..

(C++) 백준 9372번 - 상근이의 여행

문제 링크 : https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 풀이 상근이가 최소한의 수의 비행기로 모든 나라를 돌아다니는 것은 최소 신장 트리를 순회하는 것과 동일하다. (정점 - 1) 개의 간선이 최소 신장 트리에 존재하므로, 비행기도 (정점 - 1) 개를 타게 된다. #include int t, n, m, a, b; using namespace std; int main(){ cin >> t; while..

(C++) 백준 1368번 - 물대기

문제 링크 : https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 풀이 새로운 우물을 파는 것은 새로운 정점을 하나 추가하여 그에 맞는 cost를 가지는 간선을 추가하는 방식으로 진행하였다. Union-Find를 사용해서 크루스칼 알고리즘을 구현하여 최소 신장 트리의 크기를 구해보았다. #include #include #include using namespace std; tuple t[100005]; int n, e,..

(C++) 백준 1197번 - 최소 스패닝 트리

문제 링크 : https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 Union-Find를 사용해서 크루스칼 알고리즘을 구현하여 최소 신장 트리의 크기를 구해보았다. 정렬 시에 가장 처음에 나타난 값을 기준으로 정렬하기에, cost 값을 튜플에 맨 앞에 위치시켜야 한다는 점을 간과하여 오랜 시간을 낭비하기도 했다. #include #include #include using namespace std; ..

(C++) 백준 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 풀이 indegree라는 자신에게 들어오는 간선의 수를 저장하는 배열을 사용하여, indegree가 0인 경우에만 큐에 넣어 출력하는 방식으로 풀이하였다. indegree가 0이 아닌 경우에는 연결된 정점을 방문할 때마다 indegree를 1씩 줄여나가며, 0이 되는 순간 큐에 들어가도록 한다. #include #include using n..

(C++) 백준 1260번 - DFS와 BFS

문제 링크 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 그래프에서의 DFS와 BFS를 구현하는 문제이다. DFS는 Stack을, BFS는 Queue를 사용해서 풀력 형식에 맞게 그래프의 정점을 하나씩 순회하도록 구현하면 된다. #include #include #include #include using namespace std; vector gp[1002]; int visited[1002]; qu..

(C++) 백준 11724번 - 연결 요소의 개수

문제 링크 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 방향이 없는 그래프를 BFS 하여 풀이하였다. BFS를 사용하여 하나의 정점부터 차례대로 순회하면 이것들은 하나의 연결 요소가 된다. 그렇기에 출발점을 정점 하나하나로 두고, 방문했는지 여부를 사용하면 연결 요소의 수까지 파악할 수 있다. #include #include using namespace std; vect..

(C++) 백준 1715번 - 카드 정렬하기

문제 링크 : https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 우선순위 큐와 그리디 알고리즘을 사용하여 풀이하였다. 카드 비교 횟수를 최소화하려면 가장 개수가 적은 두 묶음씩 먼저 합치면서 진행하면 된다. 최소 힙을 사용해서 가장 갯수가 적은 묶음 두 개를 합친 후, 다시 이를 최소 힙에 넣고 앞의 과정을 반복하는 방식으로 풀이하였다. #include #include using namespace std; int n, tota..

(C++) 백준 11286번 - 절대값 힙

문제 링크 : https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 우선순위 큐와 커스텀 비교 함수를 사용하여 풀이하였다. 우선순위 큐에서는 가장 뒤에 위치한 값이 가장 우선순위가 높다는 것이 풀이하면서 상당히 헷갈리게 만들었다. 또한 우선순위 큐에서 비교 함수를 사용하기 위해서 아래와 같이 cmp라는 클래스와 내부의 operator()를 사용해야 한다는 사실도 새롭게 알게 되었다. #include #include usin..

(C++) 백준 1620번 - 나는야 포켓몬 마스터 이다솜

문제 링크 : https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제 풀이 해시(unordered_map)를 사용하여 풀이하였다. 포켓몬 이름(string)을 key로 하고, 도감번호(int)를 value로 하는 unordered_map을 생성 후, 입력받는 대로 저장을 한다. 동시에 도감번호를 index로 하는 배열에도 포켓몬 이름을 저장한다. 다음으로 질문이 들어오는데 만약 이것이 int라면 당연히 앞 글자가 di..