Dev_Diary

https://www.acmicpc.net/problem/1017소수 체크와 이분매칭을 합쳐놓은 문제입니다.우선 각 리스트의 요소에서 더하면 소수가 되는 목록을 만들어 노드간의 연결을 구해줍니다.그 뒤 이분매칭을 해주면 됩니다.전체에서 전체로 이분매칭을 하는 것이 왜 문제의 해답이 되는가 라고 생각할 수 있습니다.문제에서 제시된 첫 번째 예시를 예로 들겠습니다.  connected_with_first : 첫 번째 수가 연결된 수 / connected : 선택된 수가 연결되어있는 인덱스    connected_with_first : 4 / connected : [3, 0, 1, 2, 5, 4]     connected_with_first : 10 / connected : [3, 2, 1, 0, 5, 4] ..

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/1174문제 자체는 DFS 를 사용해 풀면 되지만 '줄어드는 수' 자체에는 자체적인 한계가 있기 때문에 모든 줄어드는 수의 개수가 궁금해졌습니다.나아가 K 자릿수에 해당하는 줄어드는 수의 개수를 구해보고 싶어져 DP 로 해당 문제를 풀었습니다. memo[i][j] 를 자릿수가 i 이고 첫 숫자가 j 인 줄어드는 수의 개수라고 정의하겠습니다.자릿수가 i 이고 첫 숫자가 j 라면 해당 조건에서 줄어드는 수의 경우의 수는자릿수가 i-1 이고 첫 숫자가 j 이하인 줄어드는 수의 경우의 수와 같습니다. 즉 memo[i][j] = sum([memo[i-1][j_in] for j_in in range(len(memo[i-1])) if j_in 라고 할 수 있습..