0. 문제 링크 https://www.acmicpc.net/problem/12015 1. 문제 2. 문제해결 알고리즘 이분탐색 바이토닉 정렬 3. 문제 해결 및 코드 이 문제의 핵심은 부분 수열이 아니라 부분 수열의 개수이다. import sys from bisect import bisect_left input = sys.stdin.readline def main(): N = int(input()) arr = list(map(int, input().split())) stack = [0] for n in arr: if stack[-1] < n: stack.append(n) else: stack[bisect_left(stack, n)] = n print(len(stack) - 1) main() 수열에 가장 ..

0. 문제 링크 https://www.acmicpc.net/problem/1300 1. 문제 2. 사용 알고리즘 이분탐색 3. 해결 방법 처음 이 문제를 해결하려 할 때 1부터 K번째 수까지 세는 것은 100% 시간 초과가 날 것이다. 왜냐하면 K의 값이 10^9까지 올라 갈 수 있기 때문이다. 그러므로 처음에는 i, j 번째의 숫자의 특성이 있나 파악했다. 3 * 3 배열 ( N = 3 ) 일 때 다음과 같은 특성을 알 수 있었다. 1 2 3 2 4 6 3 6 9 1의 배수 2의 배수 3의 배수 조금 더 세밀하게 이야기 하면 특정 숫자의 이하의 숫자 배열은 다음과 같다. N = 7의 예시를 들어보겠다. 18 숫자보다 작거나 같은 숫자는 다음과 같다. 배열이 크다면 파랑색 부분(8)도 포함되겠지만 배열 ..

0. 문제 링크 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1. 문제 2. 해결 알고리즘 이분 탐색 3. 이 문제의 특징 이 문제의 핵심은 최대 길이의 랜선으로 뽑는 것이다. 예를 들어서 603m의 랜선을 3개로 자른다고 했을 때 200m도 3개, 201m도 3개이다. 여기서 문제는 201m 200m 자른 결과 값이 똑같이 3개인데 어떻게 구분하냐는 것이다. 답은 right 값에 있다. right 로 설정된 값..

0. 문제 링크 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 1. 문제 2. 해결 알고리즘 우선순위 큐 3. 이 문제의 특징 중간 값을 어떻게 보관하고 얻어 낼지가 관건인 문제 같다. 중간 값 보다 작은 수를 우선 순위 큐(작은 힙)에 저장하고 중간보다 큰 수를 다른 우선 순위 큐(큰 힙)에 저장하는 것이다. 코드는 다음과 같다. import sys import heapq input = sys.stdin.readline de..