Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

21. 이분 탐색

이분 탐색 알고리즘을 배워 봅시다.

Java / Python

7. 가장 긴 증가하는 부분 수열 2

12015번

의외로 이분 탐색으로 풀 수 있는 놀라운 문제 2. 자주 사용되는 알고리즘이니 알아 둡시다.

이번 문제는 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하는 문제입니다. 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력하면 됩니다.

• Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
		int N = Integer.parseInt(br.readLine());
		List<Integer> list = new ArrayList<>();
		list.add(0);
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int value, left, right, mid;       
		for(int i = 0; i < N; i++){
			value = Integer.parseInt(st.nextToken());
			if(value > list.get(list.size() - 1)) 
				list.add(value);
			else{
				left = 0;
				right = list.size() - 1;
				while (left < right) {
					mid = (left + right) / 2;
					if (value > list.get(mid)) { 
						left = mid + 1;
					} else {
						right = mid;
					}
				}
				list.set(right, value);
            }
        }
		bw.write(list.size()-1 + "\n");
		br.close();
		bw.flush();
		bw.close();
	}
}

• Python

• 이분탐색을 구현해서 푸는 방법입니다. (시간 초과가 나 PyPy3로 돌렸습니다.)

import sys
N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
DP = [0]

for i in range(N):
    left = 0
    right = len(DP) - 1
    while left <= right: 
        mid = (left + right) // 2  
        if DP[mid] < arr[i]:
            left = mid + 1
        else:
            right = mid - 1
    if left >= len(DP):
        DP.append(arr[i])
    else :
        DP[left] = arr[i]
print(len(DP) - 1)

• bisect를 사용해서 푸는 방법입니다.

import sys
from bisect import bisect_left 
N = int(sys.stdin.readline()) 
arr = list(map(int, sys.stdin.readline().split())) 
dp = [0]

for i in arr: 
    if dp[-1] < i: 
        dp.append(i) 
    else: 
        dp[bisect_left(dp, i)] = i
        
print(len(dp)-1)