목록코딩테스트 (130)
코딩하는 해맑은 거북이
해당 글은 백준 1654번 '랜선 자르기' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 설명 해당 문제는 이진탐색으로 O(logN)의 시간복잡도로 해결할 수 있는 문제이다. 이전에 풀었던 나무자르기 이진탐색 문제와 비슷한데, 다른 점은 count를 mid로 나눈 몫의 갯수로 구하므로 mid가 0이 되지 않도록 start는 1부터 진행해야 한다. 코드 k, n = map(int, input()..
해당 글은 백준 4963번 '섬의 개수' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 설명 해당 문제는 DFS나 BFS로 간단하게 해결할 수 있다. 여기서는 DFS를 통해 해결하였고, 1은 섬, 0은 바다로 표시되어 있으므로 카운트를 2부터 시작하여 DFS를 진행하고 결과 출력시 -2를 해주어 섬의 개수를 세어주었다. 그리고 주의할 점은 재귀 한계를 늘려주어야 에러가 발생하지 않는다. 코드 import sys sy..
해당 글은 백준 10816번 '숫자 카드 2' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 설명 해당 문제는 Counter 함수를 사용하여 쉽게 해결하였다. 해당 문제의 정답 비율 30퍼대라 다른 기발한 방법이 있나 의심하면서 제출하였는데, 한번에 통과되었다. 아무래도 단순 리스트로 접근하면 시간초과가 많이 발생한 듯 싶다. 굳이 Counter 함수를 쓰지 않아도 딕셔너리로 +1로 입..
해당 글은 백준 11724번 '연결 요소의 개수' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 설명 해당 문제는 DFS로 방문여부를 확인하며 모두 탐색해보면 되는 간단한 문제이다. 여기서 주의할 점은 재귀한계를 늘려주고, input을 sys.stdin.readline으로 설정하여 시간을 줄이지 않으면 시간초과가 뜬다. 코드 import sys sys.set..
해당 글은 백준 10844번 '쉬운 계단 수' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 설명 해당 문제는 1자리 수 일 때, 계단자리수는 0~9까지 수에서 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]로 카운트할 수 있다. 2자리 수 이상 일 때 부터 0일 때는 0이 앞에 올 수 없으므로 이전의 1의 갯수를, 9일 때는 올 수 있는 수는 8 밖에 없으므로 이전의 8의 갯수를 가져온다. 1~8일 때는 앞뒤로 두 개의 숫자가 올 수 있으므로 이전의 앞뒤 숫자의 갯수를 가져온다. 표로 그려보자면 자릿수에 따른 0~9의 DP는 ..
해당 글은 백준 1780번 '종이의 개수' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 설명 이전에 풀었던 분할정복 알고리즘 문제인 쿼드트리와 같지만, 2개가 아닌 3개로 분할하는 것만 다르다. 마찬가지로 분할될 때의 가장 왼쪽 위의 값과 같은 분할 안의 값이 같은지 확인하는 방법으로 진행하였다. 즉, 첫 번째 nxn 행렬에서는 (0, 0)의 값과 다른 위치의 값들을 비교한다. 코드 import sys inp..