ps45 [알고리즘] 이분 매칭(Bipartite Matching) 1. 이분 매칭 네트워크 플로우(Network Flow) 알고리즘에서 두 정점 사이의 용량이 1이고, 정점이 두 집합으로 구분되는 특수한 경우. 한쪽 그룹을 X, 다른 그룹을 Y라고 할 때, X → Y로의 최대 유량을 구하는 문제. 이때, 각 용량이 1이므로 최대 매칭 수를 찾는 문제로 볼 수 있음. 2. 알고리즘 예시 DFS를 활용하여, 매칭을 하나씩 선택하는 과정을 거친다. 예시는 조금 복잡하지만, 백준 문제의 예시를 가져왔다. 세부적인 예시는 아래와 같다. 다음과 같이 왼쪽 그룹, 오른쪽 그룹에 있는 정점에 대하여 각 선분 중 연결되어 있다. DFS를 응용하여 편하게 최적의 답을 찾을 수 있다. 우선 1번점에서 연결할 수 있는 최적의 점을 찾는다. 그러면, 왼쪽 1번점, 오른쪽 2번점을 연결할 수 .. 2022. 5. 22. [Python] 백준 3806 S를 T로 문제 링크 :https://www.acmicpc.net/problem/3806 3806번: S를 T로 첫째 줄에 테스트 케이스의 개수 C (C ≤ 200)가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 '0', '1', '?'로 이루어진 S, 둘째 줄에는 '0', '1'로 이루어진 T가 주어진다. 두 문자 www.acmicpc.net 1. 접근 방법 접은 방법을 조금 고민했는데, 가능한 조건이 많지는 않지만, BFS나 DP로는 적합하지 않을 것 같아 그리디한 방식을 탐색했다. 2. 풀이 코드 🖥python 코드 링크 :https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/3000/3806.py GitHub - mintropy/PS.. 2022. 4. 17. [Python] 2212 센서 문제 링크 : https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 1. 접근 방법 각 값이 아니라, 각 값의 차이 중 최솟값을 뽑아내는 그리디 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2200/2212.py GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장소입니다. BO.. 2022. 3. 25. [Python] 백준 2533 사회망 서비스(SNS) 문제 링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 1. 접근 방법 DP와 DFS를 고민했는데, 나는 둘 다 사용한 방법으로 가닥을 잡았다. 문제를 해결하고 DP로만 해결하는 등의 풀이도 고민했지만, 잘 되지는 않아 시간은 조금 오래 걸렸지만, 해결했다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2500/2533.py Git.. 2022. 3. 22. [Python] 백준 13335 트럭 문제 링크 : https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 1. 접근 방법 queue를 활용하여 쉽게 해결할 수 있는 문제. 리스트를 활용한다면, 슬라이싱으로 유사하게 구현할 수 있을 것 같다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/13000/13335.py GitHub - mintropy/ba.. 2022. 3. 21. [Python] 백준 2866 문자열 잘라내기 문제 링크 : https://www.acmicpc.net/problem/2866 2866번: 문자열 잘라내기 첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자 www.acmicpc.net 1. 접근 방법 전체 탐색을 하기에는 많은 것 같고, 탐색을 줄이며 해결하기 위해 이분 탐색을 선택했다. 각 문자열이 중복인지 확인하기 위해 집합을 사용했다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2800/2866.py GitHub - mintropy/bae.. 2022. 3. 13. [Python] 백준 11000 강의실 배정 문제 링크 : https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 1. 접근 방법 시작 끝 시간을 기반으로 간단한 그리디라 생각했는데, 문제를 다시 읽고 보니 전체 강의 실수를 확인하는 조금 번거로울 수 있는 문제였다. 이를 해결하기 위해 heap을 활용하여 가장 빨리 끝나는 시간 기준으로 고민했다. 2. 풀이 코드 🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/11000/11000.py 📕코드 해설 시작 시간 기준으로 오.. 2022. 2. 27. [Python] 백준 13164 행복 유치원 문제 링크 : https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 1. 접근 방법 정렬을 우선적으로 했고, 그 이후 어떻게 짝을 지어갈지 결정해야 하는데 그 방법에서 조금 고민을 했다 2. 풀이 코드 🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/13000/13164.py GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장.. 2022. 2. 27. [Python] 백준 21924 도시 건설 문제 링크 : https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 1. 접근 방법 오랜만에 MSP 문제를 접근하여 방법이 잘 떠오르지 않아 여러 가지 방법을 시도하다가, 결국 union-find로 해결했다 2. 풀이 코드 🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob.. 2022. 2. 21. 이전 1 2 3 4 5 다음
