package Search.BinarySearch;
public class BinarySearchTest {
static int[] arr;
public static void main(String[] args) {
arr = new int[]{1,3,5,7,9,11,13};
int idx = BinarySearchCode(9);
System.out.println(idx);
}
public static int BinarySearchCode(int findNumber){
int s = 0;
int e = arr.length - 1;
int mid;
int returnNumber = 0;
while(s <= e){
mid = (s+e) / 2;
if(findNumber == arr[mid]) {
returnNumber = mid;
break;
}
else if(findNumber > arr[mid])
s = mid + 1;
else if(findNumber < arr[mid])
e = mid - 1;
}
return returnNumber;
}
}
이분 탐색의 코드 자체는 간단하다.
left에서 시작하는 s, right에서 시작하는 e가 서로 교차하게 되면 종료한다.
(s+e)/2를 이용한 중간 값 mid를 계속 조건에 맞게 변화시키며 탐색범위를 이분한다.
찾지 못하였다면 그냥 종료될 것이고, 찾았다면 idx를 리턴한다.
이분 탐색에서 가장 중요하다고 생각하는 점은
변하는 가변 값과 변하지 않는 기준 값이다.
기준 값과 가변 값과의 비교를 통해 s, e 범위를 결정한다.
현재 코드에서는 찾을 숫자(기준 값)를 기준으로
mid를 이용해서 가변 값과의 비교를 통해 s, e를 결정하고 있지만
Prametric Search를 하게 되면 기준 값은 문제를 보고 결정을 해주어야 한다.
public static long binarySearch(int need){
long s = 0;
long e = 2_000_000_000;
long returnHeight = 0;
while(s <= e){
long mid = (s + e) / 2;
// 기준값 설정
// 자른 값들의 총합을 이용
long sum = 0;
for(int i = 0; i<arr.length; i++){
int ele = arr[i];
if(ele > mid)
sum += ele - mid;
}
if(sum >= need) { // 조건을 만족하므로 범위를 더 엄밀하게 줄임
s = mid + 1;
returnHeight = mid; // 조건을 충족한다면 일단 저장
}else if(sum < need)
e = mid - 1;
}
return returnHeight;
}
백준 2805 나무자르기 문제의 코드 일부다.
해당 문제에서 기준 값은 need 이다. (함수의 매개변수로 받고 있음)
가변 값은 mid를 이용해 구한 sum이다.
mid를 기준으로 자른 값들의 총합(sum)이 need 이상이면,
더 엄밀하게 자르기 위해 s를 더 올려서 mid를 높인다.
만족하지 않는다면 e를 낮춰서 mid를 낮춘다.
탐색 범위를 마지막에 만족하는 것까지 좁힐 수 있으므로 최대값을 구할 수 있다.
이분 탐색, 매개 변수 탐색을 구현할 땐 기준 값, 가변 값을 무엇으로 할 지 항상 생각하자.
다익스트라 알고리즘은 출발지 -> 경유지 -> 목적지를 이용하여 최단 경로를 구하게 된다.
이 과정을 반복하게 되면 고정된 출발지에서 모든 edge의 최단 경로를 구할 수 있다.
필요 사항
우선 순위 큐 (순서대로 확인하는 것이 아닌, 거리가 가장 짧은 것부터 수행하기 때문에 수행 시간을 단축)
고정된 출발지에서 목적지까지의 경로 값 저장 배열
최소 비용을 만들기 위해 필요한 Node의 개수는 항상 3개라고 생각해야 한다. [출발, 경유, 목적]
출발지 -> 경유지, 경유지 -> 목적지로 따로 생각해야 한다.
경유지를 반복문을 돌리므로 목적지는 복수개다.
주목할 부분은 경유지 -> 목적지 인 부분이다.
목적지였던 부분이 다음부터 경유지로 사용이 되어
경유지가 향하는 모든 edge의 비용을 확인한다.
퍼져나가는 방식으로 최종적으로 모든 노드의 최소 비용을 알 수 있다.
round 1 = 경유지 -> 목적지
round 2 = 경유지 -> 목적지
round 3 = 경유지 -> 목적지
[목적지가 최소 경로 비용으로 처리되면 다음부터는 목적지가 경유지로 쓰임]
BFS 동작 방식과 유사하다.
동작 예시
다익스트라 알고리즘은 경유지로 가장 먼저 자기 자신을 기준으로 update 한다.
1번 노드에서 3, 4번 노드를 update 시켜줄 수 있다.
[1 -> 1 -> 3] [1 -> 1 -> 4]
dist배열 = [INF, 0, INF, 6, 3, INF] // 0번은 편의를 위해 사용하지 않는다.
3, 4번 노드가 update 되고,
큐에 3, 4번 노드가 들어갔다.
4번 노드의 가중치가 가장 작으므로 우선순위 큐에 의해 가장 먼저 나온다.
4번 노드에서 2, 3번 노드를 update 시켜줄 수 있다.
[1 -> 4 -> 2] [1 -> 4 -> 3]
dist배열 = [INF, 0, 4, 4, 3, INF]
2, 3번 노드가 update 되고,
큐에 2, 3번 노드가 들어갔다.
현재 큐에 3번 노드가 두 번 들어갔다.
이 경우는 먼저 들어간 3번 노드는 가중치가 6으로 dist [3]의 값보다 크므로 사용되지 않고 버려진다.
1 -> 1 -> 3 경로보다 1 -> 4 -> 3 경로가 최소 비용이므로 1 -> 4 -> 3을 사용하면 되기 때문이다.
(update 된 거리보다 크다면, update 한 노드는 큐에 들어간 것이므로 최소가 보장. 버려도 되는 이유)
이 같은 방식으로 시작 노드를 기준으로 퍼져나가며 모든 노드의 최소 비용을 계산한다.
다익스트라 알고리즘은 방향 그래프여야 하며, 거리가 음수면 안된다.
거리가 음수, 그리고 사이클이 존재한다면 거리를 계속 줄이는 음수 사이클이 발생. -무한대 형성
public class Dijkstra {
static int[] dist;
static int[] path; // 자신의 앞 경로를 갖고 있다. ** 모든 경로를 확인할 수 있다.
static List<List<Node>> list = new ArrayList<>(); // 간선들
static final int edgeCount = 5 + 1;
static final int vCount = 7;
public static void main(String[] args) {
//노드 5개
dist = new int[edgeCount]; // 0 사용안함.
path = new int[edgeCount];
//간선 7개
for(int i = 0; i<=vCount; i++) {
list.add(new ArrayList<>());
}
// (1 - > 5) 2000 쓰는 경로
list.get(1).add(new Node(4, 2000));
list.get(1).add(new Node(5, 2000));
// (1 -> 5) 10 쓰는 경로
list.get(1).add(new Node(2, 5));
list.get(2).add(new Node(5, 5));
// (1 -> 5) 3 쓰는 경로
list.get(1).add(new Node(3, 1));
list.get(3).add(new Node(4, 1));
list.get(4).add(new Node(5, 1));
// TODO: 이 부분 주의 자신은 0으로 만들어야함
// 자기 자신 빼고 나머지 INF 로 초기화
Arrays.fill(dist, 100_000_000);
dist[1] = 0; // 시작
dijk();
// 결과
System.out.println(Arrays.toString(dist));
// 경로
System.out.println(Arrays.toString(path));
}
// TODO: 출발지 1번은 계속 고정
public static void dijk(){
Queue<Node> q = new PriorityQueue<>((o1,o2) -> o1.w - o2.w);
q.add(new Node(1, 0)); // 경유지, 비용 (1 -> 1 -> n)
while(!q.isEmpty()) { // TODO: 경유지 뽑기 // 1 -> M
Node mid = q.poll(); // 1과 연결된 경유지
// 과거 , 현재
if(mid.w > dist[mid.dest]) // update 된 거리보다 큐에서 뽑은게 더 크면 사용 안하고 버림
continue;
// TODO: 경유 -> 도착 꺼내는 부분
for(Node d : list.get(mid.dest)){
if(dist[d.dest] > dist[mid.dest] + d.w){ // 갱신이 되는 부분.
dist[d.dest] = dist[mid.dest] + d.w;
// 갱신이 된 것. 1->n , n->M
// (1 -> 도착지) [[ (1 -> 경유(테이블) + 경유(테이블) - > 도착지 ]]
// 계속 갱신 계속 생신
// TODO: 현재 목적지가 다음부터는 경유지로 쓰인다.
q.offer(new Node(d.dest, dist[d.dest]));
// 갱신된 (1 -> 목적지) 를 넣어준다.
// 갱신된걸 넣지 않으면 for 부분을 또 확인하기 때문에 갱신된 값을 넣어주는게 좋다.
path[d.dest] = mid.dest; // 길찾기 용도 (자신의 앞 노드)
}
}
}
}
}
// 경유지로도 쓰고, 목적지로도 쓰임
class Node{
int dest; // 도착지
int w; // 가중치
Node(int dest, int w){
this.dest = dest;
this.w = w;
}
public String toString(){
return this.dest + " " + this.w;
}
}
