Dev_Diary

https://www.acmicpc.net/problem/32349이분매칭을 사용해 풀 수 있는 문제입니다.어차피 목표 위치가 상하좌우 방향의 위치에 인접해 있는것이 아니면 두 번 이상 이동해야 하기 때문에 구슬을 들었다 놓는 경우와 이동 횟수가 같습니다. 즉 한 칸을 이동하는 경우에만 최적화를 한 뒤 나머지는 모두 들어서 옮기면 됩니다. 우리가 주목해야 하는 경우는 두 가지 인데1. 초기 위치에는 구슬이 있지만 구슬이 없기를 원하는 경우 2. 초기 위치에는 구슬이 없지만 구슬이 있기를 원하는 경우 우리는 1 -> 2 로 구슬을 옮기길 원하기 때문입니다. 즉 1 과 2 를 탐색해 정리한 뒤 1 과 2 의 인덱스가 인접해 있는 경우를 찾아 연결 가능 목록에 넣어줍니다.후에 이분매칭을 통해 최대한 많이 한번..

https://www.acmicpc.net/problem/15681트리를 순회하는 문제입니다.우선 양방향 그래프를 구성한 뒤 루트 노드에서 시작해 BFS 를 통해 트리를 만들어줄 수 있습니다. 자손의 수는 자식의 자손의 수를 모두 합한 것에 자식의 수를 합친 것과 같습니다.즉 더 작은 경우로 나누어 계산할 수 있고 DP 로 풀 수 있습니다.import sysfrom collections import dequesys.setrecursionlimit(1000000)input = sys.stdin.readline# 자식 노드의 수를 찾는 함수def cal_child(tree, childs, node):    # 자손의 수가 구해져 있지 않으면    if childs[node] 0:        # 자식이 없..

https://www.acmicpc.net/problem/1647최소 스패닝 트리 문제입니다.우선 모든 마을이 연결되게 하는 최소 코스트를 구한 뒤 가장 코스트가 큰 길을 지우면 코스트 합이 가장 작은 두 개의 마을이 됩니다.import sysinput = sys.stdin.readline# 크루스칼 알고리즘을 위한 Union-Find# Uniondef Union(root_list, node_1, node_2):    # 각 노드의 루트    root_1 = Find(root_list, node_1)    root_2 = Find(root_list, node_2)    # 각 루트가 같으면    if root_1 == root_2:        return False    # 다르면 루트가 작은쪽으로 병..

https://www.acmicpc.net/problem/1197말 그대로 최소 스패닝 트리 문제입니다.크루스칼 알고리즘을 통해 쉽게 풀 수 있습니다.다만 recursion error 가 발생할 때에는 연결된 엣지의 수가 N-1 을 초과하지 않았는지 체크해주면 됩니다. import sysinput = sys.stdin.readline# 크루스칼 알고리즘을 위한 Union-Find# Uniondef Union(root_list, node_1, node_2):    # 각 노드의 루트    root_1 = Find(root_list, node_1)    root_2 = Find(root_list, node_2)    # 각 루트가 같으면    if root_1 == root_2:        return F..

https://www.acmicpc.net/problem/2467용액의 입력은 정렬되어 있다는 점을 활용해 투포인터로 풀 수 있습니다. l 값은 증가할수록 합이 증가하고r 값은 감소할수록 합이 감소합니다. 합이 0 보다 크면 합을 줄여야 하므로 r 값을 감소시키고합이 0 보다 작으면 합을 늘여야 하므로 l 값을 증가시키면 됩니다.import sysinput = sys.stdin.readlinedef solution(fluids):    ## 투포인터    l = 0    r = len(fluids)-1    # 최소 절댓값    min_abs_sum_nums = float('inf')    # 합이 0 이거나 두 포인터가 교차할 때 까지    while l r:        # 합        sum_..

