백준
[백준] 16724. 피리 부는 사나이 - Python
[Gold III] https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 풀이 Union-Find(Disjoint Set)를 이용하여 풀 수 있는 문제라는 것만 캐치한다면, 어렵지 않게 풀이할 수 있었던 문제. NxM 지도의 각 칸에 번호를 지정하고, (좌표가 r, c 일 때, 칸의 번호를 r * M + c 로 지정.) 그 번호를 기반으로 root를 저장하는 dictionary를 초기화. Union, Find 함수..
[백준] 13164. 행복 유치원 - Python
[Gold V] https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 풀이 [백준] 2212. 센서 - Python 와 거의 동일한, 간단한 Greedy 문제. 모든 원생의 키를 오름차순으로 정렬 후, 옆 사람과의 키 차이를 저장하고, 키 차이를 다시 오름차순으로 정렬 후, 맨 뒤에서부터 (K-1)개를 빼고 모두 더하면 된다. K개의 조로 나눈다는 것은, 중간에 키 차이를 무시하고 넘어갈 수 있는 횟수가 K-1번이라는 뜻이라고 생각할 수 있다...
[백준] 17089. 세 친구 - Python
[Gold V] https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net 풀이 Brute-Force로 모든 경우를 순회하며 검사하면 되는 문제. 다만 정말 생각없이 3중첩 for문으로 구현한다면, N(3 ≤ N ≤ 4,000) 이기 때문에, O(N^3) 으로는 시간초과를 받을 수밖에 없다. 아래와 같이 순회를 돌게 되면, line 17~20 의 두 번째 for문까지의 시간 복잡도가, "사람의 수"가 아닌 "친구..
[백준] 20056. 마법사 상어와 파이어볼 - Python
[Gold IV] https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 풀이 지시하는 대로 구현하면 어렵지 않게 풀이할 수 있는 구현 문제. 파이어볼이 이동할 때 MOD연산을 활용하는 것과 질량이 0이 된 파이어볼을 제대로 제거하는 것에 유의하자. AC. N, M, K = map(int, input().split()) # 방향 (r이동량, c이동량) directions = [[-1, 0], [-1, 1], [0..
[백준] 14719. 빗물 - Python
[Gold V] https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 아이디어를 생각해내기가 조금 어렵지만, 그것만 생각해낸다면 쉽게 풀이할 수 있는 문제. 모든 열에 대하여, 그 칸의 왼쪽과 오른쪽 열의 최댓값을 구하고, (line 7, 8) 왼쪽과 오른쪽의 최댓값 중 더 작은 것에서 현재 열의 칸 수를 빼면 받을 수 있는 빗물의 양이 된다. (line 9) AC. H, W = map(int, input().split()) ..
[백준] 1922. 네트워크 연결 - Python
[Gold IV] https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 기본적인 MST(Minimum Spanning Tree) 문제. Kruskal 알고리즘을 통해 MST를 구현하였다. 응용된 것 없이 MST를 구현하기만 하면 되는 문제이므로 설명은 생략. AC. from collections import deque # input N = int(input()) M = int(input()) root = {i: i for i in range(1, N+1)} edges = [] for _ in range(M): a, b, c = map..
[백준] 1365. 꼬인 전깃줄 - Python
[Gold II] https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 풀이 Binary Search를 이용해 O(NlogN)으로 풀이하는 LIS 문제. 아래 문제들과 거의 동일하다. 따로 설명을 적지 않겠음. [백준] 2565. 전깃줄 - Python [백준] 12015. 가장 긴 증가하는 부분 수열 2 - Python AC. import bisect from collections import deque import sys input..
[백준] 2568. 전깃줄 - 2 - Python
[Platinum V] https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 풀이 이분탐색을 이용한 LIS - O(NlogN) 문제. 아래 두 문제를 참고하면 쉽게 풀이할 수 있다. [백준] 2565. 전깃줄 - Python [백준] 14003. 가장 긴 증가하는 부분 수열 5 - Python AC. import bisect from collections import deque n = int(input()) lines = [] for _ in r..