Algorithm
[백준] 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..
[백준] 2212. 센서 - Python
[Gold V] https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 풀이 간단한 Greedy 문제. 처음에는 집중국의 수신 가능 영역이, 각 집중국이 수신할 수 있는 "범위" 인 줄 알았으나, (좌표 3에서 수신범위가 2라면 1~5를 커버한다는 생각.) 그냥 진짜로 literally 집중국이 수신하는 영역을 나타내는 거였다. 꼭 주위 N만큼의 범위를 수신하는 것이 아니라, 앞으로 2칸, 뒤로 3칸 이렇게도 가능한 것. 그렇..
[백준] 18119. 단어 암기 - C++
[Gold IV] https://www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 풀이 원래 Bitmask 문제를 제일 까다로워하고, 익숙치 않아 했는데, 점점 풀 만해지는 것 같다. ^ㅁ^! 이 문제는 각각의 알파벳(a, b, c, d, ..., x, y, z)의 기억 여부를, 비트마스킹으로 저장하는 것이 핵심이다. 32 bit의 int형 숫자를 이용해, 26개의 알파벳 각각의 기억 여부를 저장한다. ex) 00000000 00000000 00001000..
[백준] 4195. 친구 네트워크 - Python
[Gold II] https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 Union-Find를 이용한, 서로소 집합(Disjoint Set) 응용 문제. 기존 Union-Find를 이용한 기본적인 문제와 크게 다르지 않으나, 네트워크에 속한 친구의 수를 따로 계산해줘야 한다. (rank와는 다름.) 네트워크에 속한 친구의 수를 기록하는 dictionary를 선언하고, (cnt) union해 주는 과정에서, root가 되는 쪽에다 다른 ..
[백준] 20040. 사이클 게임 - Python
[Gold IV] https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 Union-Find를 이용한, 서로소 집합(Disjoint Set) 문제. Union-Find를 잘 구현하고, 이를 이용해 사이클이 생겼는 지를 각 반복마다 확인하면 된다. Union-Find 알고리즘을 알고 있다면 다른 설명이 필요하지 않으므로, 생략. AC. from collections import deque n, m = map(int, input().split(..
[백준] 12026. BOJ 거리 - Python
[Silver I] https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 간단한 DP 문제. 맨 마지막 (N번)에서부터 출발하여, 1번까지 필요한 에너지의 양의 최소를 기록하며 나아가면 된다. (dp[i] => (i+1)번부터 N번까지 이동하는 데에 사용하는 에너지의 최솟값) dp 배열을 생성하여, N번부터 1번까지 모두 순회하며, 현재 위치보다 더 앞쪽에 있는 가능한 위치로의 에너지 최솟값을 기록하자. 예를 들어, 아래와 같은 input이 들어왔다고 가정하자. 9 BOJBOJBOJ 우선 dp[8] = ..
[백준] 2638. 치즈 - Python
[Gold III] https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 "두 변 이상 치즈 외부 공기와 접촉" 한다는 조건만 잘 처리해 준다면, N, M (5 ≤ N, M ≤ 100) 이기 때문에 나머지는 Brute-Force로 처리해도 해결되는 문제이다. air 2차원 배열을 생성하여, 모든 칸을 순회하며, 외부 공기와 접촉한 공기 칸을 체크한다. 이 때, air 배열의 모든 칸은 1로 초기화하고, 외부와 닿아 있는 공기 칸일 ..