분류 전체보기
[백준] 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..
[백준] 15846. 퇴사 2 - Python
[Gold V] https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이 1 문제를 보니, Greedy는 아닌 것 같고.. DP로 접근해야겠다는 생각으로 문제를 읽기 시작. 첫 시도에는, 1차원 dp이고, 1일차 부터 Bottom-Up으로 채워나가는 식으로 접근하려고 시도했다. 예제 입력 1 은 아래와 같다. 1일2일3일4일5일6일7일 Ti3511242Pi102010201540200 이런 상황에서, 1일차부터 접근하면..