https://www.acmicpc.net/problem/2787 '수열의 특정 인덱스에 특정한 수들이 들어갈 수 있고 가능한 많은 수를 인덱스에 배치해라'즉 흔한 이분매칭 문제입니다. 다만 헷갈릴 수 있는 부분이 있다면'[x, y] 구간의 최대/최솟값이 v 이다' 라는 말은 [x, y] 구간에 v 가 꼭 존재해야 한다는 말입니다.또 나머지 구간에는 v 가 존재할 수 없다는 말과 같습니다.  이를 신경써서 항상 이분매칭을 풀던 것 처럼 노드 -> 노드 연결 가능성만 체크해주면 됩니다.import sysinput = sys.stdin.readline# 이분매칭def bimatch(idx, range_list, connected, visited, excluded_idxs):    # 이미 방문한 노드면 탐색..

https://www.acmicpc.net/problem/2191이분매칭 문제입니다.단순하게 연결된 노드만 구해준다면 기본적인 이분매칭입니다.import sysfrom math import sqrtinput = sys.stdin.readline# 이분매칭def bimatch(idx, connectable, connected, visited):    # 이미 방문한 노드면 탐색 안함    if visited[idx]:        return False    # 방문 체크    visited[idx] = True    # 탐색 가능한 노드 탐색    for node in connectable[idx]:        # 연결할 수 있거나 연결된 노드를 다른 노드로 옮길 수 있다면        if conne..

https://www.acmicpc.net/problem/3295해당 문제는 이분매칭으로 풀 수 있는 문제입니다.이분매칭 문제는 보통 왜 이분매칭으로 풀 수 있는지 이해하는게 어렵습니다. 문제에서 보면 선형 배열은 K-1 의 가치를, 링은 K 의 가치를 갖습니다.그런데 이 수치는 해당 배열과 링이 갖고있는 노드의 수와 같음을 알 수 있습니다.결국 해당 문제는 '노드끼리 가장 많이 연결할 수 있는 경우를 찾아라' 를 요구하고 있습니다. 또 선형배열과 링은 하나의 노드 안에 들어가는 엣지와 나가는 엣지가 모두 하나 이하로 존재합니다. 즉 연결된 모든 노드는 1 대 1 매칭이 된다는 말입니다. 정리해보자면 '노드를 연결할 건데 모든 노드끼리는 1 대 1로 매칭이 되고 해당 조건 아래에서 가장 노드를 많이 연결..

https://www.acmicpc.net/problem/11378https://dev-diary-0717.tistory.com/176기존에 포스팅한 열혈강호 3 과 같은 문제라고 볼 수 있습니다.다만 달라진 점은 한 사람이 추가로 담당할 수 있는 일이 1 개가 아닌 K 개가 된 것인데 추가 노드에서 직원 노드로 간선을 만들 때 흐를 수 있는 유체의 양을 K 로 설정하면 K 번 모두 탐색을 하며 최대치까지 부여하기 때문에 해결됩니다.import sysfrom collections import deque, defaultdictinput = sys.stdin.readlinedef solution(N, M, K, hope_list):    # 흐를수 있는 유체의 양    flowable = defaultdic..

https://www.acmicpc.net/problem/11377열혈강호 2 까지는 이분매칭으로 풀었지만 해당 문제는 네트워크 플로우 알고리즘 중 에드몬드 카프 알고리즘으로 풀었습니다.아마 2 개의 일을 할 수 있는 K명을 정하는데 큰 지장이 있을 것이라고 생각합니다.모두 두 개씩 일을 할 수 있을 때 (열혈강호 2) 이분 매칭을 두 번 돌렸던 것을 생각해 우선 모두에게 일을 하나씩 되는대로 할당하고 추가적으로 일을 할당하는 방식으로 진행했습니다. 문제에서 제시한 예제를 그래프로 만들면 이렇게 됩니다.해당 그래프에서 이동하는 경로는 0 - 1 - 6 - 120 - 2 - 7 - 120 - 3 - 10 - 120 - 11 - 1 - 8 - 12 으로 우선 모든 직원들에게 일을 할당한 뒤 추가 노드에서 일..