이분 탐색은 결정 문제(Decision Problem)의 답이 이분적일 때 사용할 수 있는 탐색 기법이다.
❗️ 결정 문제란? 답이 Yes or No인 문제를 의미하며, 보통 1개의 parameter를 가진다.
1 ~ 50까지 오름차순 정렬된 카드 더미에서 28번 카드를 찾는 문제가 있을 때, 첫 번째 카드부터 i번째 카드는 v[i], 28은 val로 설정한다. 이 경우 결정 문제를 "v[i] >= val인가?"로 잡으면, 결정 문제의 답은 i가 증가함에 따라 F, F, ..., F, T, T, ..., T와 같이 분포한다.
이 때 찾고자 하는 값은 처음으로 v[i] >= val인 지점, 즉 처음 결정 문제가 True가 되는 i값이 된다.
⭐️ 구현 방법
이분 탐색의 구현은
1) Check(lo) != Check(hi)가 되도록 lo, hi의 초기값을 설정한 뒤, 2) lo + 1 < hi인 동안 mid = (lo + hi) / 2를 구해서, 3) Check(lo) == Check(mid)라면 lo = mid를, Check(hi) == Check(mid)라면 hi = mid로 설정한다.
이분 탐색이 끝나면 lo, hi는 결정 문제의 답이 바뀌는 경계에 위치하게 되며,
만약 결정 문제의 답의 분포가 F ~ T인데 정답이 가장 큰 F라면 lo를, 가장 작은 T라면 hi를 출력한다.
1. 경계를 포함하도록, 즉 Check(lo) != Check(hi)가 되도록 [lo, hi]를 설정한다.
2. Check(lo) == Check(mid)라면 lo = mid, 아니라면 hi = mid를 반복한다.
const lower_bound = (v, x) => {
const n = v.length;
let lo = -1, hi = n;
while (lo + 1 < hi) {
let mid = Math.floor((lo + hi)/2);
if (!(v[mid] >= x)) lo = mid;
else hi = mid;
}
return hi;
}
const upper_bound = (v, x) => {
const n = v.length;
let lo = -1, hi = n;
while (lo + 1 < hi) {
let mid = Math.floor((lo + hi)/2);
if (!(v[mid] > x)) lo = mid;
else hi = mid;
}
return hi;
}
console.log(lower_bound([1, 2, 3, 3, 4], 3)); // 2console.log(upper_bound([1, 2, 3, 3, 4], 3)); // 4
⭐️자주 하는 실수
1. lo, hi는 항상 정답의 범위를 나타낼 수 있어야 한다. 예를 들어 lo를 출력해야 하는 문제의 답이 최대 n일 때, hi = n으로 선언하거나, hi를 출력해야 하는 문제의 답이 최소 0일 때 lo = 0으로 선언하면 안된다. (hi = n + 1, lo = -1로 선언해야 한다.)
2. 오버플로우에 주의한다.
3. 결정 문제의 정의에 맞게 Check 함수를 잘 구현해야 한다. Check 함수의 부등호를 조금만 틀려도 전혀 다른 값이 나올 수 있다.
특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구한다. ❗️음의 간선을 포함할 수 없다.
과정
출발 노드를 설정한다.
출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
방문하지 않은 노드 중에서, 가장 비용이 적은 노드를 선택한다.
해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.
위 과정에서 3번 ~ 4번을 반복한다.
예제
초기 가중치 (1번 노드에서 다른 노드로 직접 가는 비용)
1
2
3
4
1
0
2
5
1
1번 노드 선택
현재 방문하지 않은 노드 중에서 가장 비용이 적은 노드: 4번 4번 노드를 거쳐서 가는 경우를 모두 고려하여 최소 비용 배열을 갱신한다.
1번 -> 3번 갱신 (1번 -> 4번 -> 3번 = 4)
1
2
3
4
1
0
2
4
1
다음으로 방문하지 않은 노드 중에서 가장 비용이 적은 노드: 2번 2번 노드를 거쳐서 최소 비용이 갱신되는 경우는 없음.
다음으로 방문하지 않은 노드: 3번 3번 노드를 거쳐서 최소 비용이 갱신되는 경우는 없음.
1번 노드에서 다른 노드로 가는 최단 거리
1
2
3
4
1
0
2
4
1
코드
publicclassDijkstra{
staticint INF = 999999;
publicstaticvoid main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int V = Integer.parseInt(st.nextToken()); // 노드의 개수int E = Integer.parseInt(st.nextToken()); // 간선의 개수int K = Integer.parseInt(br.readLine()); // 시작 노드
Node[] graph = new Node[V+1];
int[] dist = newint[V+1];
boolean[] visited = newboolean[V+1];
Arrays.fill(dist, INF);
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine(), " ");
intfrom = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph[from] = new Node(to, cost, graph[from]);
}
dist[K] = 0; // 시작점for (int i = 1; i <= V; i++) {
int min = Integer.MAX_VALUE;
int cur = 0;
for (int j = 1; j <= V; j++) {
// cur = 방문하지 않은 것 중 가장 비용이 적은 노드if (!visited[j] && min > dist[j]) {
min = dist[j];
cur = j;
}
}
visited[cur] = true;
for (Node j = graph[cur]; j != null; j = j.link) {
// j를 경유하여 갈 수 있는 경우의 최단 거리 갱신if(!visited[j.vertex] && dist[j.vertex]>dist[cur]+j.cost) {
dist[j.vertex]=dist[cur]+j.cost;
}
}
}
for (int i = 1; i <= V; i++) {
System.out.println(Arrays.toString(dist[i]));
}
}
staticclassNode{
int vertex, cost;
Node link;
public Node (int vertex, int cost, Node link) {
this.vertex = vertex;
this.cost = cost;
this.link = link;
}
}
}
