Dev_Diary

https://www.acmicpc.net/problem/10254지난번에 포스팅한 문제와 같은 알고리즘을 사용하지만 이번에는 단순 계산으로는 시간초과가 발생하므로 회전하는 캘리퍼스 알고리즘으로 문제를 풀었습니다. 회전하는 캘리퍼스는 특정한 도형에서 가장 먼 두 꼭지점을 찾는데 아주 유용한 알고리즘입니다.어떠한 점 A 에서 가장 먼 점 B 를 구할 때 점 A 를 지나는 직선 A' 를 정하면 그 직선과 평행하고 점 B 를 지나는 직선 B' 는 항상 존재합니다. 또한 직전의 점 B- 와 점 B 를 잇는 벡터 B'- 와 점 B 와 직후의 점 B+ 를 잇는 벡터 B'+ 는 각각 B' 와 이루는 외적값의 부호가 반대입니다.즉 (B-, B) : B'- / B' 와 B' / (B, B+) : B'+ 가 이루는 외적값..

https://www.acmicpc.net/problem/9240볼록껍질 + 회전하는 캘리퍼스 문제이지만우선 볼록껍질만 구하면 단순 계산으로 모든 볼록껍질에 속하는 점들 사이의 거리를 비교해도 풀 수 있습니다. 볼록껍질의 경우 C++" data-og-description="https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 " data-og-host="dev-diary-0717.tistory.com" data-og-source-url="https://dev-diary-0717.tistory.com/141..

https://www.acmicpc.net/problem/11405지난 문제와 같이 최소 비용 최대 유량 문제입니다.SPFA 알고리즘과 네트워크 플로우 알고리즘을 함께 사용해 풀었습니다.최대 비용을 구할 때 전달된 책의 수를 곱해주어야 합니다. import sysfrom collections import dequeinput = sys.stdin.readline# SPFAdef spfa(start, N, M, graph, flowable): # 방문 목록 visited = [-1 for _ in range(1+M+N+1)] visited[start] = start # 최단거리 min_dists = [float('inf') for _ in range(1+M+N+1)] min_..

https://www.acmicpc.net/problem/14286최대 유량 최소 컷 정리를 이용한 최대 유량 문제입니다.최소 컷을 구하기 위해 간선을 차단할 때는 경로 중 가장 코스트가 작은 간선을 차단합니다.그 과정이 최대 유량 문제에서 유량을 흘릴 때 경로에서 가장 작은 코스트를 흘려주는 것과 같기 때문에 결국 최소 컷 문제의 해와 최대 유량 문제의 해는 같다고 볼 수 있습니다. 다만 양방향 간선이기 때문에 노드를 들어오는 노드와 나가는 노드로 쪼개어 풀면 수월하게 풀 수 있습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(n, m, edges, s, t): # 최대 유량 최소 컷 # 최소 컷..

https://www.acmicpc.net/problem/11408열혈강호 시리즈 다섯번째 문제입니다.이번 문제 또한 최대 유량 문제이지만 그 중에서 최소 코스트를 구하는 최소 비용 최대 유량(MCMF) 문제 입니다. 거창한 이름과는 다르게 해결 방법은 크게 새롭지 않습니다. 최대 유량 문제에서 길을 탐색할 때 모든 엣지의 코스트가 1 이었기 때문에 BFS 를 사용해 단순히 경로만 파악했다면 코스트가 생겼기 때문에 최단 코스트가 발생하는 경로를 찾아주면 됩니다. 최단 경로를 구한다면 가장 간단하게 다익스트라 알고리즘을 생각할 수 있지만 최대 유량 문제에서 코스트를 계산할 때에는 음의 경로로 이동할 경우 음의 코스트를 더해주어야 하기 때문에 다익스트라는 사용할 수 없습니다. 때문에 음의 경로가 존재해도 경..

https://school.programmers.co.kr/learn/courses/30/lessons/258709?language=python3모든 경우의 수를 계산해보면 풀 수 있는 문제입니다.combinations, prodect 함수를 잘 사용하면 상당히 짧은 코드로 풀 수 있습니다.또 이긴 경우의 수를 계산할 때, 이분탐색 라이브러리인 bisect 를 사용하면 보다 편하게 구할 수 있습니다.from itertools import combinations, productfrom bisect import bisect_leftdef solution(dice):    # 주사위의 개수    n = len(dice)    # 주사위들의 경우의 수    dices_case = list(product(rang..

https://www.acmicpc.net/problem/2051역시 최소 버텍스 커버 + 이분매칭 문제입니다.다만 이분매칭을 단순히 활용하는 문제가 아닌 좀 더 본질에 가까운 문제라고 할 수 있습니다.바로 최소 버텍스 커버의 해 자체를 구하는 문제이기 때문입니다. 즉 최소 버텍스 커버 문제를 만족하는 노드들을 구하는 문제입니다.이는 쾨닉의 정리에 포함되어 있는 부분인데 방법은 이렇습니다. 1. 이분매칭을 통해 매칭되는 노드 / 엣지를 구합니다.2. 엣지를 뻗어 나가는 노드군을 L / 엣지가 도달하는 노드군을 R 이라고 했을 때, L 에 속한 노드 중 매칭되지 않은 노드를 L*, R 에 속한 노드 중 매칭된 노드를 R* 이라고 정하고 구해줍니다.3. L* 에서 시작해 연결된 노드들을 순회할텐데, L* 에..

https://www.acmicpc.net/problem/2414최소 버텍스 커버 문제 + 이분매칭 문제입니다. Python" data-og-description="https://www.acmicpc.net/problem/1867'해당 문제는 이분매칭 알고리즘을 사용하는 문제입니다.'라고 말하면 왜인지 다들 화가 날 것 같습니다. 저는 화가 났습니다. 왜냐하면 이 문제는 단순한 이분매칭 " data-og-host="dev-diary-0717.tistory.com" data-og-source-url="https://dev-diary-0717.tistory.com/158" data-og-url="https://dev-diary-0717.tistory.com/158" data-og-image="https://..

https://www.acmicpc.net/problem/3713이번 문제도 최소 버텍스 커버 + 이분매칭 콤보 문제입니다.만날 수 있는 노드를 모두 찾은 뒤 해당 노드들을 제거하면 됩니다.import sysinput = sys.stdin.readline# 이분매칭def bimatch(idx, connectable, connected, visited):    # 이미 방문했으면 패스    if visited[idx]:        return False        # 방문 체크    visited[idx] = True    # 순회    for node in connectable[idx]:        # 만날 수 있거나 뺏을 수 있으면        if connected[node] 0 or bima..

https://www.acmicpc.net/problem/1014https://www.acmicpc.net/problem/11014해당 문제는 최소 버텍스 커버 문제입니다. 해당 문제에서 학생 -> 학생 의 버텍스 (엣지) 는 커닝의 가능성으로 볼 수 있습니다.즉 모든 버텍스를 커버하면 커닝의 가능성이 있는 모든 위치를 탐색하는 것과 동일합니다.그러므로 모든 버텍스를 커버하고 남는 자리에 학생을 앉히면 커닝을 당하거나 할 가능성이 없습니다. 해당 문제에서 특정 위치에 학생을 앉힌다고 가정하면 해당 학생과 같은 열에 있는 학생은 커닝을 당할일도 할 일도 없습니다. 즉 어떤 학생에게서 다른 학생에게 향하는 버텍스는 짝수 -> 홀수 / 홀수 -> 짝수 의 두 경우로 나뉩니다. 그러므로 해당 문제의 그래프는 홀..