[알고리즘 -6] 이분탐색, LIS

이분탐색 (Binary Search)

오름차순으로 정렬되어 있는 리스트에서 같은 크기의 두 부분으로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 데이터를 찾는 알고리즘

 

1. 정렬된 배열의 중간요소와 어떠한 대상 값을 비교한다

2. 그 요소가 아닌 경우 절반을 제거하고 나머지 절반에서 검색을 반복한다

    2-1. 그 요소가 중간요소보다 작을 경우, 왼쪽으로 다시 탐색

    2-2. 그 요소가 중간요소보다 클 경우, 오른쪽으로 다시 탐색

 

 

이렇게 정렬된 배열에서 중간값이 어떠한 대상 값보다 큰지, 작은지 비교하고 탐색 범위를 반으로 나누기 때문에 시간복잡도는 logN이다. 

 

 

v배열에서 찾는 값이 n일때 코드이다

while(l <= r){
    mid = (l + r) / 2; 
    if(v[mid] > n) r = mid - 1; 
    else if(v[mid] == n) return 1;
    else l = mid + 1; 
}

 

📌 이분탐색 알고리즘 문제

https://www.acmicpc.net/problem/2792 

import java.util.*;
import java.io.*;

public class Main{
	static int n,m;
	static int nList[],mList[];
    
	static int search(int num){
		int l=0; int r=n-1;
		int check=0;
		
		while(l<=r){
			int mid=(l+r)/2;
			if(nList[mid]==num){
				check=1;
				return check;
			}else if(nList[mid]>num){
				r=mid-1;
			}else{
				l=mid+1;
			}
		}
		return check;
	}
	public static void main(String[]args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		int T;
		
		T=Integer.parseInt(br.readLine());
		
	
		for(int test_case=0;test_case<T;test_case++){
			//입력
			n=Integer.parseInt(br.readLine());
			nList=new int[n];
			st=new StringTokenizer(br.readLine());
			for(int i=0;i<n;i++){
				nList[i]=Integer.parseInt(st.nextToken());
			}
			
			m=Integer.parseInt(br.readLine());
			mList=new int[m];
			st=new StringTokenizer(br.readLine());
			for(int i=0;i<m;i++){
				mList[i]=Integer.parseInt(st.nextToken());
			}
			
			//정렬
			Arrays.sort(nList);
			
			//이분탐색
			for(int i=0;i<m;i++){
				bw.write(Integer.toString(search(mList[i])));
				bw.write('\n');
			}
			bw.flush();
		}
	}
	
}

 

 

 

LIS (Longestr Increase Sequence), 최장 증가 부분 수열

어떤 수열에서 일부 원소를 골라서 만들 수 있는 수열 중에서, 길이가 최대이면서 오름차순을 유지하는 수열

 

 

📌 LIS 문제

https://www.acmicpc.net/problem/11053

 

 

 

import java.util.*;
import java.io.*;

public class Main{
	public static void main(String[]args) throws IOException{
		Scanner sc=new Scanner(System.in);
		int ret=0;
		int n;
		int a[],cnt[];
		n=sc.nextInt();
		
		a=new int[n];
		cnt=new int[n];
		
		for(int i=0;i<n;i++){
			a[i]=sc.nextInt();
		}
		for(int i=0;i<n;i++){
			int maxValue=0;
			for(int j=0;j<i;j++){
				if(a[j]<a[i] && maxValue<cnt[j]){
					maxValue=cnt[j];
				}
			}
			cnt[i]=maxValue+1;
			ret=Math.max(ret,cnt[i]);
		}
		System.out.println(ret);
	}
}