[백준 / BOJ][Python] 19640 - 화장실의 규칙 https://www.acmicpc.net/problem/19640 19640번: 화장실의 규칙 위와 같이 줄을 선 경우를 생각해보자. (x, y) 는 사원의 근무 일수가 x, 화장실이 급한 정도가 y임을 나타낸다. [x, y]는 해당 사원이 데카임을 의미한다. 즉, 위의 그림에서 데카는 3번 사원이다. www.acmicpc.net 걸린 시간 12 : 58 문제 풀이 문제 그대로 구현하면 되는 시뮬레이션 문제. 단 우선순위 큐를 사용하여 가장 먼저 사라질 원소를 관리해야 한다. 줄의 선두에 있는 사람들을 우선순위 큐에 넣고 삭제, 삽입을 반복하며 문제의 조건을 만족하면 반복을 그만둔다. 구현이 어렵지는 않지만 실수에 주의. 코드 import ..

[백준 / BOJ][Python] 1595 - 북쪽나라의 도로 https://www.acmicpc.net/problem/1595 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net 걸린 시간 07 : 37 문제 풀이 트리의 지름을 구하는 문제. 지문에서 그래프가 트리라는 사실을 알 수 있고, 이후는 단순하게 그래프 탐색 2번으로 트리의 지름을 구하면 된다. 입력이 조금 헷갈릴 수 있다. 코드 import sys from collections import deque input = sys.stdin.readline d..

[백준 / BOJ][Python] 2479 - 경로 찾기 https://www.acmicpc.net/problem/2479 2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 걸린 시간 09 : 22 문제 풀이 간단한 최단 거리 탐색 문제. 가능한 모든 문자열 쌍을 비교하여 해밍 거리가 1이면 간선을 추가한다. 모든 간선의 길이가 1로 같기 때문에, 다익스트라 같은 알고리즘은 필요 없고 단순히 BFS 혹은 DFS로 거리를 구할 수 있다. 코드 import sys, itertools from collection..

[백준 / BOJ][Python] 23254 - 나는 기말고사형 인간이야 https://www.acmicpc.net/problem/23254 23254번: 나는 기말고사형 인간이야 192시간 동안 1번 과목을 35시간, 2번 과목을 43시간, 3번 과목을 30시간, 4번 과목을 17시간, 5번 과목을 37시간, 6번 과목을 30시간동안 공부하면 1, 2, 3, 4, 6번 과목은 100점, 5번 과목은 77점, 7번 과목은 www.acmicpc.net 문제 풀이 우선순위 큐를 사용한 그리디 알고리즘 문제. 1시간 공부로 가장 점수를 많이 올릴 수 있는 최대 힙에 넣어주며 현시점에서 가장 효율적인 것을 택하면 된다. 자세한 내용은 아래 코드 주석으로 설명. 코드 import sys from heapq imp..

[백준 / BOJ][Python] 5419 - 북서풍 https://www.acmicpc.net/problem/5419 5419번: 북서풍 각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다. www.acmicpc.net 문제 풀이 상당히 많은 아이디어가 필요한 문제. 항상 왼쪽 위에서 오른쪽 아래로만 진행할 수 있다는 부분을 어떻게 처리할지가 문제의 풀이를 결정한다. x값을 기준으로 정렬하고, y값은 세그먼트 트리를 통해 현재 위치의 좌표 보다 더 큰 값이 몇 개 있었는지 저장했다. 입력 받은 y값을 그대로 사용하여 세그먼트 트리를 만들면 메모리 초과가 나기에 좌표 압축을 통해 세그먼트 트리의 크기를 줄여줬다. 또한, 재귀적인 방법으로 세그먼트 트리를 구현하면 시간 초과..

[백준 / BOJ][Python] 2170 - 선 긋기 https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 문제 풀이 기초 수준의 스위핑 문제. 우선 시작점과 끝점을 기준으로 선들을 정렬한다. 이후 기존의 선에 추가하여 덧붙일 수 있다면 붙이고, 기존 선의 끝점보다 새로 긋는 선의 출발점이 뒤에 있다면 이전 선의 길이를 정답에 더하고 새로운 선을 긋는다. 코드 import sys input = sys.stdin.re..