본문 바로가기

파이썬12

[알고리즘] 이분 매칭(Bipartite Matching) 1. 이분 매칭 네트워크 플로우(Network Flow) 알고리즘에서 두 정점 사이의 용량이 1이고, 정점이 두 집합으로 구분되는 특수한 경우. 한쪽 그룹을 X, 다른 그룹을 Y라고 할 때, X → Y로의 최대 유량을 구하는 문제. 이때, 각 용량이 1이므로 최대 매칭 수를 찾는 문제로 볼 수 있음. 2. 알고리즘 예시 DFS를 활용하여, 매칭을 하나씩 선택하는 과정을 거친다. 예시는 조금 복잡하지만, 백준 문제의 예시를 가져왔다. 세부적인 예시는 아래와 같다. 다음과 같이 왼쪽 그룹, 오른쪽 그룹에 있는 정점에 대하여 각 선분 중 연결되어 있다. DFS를 응용하여 편하게 최적의 답을 찾을 수 있다. 우선 1번점에서 연결할 수 있는 최적의 점을 찾는다. 그러면, 왼쪽 1번점, 오른쪽 2번점을 연결할 수 .. 2022. 5. 22.
[Python] 백준 1186 직사각형 색칠하기 문제 링크 : https://www.acmicpc.net/problem/1186 1186번: 직사각형 색칠하기 2차원 좌표 평면에 변이 축에 평행한 직사각형 N개가 있다. 직사각형은 1부터 N까지 번호가 매겨져 있다. i번 직사각형의 왼쪽 아래 꼭짓점의 좌표는 (xi,1, yi,1)이고, 오른쪽 위 꼭짓점의 좌표는 (xi www.acmicpc.net 1. 접근 방법 어떻게든 그리디 한 방법이나, 스위핑 같은 방법을 고민했는데, 여러 직 사각형이 겹치는 경우의 해결 방법이 떠오르지 않아, 전체 탐색을 고민했다. 최대 50개 직사각형을 탐색해서 50 * 50으로 각 직사각형마다 겹치는지 확인할 수 있고, 각 직사각형이 최대로 많이 탐색해도 50 * 8 정도라 생각하여 최대 1,000,000번의 탐색으로 가능.. 2021. 11. 1.
[Python] 백준 23257 비트코인은 신이고 나는 무적이다 문제 링크 : https://www.acmicpc.net/problem/23257 23257번: 비트코인은 신이고 나는 무적이다 코인 경력 4년차, 차트에 통달한 찬호는 이전 $N$개의 월봉을 통해 다음 월봉의 절댓값을 예측할 수 있는 아래의 공식을 만들어냈다. (다음 월봉의 절댓값) = 이전 $N$개의 월봉 중 중복을 허용해 www.acmicpc.net 1. 접근 방법 처음에는 XOR 연산에 대해 고민했는데, XOR 연산 처리는 비교적 쉽게 방법을 찾았다. https://stackoverflow.com/questions/52108901/xor-operation-on-three-values XOR operation on three values I have three boolean values. I nee.. 2021. 10. 30.
[Python] 백준 22234 가희와 은행 문제 링크 : https://www.acmicpc.net/problem/22234 22234번: 가희와 은행 가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다. [그림 1] 카운터 직원과 N명의 손님 x번 손님에 대한 정보는 x번 손님의 www.acmicpc.net 1. 접근 방법 간단한 구현 문제인데, 출력을 어떻게 조정할지 많이 고민했다. 구현 과정은 각 손님의 남은 시간을 확인하고, 업무처리를 각각 상황에 맞게 시간을 사용하고, 사용한 시간만큼 출력할 리스트에 저장하면서 진행했다. 2. 풀이 코드 🖥python 코드 from collections import deque import sys input = sys.stdin.readli.. 2021. 10. 28.
[Python] 백준 16888 루트 게임 문제 링크 : https://www.acmicpc.net/problem/16888 16888번: 루트 게임 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 105)가 주어진다. 둘째 줄부터 T개의 줄에 테스트 케이스가 한 줄에 하나씩 주어지며, N(1 ≤ N ≤ 106)이 주어진다. www.acmicpc.net 1. 접근 방법 소수 판정 에라토스테네스 체와 비슷한 방식으로 해결될 것이라 생각이 들었다. 처음에는 각 조건마다 다음 턴을 거꾸로 탐색하는 과정을 반복했는데, 시간이 생각보다 많이 걸려서, 에라토스테네스 체에서도 사용하는 아이디어인, 소수를 발견하면 배수를 모두 소수가 아님을 표시하는 방법을 채용하여 해결했다. 2. 풀이 코드 🖥python코드 import sys input = sys.stdi.. 2021. 10. 28.
[Python] 백준 3109 빵집 문제 링크 : https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 1. 접근 방법 좋지 않은 습관이지만, 문제 카테고리를 먼저 확인하고 접근했고, 그리디라는 카테고리만 생각하여 처음에는 잘못 접근했었다. 결론적으로, 파이프가 생성될 수 있는 시작점, 끝점을 이어가면서 해결했는데, 시작점부터 위에서, 아래로 확인을 하면 기존 파이프 때문에 새로 생성하지 못하는 경우는 없고, 이 방법으로 해결했다. 서로 겹치지 않고, 세 방향 탐색이라는 부분에서 그리디를 카테고리로 .. 2021. 10. 28.
[Python] 백준 1461 도서관 문제 링크 : https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 1. 접근 방법 마지막 책을 옮긴 후 다시 원점으로 돌아올 필요가 없어서 가장 멀리 있는 위치를 마지막에 가는 것은 어렵기 않게 생각했는데, 세부적 구현에서 많이 고민했다. 최적의 위치를 잘 찾는것이 이 문제의 가장 중요한 부분이라 생각한다. 2. 풀이 코드 🖥python 코드 import sys input = sys.stdin.readline MIIS = lambda: map(int, .. 2021. 10. 27.
[Python] 백준 20056 마법사 상어와 파이어볼 문제 링크 : https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 1. 접근 방법 빡빡한 구현이 필요한 상어 문제를 처음 접했을 때는 많이 막막했었다. 코드를 구현하는 과정뿐만 아니라, 적절한 자료구조, 알고리즘을 잘 다루지 못해서 더욱 막막했었던 것 같다. 그러나 시간이 지나고, 문제를 코드로 구현하는 과정과, 자료구조, 알고리즘을 잘 다루기 시작하며 보다 수월하게 문제를 해결하는 것 같다. 2. 풀이 코드.. 2021. 10. 25.
[Python] 소가 길을 건나간 이유 7 문제 링크 : https://www.acmicpc.net/problem/14461 14461번: 소가 길을 건너간 이유 7 30에서 출발해서 가능한 한 빨리 도착하려면 10으로 간 뒤 풀을 먹고, 5로 간 뒤 풀을 먹고, 존의 집인 80으로 가야 한다. 길을 건너는 데 총 16초, 풀을 먹는데 총 15초가 걸린다. www.acmicpc.net 1. 접근 방법 최단거리 문제인데, 사이클과 방문한 위치를 여러 번 방문할 수 있는 문제여서 다익스트라로 접근했다. 여러 차례 시행착오를 거쳤는데, 완전 탐색이 되지 않도록 하는 것이 이 문제의 핵심인 것 같다. 2. 풀이 코드 🖥python 코드 import heapq import sys input = sys.stdin.readline MIIS = lambda: .. 2021. 10. 25.

티스토리툴바