o_onn5

이분매칭 알고리즘이란? 2개의 정점 그룹이 있을 때, 그룹에서 그룹으로 정점의 최대 매칭을 찾는 알고리즘입니다. 아래와 같은 두 그룹의 정점이 있다고 합시다. 각 그룹을 연결할 수 있는 간선의 정보입니다. A: 2, 5 B: 2, 3, 4 C: 1, 5 D: 1, 2, 5 E: 2 위 간선들 중에서 정점을 한 번만 사용해서 최대 매칭을 이룰 수 있게 만드는 것이 이분매칭 알고리즘의 목적입니다. 알고리즘은 깊이 우선 탐색(DFS)로 진행이 되며, 과정은 아래와 같습니다. 우선 A와 매칭이 가능한 1을 매칭 시킵니다. 현재 연결 정보 A -- 2 B -- C -- D -- E -- A는 매칭했으니 B를 보도록 합시다. B를 2와 매칭시키려했는데 이미 A가 차지했네요. 이런 경우는 이전에 매칭됐던 A가 양보를..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소스패닝 트리를 만드는 크루스칼 문제다. 전형적인 크루스칼 문제라서 개념을 아는 사람이라면 쉽게 풀 수 있다. import math # 특정 원소가 속한 집합 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) ret..

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 Topology(위상정렬) 알고리즘 문제다. 위상정렬의 알고리즘은 다음과 같이 진행된다. 1. indegree(진입차수)가 0인 노드를 찾고 큐에 넣는다. 2. 큐에서 노드를 꺼내고 해당 노드와 연결되는 모든 노드를 탐색한다. 3. 탐색되는 노드들의 indgree 값을 1씩 감소시킨다. 4. 탐색된 노드들 중 indgree 값이 0인 노드를 큐에 넣는다...

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net deque에 대해서 알아볼 수 있는 문제다. 처음에는 R을 받을 때마다 q.reverse()를 통해 역순정렬을 해서 시간초과가 나왔다. cnt 변수를 하나 만들어서 R을 받을 때마다 1씩 증가시키며 마지막에 한 번만 reverse를 해주면 되는 문제였다. 이게 핵심이었던 것 같고, 공부하면서 reverse(), rotate(), 리스트와 덱의 차이점 등을 알 수 있어서 좋은 문제라 생각한다. 끗 from collections import deque de..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 크루스칼 문제다. 일반적인 크루스칼 개념을 적용시켜서 푸는 것은 동일하다. 각 노드의 x축 y축 z축 차이를 탐색한 뒤에 절댓값이 가장 작은 가중치를 선택하면 된다. 그렇다고 모든 노드를 하나씩 비교해보면 시간초과가 난다. 따라서 간선의 가중치와 노드를 저장한 뒤에 우선순위 정렬을 시행한 뒤 비교해줘야한다. 정리해보면 1. x축 y축 z축의 리스트를 하나 만든다. ..

최소신장트리(MST, MinimumSpanningTree)를 구하는 알고리즘 중 하나이다. 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 없어야하고 간선의 가중치가 최소가 되는 트리를 의미한다. 아래의 그림이 바로 그런 예시다. 알고리즘은 대략적으로 다음과 같다. 1. 가장 작은 가중치의 간선 탐색 2. 사이클이 생기지 않는 노드인지 확인 3-1. 사이클이 생긴다면 pass 3-2. 사이클이 생기지 않으면 해당 간선 리스트에 저장 아래 코드는 MST의 최소 가중치를 구하는 코드다. # 특정 원소가 속한 집합 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 최근에 DP를 배우고 DP문제에 재미들렸다. DP가 유독 생각하는 시간이 코드 수정하는 시간보다 많은 알고리즘인 것 같다. DP 코드가 대체적으로 길지 않은데 어렵다보니 매력적인 알고리즘이다. 이 동전 문제도 DP문제 중 대표적인 유형이라고 볼 수 있을 것 같다. 이전에 공부했던 내용이라 금방 풀었음. n,k=map(int,input().split()) coins = [] for _ in range..