Typiler

파라매트릭 서치(Parametric Search)는 바이너리 서치와 매우 유사합니다. 차이점은 최적화 문제를 결정문제로 바꾸어 푸는 것입니다. 원하는 조건을 만족하는 가장 알맞는 값을 특정한 오차범위 이내에서 알고 싶은 경우에 사용을 합니다.

• 바이너리 서치 : 배열에서 중앙값이 가리키는 값이 내가 찾는 값인지가 중요
• 파라매트릭 서치 : 원하는 조건을 만족하는 가장 알맞는 값을 찾는 것

동작과정

1. 데이터를 정렬한다.
2. 범위를 반씩 좁혀간다.
3. S 와 E 가 같을때 까지 진행한다.

시간복잡도

바이너리 서치와 같은 O( log N ) 입니다.

참고사이트

https://www.crocus.co.kr/1000

https://en.wikipedia.org/wiki/Parametric_search

기본코드

'#' 의 개수를 알아내는 문제

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static char[] arr;
    
    static int parametricSearch(int s, int e){
    	
    	int maxIndex = -1;
    	
    	while(s<=e){
    		int mid = (s+e)/2;
    		char mVal = arr[mid];
    		
    		if (mVal == '#') {
                if (maxIndex < mid) maxIndex = mid;
                s = mid + 1;
            }
            else {
                e = mid - 1;
            }
    	}
    	
    	return maxIndex;
    	
    }
    
    public static void main(String[] args) throws IOException {      
    	
    	String str = "#######___";
   		arr = str.toCharArray();
  		
   		int cnt = parametricSearch(0, arr.length-1) + 1;
    		
   		bw.write(cnt+"\n");
    	
        br.close();
        bw.close();        
    }
}

바이너리 서치와 바이너리 서치 트리는 차이가 있습니다. 이중 오늘 공부할 내용은 바이너리 서치(Binary Search) 입니다. 자료구조가 아니라 알고리즘입니다. 바이너리 서치는 정렬되어있는 상태에서 내가 원하는 값을 찾고 싶을때 찾는 알고리즘 입니다. 여기서 정렬되어있는 상태가 중요합니다. 이것이 기본조건입니다. 데이터를 빨리 찾기 위한 방법입니다.

동작과정

1. 데이터를 정렬한다.
2. 범위를 반씩 좁혀가며 데이터를 찾는다.

시간복잡도

한번 탐색할때 마다 크기를 반으로 줄이기 때문에 시간복잡도는 O( log N ) 이 됩니다.

참고사이트

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

기본코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;


class 바이너리서치_기본코드 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int[] arr = {50,30,1,2,5,7,9,10};
    static int tar = 7;
    
    static void bSearch(int s, int e){
    	while(s<=e){
    		int mid = (s+e)/2;
    		int mVal = arr[mid];
    		
    		if(mVal == tar){
    			System.out.println("발견");
    			return;
    		}
    		
    		if(mVal < tar) s= mid + 1;
    		else e = mid - 1;
    	};
    	
    	System.out.println("미발견");
    }
    
    public static void main(String[] args) throws IOException {      
    	
    	// 바이너리 전제조건 => 정렬이 필수
    	Arrays.sort(arr);
    	
    	bSearch(0,arr.length-1);
    	
        br.close();
        bw.close();        
    }
}

그래프 문제에서 대표적인 최단 경로를 구하는 알고리즘입니다. 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다고 알려져 있습니다. 하나의 정점에서 모든 정점으로 가는 최단 경로를 알려줍니다. (단, 음의 간선을 포함할 수 없음)

응용이 많은 부분이라 기본적인 내용을 확실히 숙지하여야 합니다.

동작과정

1. 출발 노드를 설정
2. 출발노드 기준으로 각 노드의 최소비용을 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택
4. 해당 노드를 거쳐서 톡정한 노드로 가는 경우를 고려하여 최소 비용을 갱신
5. 위 과정에서 3~4 과정을 반복

시간복잡도

• 힙의 구조를 활용하면 : O(N * log N)

참고 사이트

• 동빈나 : https://blog.naver.com/ndb796/221234424646
• 위키백과 : https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

기본코드

아래와 같은 그래프가 존재한다고 합시다. 0에서 시작하여 각 노드까지의 최단 거리를 구하는 코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;

class Node implements Comparable<Node>{
    int n;
    int dist;

    Node(int a, int b) {
        n = a;
        dist = b;
    }

    @Override
    public int compareTo(Node tar) {
        if (tar.dist < this.dist) return 1; 
        if (tar.dist > this.dist) return -1; 
        return 0;
    }    

}

class 다익스크라_기본코드_단방향 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static ArrayList<ArrayList<Node>> alist = new ArrayList<ArrayList<Node>>();
    static PriorityQueue<Node> q = new PriorityQueue<Node>();

    static int[] best;
    static int[] used;

    public static void main(String[] args) throws IOException {        

        int n = 5;
        best = new int[n];
        used = new int[n];

        for (int i = 0; i<n; i++) {
            alist.add(new ArrayList<>());
        }

        alist.get(0).add(new Node(2, 70));
        alist.get(0).add(new Node(1, 10));
        alist.get(0).add(new Node(4, 170));        
        alist.get(1).add(new Node(2, 50));
        alist.get(1).add(new Node(3, 20));
        alist.get(2).add(new Node(4, 60));    
        alist.get(3).add(new Node(2, 15));

        //다익스트라 초기세팅
        q.add(new Node(0, 0));
        for (int i = 0; i<n; i++) best[i] = Integer.MAX_VALUE;
        best[0] = 0;

        while(!q.isEmpty()) {
            Node via = q.poll();
            if (used[via.n] == 1) continue; //이미 했었던 경유지면 탈락
            if (best[via.n] != via.dist) continue; //예전정보면 탈락

            used[via.n] = 1;             

            for (int i = 0; i<alist.get(via.n).size(); i++) {
                Node tar = alist.get(via.n).get(i);

                //지금까지 구했던 최고의 비용보다, 더 저렴한 비용이 발견되면 
                if (best[tar.n] > via.dist + tar.dist) {
                    best[tar.n] = via.dist + tar.dist; //갱신 
                    q.add(new Node(tar.n, best[tar.n]));
                }
            }
        }

        System.out.println(best[4]);

        br.close();
        bw.close();
    }
}

0에서 시작하여 각 노드들의 최단 거리는 아래와 같이 빨강색 경로로 이동을하여 4까지 가는 최단경로의 거리는 105 입니다.