이분탐색

탐색 범위를 두 부분으로 분할하면서 찾는 방식
처음부터 순차적으로 탐색하는 것보다 훨 씬 빠른 장점을 지님

시간 복잡도
O(logN)

• 배열이 정렬되어 있어야함
• 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다. -> 재귀 또는 반복
  

1. 재귀

private static int binarySearch1(int[] arr,int target,int start,int end){
		if(start>end) return -1;
		int mid=(start+end)/2;
		if(arr[mid]==target) return mid;
		if(arr[mid]>target) return binarySearch1(arr,target,start,mid-1);
		else return binarySearch1(arr,target,mid+1,end);
	}

2. 반복

private static int binarySearch2(int[] arr,int target,int start,int end){
		while(start<=end){
			int mid=(start+end)/2;
			if(arr[mid]==target) return mid;
			if(arr[mid]>target) end=mid-1;
			else start=mid+1;
		}
		return -1;
	}

https://minhamina.tistory.com/127

최단 경로

다익스트라 최단경로 알고리즘

다익스트라 최단 경로 알고리즘은 그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
다익스트라는 '음의 간선'이 없을 때 정상 동작한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미한다.
기본적으로 그리디 알고리즘으로 분류된다.
매번 가장 적은 비용의 노드를 선택하여 과정을 반복하기 때문

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다(무한대)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
   위 과정을 노드에서 반복한다.
   

위와 같은 과정을 반복한다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class 다익스트라 {
	static class Node implements Comparable<Node>{
		private int index;
		private int distance;

		Node(int index,int distance){
			this.index=index;
			this.distance=distance;
		}

		public int getIndex(){
			return this.index;
		}

		public int getDistance(){
			return this.distance;
		}

		@Override
		public int compareTo(Node other){
			if(this.distance<other.distance){
				return -1;
			}
			return 1;
		}
	}

	public static final int INF=(int)1e9;
	public static int n,m,start;
	public static int[] d=new int[100001];
	public static ArrayList<ArrayList<Node>> graph=new ArrayList<>();

	public static void dijkstra(int start){
    //방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드
		PriorityQueue<Node> pq=new PriorityQueue<>();
		pq.offer(new Node(start,0));
		d[start]=0;
		while(!pq.isEmpty()){
			Node node=pq.poll();
			int dist=node.getDistance();
			int now=node.getIndex();
			if(d[now]<dist) continue;
			for(int i=0;i<graph.get(now).size();i++){
				int cost=d[now]+graph.get(now).get(i).getDistance();
				if(cost<d[graph.get(now).get(i).getIndex()]){
					d[graph.get(now).get(i).getIndex()]=cost;
					pq.offer(new Node(graph.get(now).get(i).getIndex(),cost));
				}
			}
		}
	}


	public static void main(String[] args){
		n=6;
		for(int i=0;i<=n;i++){
			graph.add(new ArrayList<Node>());
		}

		Arrays.fill(d,INF);
		graph.get(1).add(new Node(2,2));
		graph.get(1).add(new Node(3,5));
		graph.get(1).add(new Node(4,1));
		graph.get(2).add(new Node(3,3));
		graph.get(2).add(new Node(4,2));
		graph.get(3).add(new Node(2,3));
		graph.get(3).add(new Node(6,5));
		graph.get(4).add(new Node(3,3));
		graph.get(4).add(new Node(5,1));
		graph.get(4).add(new Node(5,1));
		graph.get(5).add(new Node(3,1));
		graph.get(5).add(new Node(6,2));

		dijkstra(1);
		for(int i=1;i<=n;i++){
			if(d[i]==INF){
				System.out.println("INF");
			}
			else{
				System.out.println(d[i]);
			}
		}

	}
}

플로이드 워셜 알고리즘

'모든 지점에서 다른 모든 지저까지의 촤단경로를 모두 구해야 하는 경우'에 사용 하는 알고리즘이다.
다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행
2차원 최단거리 테이블이 필요하다.
점화식을 사용하여 최단경로를 구하기 때문에 다이나믹 프로그래밍 유형

import java.util.*;
public class 플로이드_워셜 {
	public static void main(String[] args){
		int[][] graph=new int[5][5];
		int INF=(int)1e9;
		int n=4;
		for(int i=0;i<=n;i++){
			Arrays.fill(graph[i],INF);
		}

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j) {
					graph[i][j] = 0;
				}
			}
		}

		graph[1][2]=4;
		graph[1][4]=6;
		graph[2][1]=3;
		graph[2][3]=7;
		graph[3][1]=5;
		graph[3][4]=4;
		graph[4][3]=2;

		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				for(int k=1;k<=n;k++){
					graph[j][k]=Math.min(graph[j][k],graph[j][i]+graph[i][k]);
				}
			}
		}

		for(int a=1;a<=n;a++){
			for(int b=1;b<=n;b++){
				if(graph[a][b]==INF){
					System.out.print("INF");
				}
				else{
					System.out.print(graph[a][b]+ " ");
				}
			}
			System.out.println();
		}


	}
}

최소 비용(MST)(크루스칼, 프림)