Algorithm

[백준] 1911. 흙길 보수하기 - Python

[Gold V] https://www.acmicpc.net/problem/1911 1911번: 흙길 보수하기 어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000 www.acmicpc.net 풀이 간단한 그리디 문제. 입력된 물웅덩이를 좌표 순으로 정렬한 이후, 모든 물웅덩이를 순회하며, 널빤지를 설치해야 할 경우에 설치한다. 각 순회마다 널빤지의 시작, 끝 좌표를 받고, (line 12) 시작 좌표에 널빤지가 설치되어 있지 않다면, 우선 하나 설치한다. (line 13~15) 그리고, 마지막 좌표를 덮을 때 까지 널빤지를 추가로 설치한다. (..

[백준] 2780. 비밀번호 - Python

[Silver I] https://www.acmicpc.net/problem/2780 2780번: 비밀번호 각각의 Test case에 대해서 조건을 만족하는 비밀번호의 개수를 출력하라. 단, 수가 매우 커질 수 있으므로 비밀번호의 개수를 1,234,567으로 나눈 나머지를 출력하라. www.acmicpc.net 풀이 간단한 DP 문제. 비밀번호 길이가 i일 때, j라는 숫자에서 출발했을 때의 비밀번호 개수를 dp[i][j] 라 하자. 인접한 번호로만 갈 수 있으므로, dp[i][j] 는 인접한 숫자들의 dp[i-1][~] 들의 합으로 구할 수 있다. 점화식은 대충 표현하자면 아래와 같다. # dp[i][j] = dp[i-1][(인접한 숫자)] 들의 합 # ex) dp[3][2] = dp[2][1] + d..

[백준] 14003. 가장 긴 증가하는 부분 수열 5 - Python

[Platinum V] https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 풀이 이분 탐색(Binary Search)를 이용해, log(n logN)의 시간 복잡도로 풀어내는 LIS 문제에서, LIS 배열까지 구해야 한다. 입력된 배열을 순회하며, res 배열의 몇 번째 index에 들어가는 지를 모든 원소에 대해 기록하고, (res_idx) res_idx 배열을 거꾸로 순회하면서, index가 가장 처음 나오는 부분..

[백준] 12015. 가장 긴 증가하는 부분 수열 2 - Python

[Gold II] https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 이분 탐색(Binary Search)를 이용해, log(n logN)의 시간 복잡도로 풀어내는 LIS 문제. res 배열을 생성, 입력된 배열을 모두 순회하며, res 배열의 마지막 숫자보다 크다면 res 맨 뒤에 append. 작다면, 이분 탐색을 이용해 들어갈 자리를 찾고, 그 index에 대신 삽입. 최종적으로 LIS의 길이를 구할 수 있게 된다. 다만 이렇게 만들어진..

[백준] 2352. 반도체 설계 - Python

[Gold II] https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 풀이 [백준] 2565. 전깃줄 - Python 문제와 동일하다시피 한 문제이다. 다만, 전깃줄 문제는 O(N^2)의 LIS (DP)로 풀이할 수 있는 반면, 이 문제는 n

[백준] 2615. 오목 - Python

[Silver I] https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 풀이 19x19의 모든 칸을 순회하며, 오목이 되는 지 여부를 Brute-Force로 검사하면 된다. 오목이 될 수 있는 모든 경우는 하향 직선 5개, 우하향 대각성 5개, 우향 직선 5개, 우상향 대각선 5개가 이어지는 4가지의 경우가 존재하며, 시작하는 돌의 바로 이전 칸과, 5개째가 아닌 6개째의 칸까지 같이 확인하여 6목이 되지 않는 지를 검사해야 한다. AC. b = ..

[백준] 2565. 전깃줄 - Python

[Gold V] https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 전깃줄이 교차하는 경우를 생각해 보자. A 전봇대에서 B 전봇대로의 모든 전깃줄을 시작부터 숫자가 작은 순서대로 하나하나 연결한다고 생각할 때, 도착하는 위치가 이미 존재하는 도착지들보다 더 작은 숫자라면, 전깃줄이 교차하게 된다. 따라서 그러한 전깃줄들을 제거하면 되는 문제이다. 이 과정에서, A 전봇대에서의 출발 위치를 기준으로 정렬하게 되면, 아래와 같다. [[1, 8], [2..

[백준] 17144. 미세먼지 안녕! - Python

[Gold IV] https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 확산 과정과 공기청정기가 작동하는 과정을 문제에서 지시한 대로 정확하게 구현하면, 어렵지 않게 풀 수 있었던 문제. 다만 확산 과정에서, 새로운 배열을 생성하여 확산 과정을 기록하지 않으면, 다른 칸을 확산시키면서 값이 변하여 확산되는 미세먼지의 양이 변할 수 있으므로, 새로운 배열을 생성하여 계산한 이후 deep copy로 복사하여 다시 다음 과정을 진행시킨다. (new..