Dev_Diary

https://www.acmicpc.net/problem/9576오늘도 역시 이분매칭 기본 문제입니다.아래 문제들과 같은 문제이니 참고해주시면 좋을 것 같습니다.https://dev-diary-0717.tistory.com/170https://dev-diary-0717.tistory.com/171https://dev-diary-0717.tistory.com/172import sysinput = sys.stdin.readline# 이분매칭def bimatch(idx, hope_list, visited, connected):    # 이미 체크한 사람이면    if visited[idx]:        return False    # 체크    visited[idx] = True    # 원하는 책 목록 순..

https://www.acmicpc.net/problem/11375https://www.acmicpc.net/problem/11376열혈강호 1 의 경우 단순한 이분매칭입니다.https://dev-diary-0717.tistory.com/170https://dev-diary-0717.tistory.com/171두 문제와 상황과 입력만 다를 뿐 정확히 같은 문제이니 참고하시면 될 것 같습니다. 열혈강호 2 의 경우에는 한쪽이 담당할 수 있는 반대 노드가 n 개일 경우입니다.해당 경우에는 하나의 노드를 할당받을 수 있는 노드에서 n 개의 노드를 할당받을 수 있는 노드 쪽으로 이분매칭을 실행하면 됩니다. 다만 담당할 수 있는 업무가 n 개이므로 케이스를 n 개로 나누어 각각 처리해주면 됩니다. 이 외에도 일반..

https://www.acmicpc.net/problem/2188전형적인 이분매칭 문제입니다. Python" data-og-description="https://www.acmicpc.net/problem/1298전형적인 이분매칭 문제입니다.해당 알고리즘은 DFS 를 기반으로 합니다.우선 순차적으로 노드를 순회하며 매칭 가능한 노드를 연결합니다.다음 노드에서 임의의 노" data-og-host="dev-diary-0717.tistory.com" data-og-source-url="https://dev-diary-0717.tistory.com/170" data-og-url="https://dev-diary-0717.tistory.com/170" data-og-image="https://scrap.kakaoc..

https://www.acmicpc.net/problem/1298전형적인 이분매칭 문제입니다.해당 알고리즘은 DFS 를 기반으로 합니다.우선 순차적으로 노드를 순회하며 매칭 가능한 노드를 연결합니다.다음 노드에서 임의의 노드를 골랐는데 해당 노드가 이미 다른 노드와 연결되어있다면 연결된 노드를 다른 노드와 연결시킬 수 있는지 재귀적으로 탐색하며 최대한 옮긴 뒤 현재의 노드와 고른 노드를 연결시키는 방식입니다.조금 가볍게 말하자면 지하철을 탔을 때 임의의 자리에 앉고 싶을 경우 이미 앉아있는 승객에게 양해를 구해 다른 자리로 옮기게 하는 방식이라고 할 수 있습니다.import sysfrom collections import dequeinput = sys.stdin.readline# 이분 매칭def bima..

https://www.acmicpc.net/problem/1719플로이드-워셜 알고리즘으로도 풀 수 있지만 저는 개인적으로 다익스트라를 좋아하기 때문에 다익스트라로 풀었습니다.일반적인 다익스트라로 하나하나 풀며 최단경로를 구한다면 O(ElogV) 의 복잡도를 갖습니다.또 각 노드마다 순회하므로 V_P_2 의 경우의 수를 곱할 수 있습니다.최악의 경우 E = 10000, V = 200 이므로 10000 * log(200) * 200 * 199 의 시간이 걸리게 되므로 대충 정수만 계산해도 제한시간 2 초는 말도 안됨을 알 수 있습니다.즉 다른 방법을 생각해야 합니다. 다익스트라 알고리즘이 작동할 때 기본적인 목표는 A-C 의 최적화된 경로를 찾는 것 이지만 중간에 있는 B 를 거치게 될 경우 A-B / B..

