기록

문제 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 해당 문제는 이분 탐색으로 해결할 수 있다. 1. 계산한 랜선의 개수 number가 필요한 랜선의 개수 N보다 크거나 N과 같다면 랜선의 길이가 속하는 구간 [start, end]를 [(start, end)/2, end]로 줄인다. 2. 계산한 랜선의 개수 number가 필요한 랜선의 개수 N보다 작다면 랜선의 길이가 속하는 구간 [start, end]를 [start, (start, end)/2]로 줄인다. 구간의 크기가 ..

문제 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 풀이 이분 탐색을 이용하여 위의 문제를 해결할 수 있다. 이를 위하여 우선 첫번째 배열을 오름차순으로 정렬해야 한다. 그 뒤에 다음에 따라 특정 수가 존재할 수 있는 짧은 구간[start, end]을 찾는다. 1. [start, end]의 중간 점을 p라고 할때, arr1의 p번째 원소가 찾으려는 값 number보다 크거나 같다면 탐색구간을 [start, p]로 줄인다. 2. arr1의 p번째 원소가 찾으려는..

문제 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 1. 구해야 하는 두 수 중 첫번째 수 a를 선택한다. 2. 지정한 수보다 오른쪽에 있는 수들을 탐색 범위[startPoint, endPoint]로 지정한다. 3. 이분 탐색을 통해 첫번째 수 a와의 합이 0에 가장 가까운 두번째 수 b를 찾는다. 3-1. a+startPoint와 a+endPoint의 곱의 부호가 -이라면 startPoint는 startPoint와 endPoint의 중간이 된다. 3-2. a+startPoint와 a+endPoi..

문제 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 가장 먼저 생각나는 것은 완전탐색이다. 다만, 반복문을 이용해 모든 경우의 수을 탐색하며 조건을 만족하는 경우 O(N^4)의 시간 복잡도로 입력값이 많아지면 엄청난 시간이 걸리게 된다. 이 문제는 투 포인터 알고리즘을 사용하면 해결할 수 있다. 리스트에 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 특정 값과 같을 때까지 포인터를 조작하는 기법을 투 포인터 알고리즘이라고 한다. 해당 문제를 해결하는 알고리즘을 정리..

보호되어 있는 글입니다.

문제 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 A, B가 커짐에 따라 A**B의 수행시간이 늘어난다. 따라서 이문제는 분할 정복을 이용하여 해결해야 한다. 모듈러 연산의 성질과 분할정복을 이용하면 B번의 연산을 log2B번으로 줄일 수 있다. 코드 def f(A, B) : if B==0 : return 1 if B%2==0 : tmp1 = f(A, int(B / 2)) ans = (tmp1 * tmp1) % C else : tmp1 = f(A, int(B / 2)) tmp2 = (tmp1 * (A % C)) % C ans = (tmp1 * tmp2) % C re..

문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 첫번째 열에 속하는 두 값을 제외하고 연산을 시작한다. 제한사항에 따르면 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 함께 사용할 수 없다. 이 조건을 이용하여 왼쪽에서 오른쪽으로 진행하면서 max(왼쪽 대각선 값+현재 값, 왼쪽값)을 연산하였다. # 초기상태 [50, 10, 100, 20, 40] [30, 50, 70, 10, 60] # n = 1 [50, 50, 100, 20, 40] [30, 100, 70, 10, 60] #..

문제 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 N이 10이라고 할때, 경우의 수를 트리의 형태로 나열 할 수 있다. 같은 수가 다른 자리에서 여러번 등장할 수 있으므로 트리의 레벨 개념을 도입하였다. (N*level의 2차원 배열을 두었다고 생각할 수 있다.) 문제에서 N은 10^6보다 작은 자연수이므로, 메모리의 한계를 고려하여 defaultdict와 dict를 이용하여 아래의 코드처럼 표현하였다. 코드 from collections import defaultdict N = int(input()) tree = defaultdict(dict) # child: {lv:p} nums = [N] lv = 0 ..