알고리즘

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

(C++) 백준 7785번 - 회사에 있는 사람

문제 링크 : https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 문제 풀이 해시를 이용한 풀이이다. unordered_set이라는 다소 생소한 STL을 사용하였다. 정렬은 cmp라는 cutom 비교 함수를 만들어서 사전순의 역순으로 정렬하였다. #include #include #include #include using namespace std; int n; string person, act; unordere..

(C++) 백준 1806번 - 부분합

문제 링크 : https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 풀이 투 포인터를 이용하여 풀이하면 된다. 여기서는 st와 en 두 개의 포인터를 사용한다. 1. 배열 A를 입력받는다. 2. en을 1씩 증가시키면서 total의 값이 S 이상일 경우, 그때 그 값이 최솟값인지 체크를 한다. 만약 en이 N이 되면 배열 끝까지 다 순회한 것이므로 더 이상 체크할 것이 없기 때문에 break 한다. 3. st를 1만큼 증가시키고,..