https://www.acmicpc.net/problem/1922최소 스패닝 트리에 관한 문제입니다.저는 크루스칼 알고리즘을 통해 풀었습니다. 크루스칼 알고리즘은 기본적으로 그리디 알고리즘에 기반을 두고 있습니다.우선 엣지들을 코스트를 기준으로 정렬합니다.가장 낮은 코스트를 가진 엣지들을 우선적으로 선택하는데, 선택한 엣지로 인해 순환이 생기지 않는다면 선택하고 순환이 생긴다면 선택하지 않습니다.import sysinput = sys.stdin.readline# Union-Finddef Union(root_list, node_1, node_2):    # 각 루트 노드    root_1 = Find(root_list,node_1)    root_2 = Find(root_list, node_2)    # ..

https://www.acmicpc.net/problem/1461M 권의 책을 한번에 가져올 수 있다는 말은 M 권의 책을 옮기는 과정 중 0 을 지나지 않는다면 먼 거리에 있는 거리 x 2 를 한 것이 해당 과정 중 움직인 거리라는 말이 됩니다.더불어 0 을 지나게 된다면 책을 들 수 있는 횟수가 초기화되기 때문에 시퀀스의 중단을 의미하기도 합니다. 때문에 0 을 지나지 않고 음수의 인덱스와 양수의 인덱스에 있는 책을 분리해 생각할 수 있습니다. 마지막에 있는 책을 옮길 때에는 다시 돌아오지 않아도 되기 때문에 가장 멀리 있는 책을 마지막 에 옮기는 것이 논리적으로 가장 짧게 이동할 수 있는 방법입니다.즉 마지막에 (가장 멀리있는 책, 가장 멀리있는 책과 같은 부호를 지니며 다음으로 멀리있는 책, ....

https://www.acmicpc.net/problem/1229DP 를 사용해 풀 수 있습니다.우선 N 보다 작은 육각수를 모두 구해줍니다.육각수는 N x (2N - 1) (N >= 1) 의 규칙을 띄고 있으니 반복문을 통해 구해줄 수 있습니다. 육각수의 최소 개수를 알고 싶은 타겟 i 보다 작은 육각수들을 순회하며memo[i - 육각수] + 1 의 개수들을 비교해 최솟값을 기록하면 됩니다.+ 1 은 육각수를 하나 고르면 해당 육각수 1 개를 더해주는 것입니다.import sysfrom bisect import bisect_leftinput = sys.stdin.readlinedef solution(N):    # N 보다 작은 육각수 리스트    hex_list = [0]    # 카운트    i =..

https://www.acmicpc.net/problem/1146브루트 포스나 BFS 의 식으로도 풀 수 있지만 시간제한에 걸리게 됩니다.다른 방법을 찾아봅시다. 우리는 N 명의 학생을 줄세워야 합니다.그 중 번호가 가장 큰 N 번째 학생을 P 번째 순서에 줄 세우는 경우를 생각해보겠습니다.그럼 남은 N-1 명의 학생을 줄 세워야 하는데, 어차피 수의 대소만이 중요하기 때문에 지그재그 패턴만 맞으면 어떤 학생이 어디에 서던 중요하지 않습니다.즉 N 번째 학생을 P 번째 세우고 양 옆에 남은 학생들을 다시 줄세우는 작은 단계로 쪼갤 수 있습니다.즉 이 문제를 DP 로 풀 수 있습니다. N 명의 학생 중 P 번째 자리에 N 번째 학생을 줄세운다고 생각하겠습니다.해당 경우를 A_NP 라고 부르겠습니다. P 가..

https://www.acmicpc.net/problem/1106전형적인 냅색 알고리즘 문제입니다.다만 최대 비용을 설정할 때 100원에 1명을 모집하는 경우가 최악이므로 최대 비용은 목표인원 x 100 으로 설정하주면 해결할 수 있습니다.import sysinput = sys.stdin.readlinedef solution(C, N, data_list):    # 최대 비용 = 100 원에 1명씩 C 명을 모집할 경우 = 100xC 원    max_cost = 100*C    # 냅색    knapsack = [[0 for _ in range(N)] for __ in range(max_cost+1)]    # 직전 비용까지의 고객 수 최댓값    # 현재 비용에서 필요 비용을 뺀 비용까지의 고객 수 최..