Repository navigation
[탐색] #254
Description
이분탐색
구현
st와 en: target이 있는 인덱스로 가능한 범위
탐색 범위 변화 & 값이 존재하지 않는 상태
코드
/**
* 이분 탐색
* 값이 있으면 1, 없으면 0
*/
public int binarySearch(int[] arr, int target) {
Arrays.sort(arr);
int st = 0;
int en = arr.length - 1;
while (st <= en) {
int mid = (st + en) / 2;
if (arr[mid] < target) {
st = mid + 1;
} else if (arr[mid] > target) {
en = mid - 1;
} else {
return 1;
}
}
return 0;
}문제
이분탐색 활용
- 배열에 target이 여러 번 들어있을 경우, 제일 왼쪽의 인덱스 혹은 제일 오른쪽의 인덱스를 반환
- target이 삽입되어도 오름차순 순서가 유지되는 제일 왼쪽/오른쪽의 인덱스를 찾는 문제
⇒ 오름차순 순서가 유지되는 제일 왼쪽/오른쪽의 인덱스의 차이 == 해당 배열 내에 target의 등장 횟수
구현
st와 en: target이 있는 모순이 생기지 않는 인덱스로 가능한 범위
구현
- list가 [1, 2, 3]이고 target이 4일 때 target을 index 3에 삽입해야함을 알 수 있습니다.
즉, 가장 오른쪽이 len-1이 아니라 len이기 때문에 처음에 en을 len으로 둡니다.
인덱스는 mid 이하에 존재한다는 사실을 기록하고 다음 단계를 진행 == 이는 곧en = mid 로 변경이 가능함을 의미
탐색 범위 변화
-
제일 왼쪽 인덱스 구하는 과정
-
제일 오른쪽 인덱스 구하는 과정
구현 시 주의사항
- 잘못된 mid 선택으로 무한루프에 빠질 수 있다.
- st와 en이 1 차이가 나는 경우
- en-st 가 어느 정도 이하로 줄어들면 그 안에서는 선형으로 탐색하도록 구현
LowerBound & UpperBound
구현 코드
/**
* target이 arr에 들어갔을 때, 정렬이 유지되는 제일 왼쪽 index를 구한다.
* @param arr : 정렬된 배열이어야 한다.
* @param target
* @return
*/
public int lower_index(int[] arr, int target) {
int st = 0;
int en = arr.length; // arr.length -1 이 아님을 주의
while (st < en) {
int mid = (st + en)/2;
if (arr[mid] < target) {
st = mid + 1;
} else if (arr[mid] >= target) { //arr[mid] = target인 경우 en을 옮겨준다.
en = mid;
}
}
// 값을 찾는게 아니라 값이 들어갈 수 있는 제일 왼쪽 index를 구하는 것이므로..
return st; //st = en으로 가능한 후보가 1개로 확정될 경우 while문을 탈출함
}
/**
* target이 arr에 들어갔을 때, 정렬이 유지되는 제일 오른쪽 index를 구한다.
* @param arr : 정렬된 배열이어야 한다.
* @param target
* @return
*/
public int upper_index(int[] arr, int target) {
int st = 0;
int en = arr.length; // arr.length -1 이 아님을 주의
while (st < en) {
int mid = (st + en)/2;
if (arr[mid] <= target) { //arr[mid] = target인 경우 st를 옮겨준다.
st = mid + 1;
} else if (arr[mid] > target) {
en = mid;
}
}
// 값을 찾는게 아니라 값이 들어갈 수 있는 제일 왼쪽 index를 구하는 것이므로..
return st; //st = en으로 가능한 후보가 1개로 확정될 경우 while문을 탈출함
}문제
Arrays.binarySearch()
Arrays.binarySearch( 정렬된 배열, 검색할 값); -- 반환타입 int
사용 코드
@Test
void case02() {
int[] arr = {4, 2, 1, 5, 3};
Arrays.sort(arr);
int index = Arrays.binarySearch(arr, 1); //정렬된 배열을 넘겨야 한다.
System.out.println(index); //0
index = Arrays.binarySearch(arr, 2);
System.out.println(index); //1
index = Arrays.binarySearch(arr, 3);
System.out.println(index); //2
index = Arrays.binarySearch(arr, 4);
System.out.println(index); //3
index = Arrays.binarySearch(arr, 5);
System.out.println(index); //4
assertTrue(Arrays.binarySearch(arr, 10) < 0);
}최단 경로
- 한 정점에서 모든 정점으로의 거리를 구할 때 → 다익스트라
- 모든 정점간의 거리를 구할 때 → 플로이드
Activity
[탐색] 이분탐색
[탐색] 이분탐색 - 정렬을 유지할 수 있는 insert index값
blossun commentedon Sep 2, 2021
Union-Fine(합집합 찾기)
[Algorithm] Union-find
blossun commentedon Sep 2, 2021
최소신장 트리 - 크루스칼 알고리즘
최소 신장 트리 정의
신장트리 ?
신장 트리는 주어진 방향성이 없는 그래프의 서브그래프(Subgraph)들 중에서 모든 정점을 포함하는 트리
왼쪽과 같은 그래프가 있을 때, 오른쪽에 있는 그래프들은 전부 왼쪽 그래프의 신장 트리입니다. 일단 모든 정점을 포함한 서브그래프이고, 트리이기 때문입니다.
최소 신장 트리
신장 트리 중에서 간선의 합이 최소인 트리를 의미
크루스칼 알고리즘
Union-Find알고리즘을 알아야 효율적으로 구현할 수 있다.간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다.
현재 선택한 간선이 정점 u, v를 연결하는 간선이라고 하자. 만약 u와 v가 같은 그룹이라면 아무 것도 하지 않고 넘어간다. u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가한다.
최소 신장 트리에 V-1개의 간선을 추가시켰다면 과정을 종료한다. 그렇지 않다면 그 다음으로 비용이 큰 간선을 선택한 후 2, 3번 과정을 반복한다.
Union-Find(합집합 찾기)
https://blog.naver.com/ndb796/221230967614
1. 간선을 크기의 오름차순으로 정렬
2. 제일 낮은 비용의 간선을 선택
3. 같은 그룹으로 만든다.
4. 1과 4를 연결하는 간선을 최소 신장 트리에 추가
5. 그 다음 가장 작은 비용의 간선을 선택해서 1~4 반복
6. 3인 간선은 3과 4를 연결하는 간선만 남았습니다. 3과 4을 연결하는 간선을 택하겠습니다. 색에서 알 수 있듯 3과 4는 그룹이 동일합니다. 그렇기 때문에 아무 것도 하지 않고 넘어갑니다. 당연히 이 간선은 최소 신장 트리에 추가되지 않습니다.
7. 정점이 총 5개인데 4개의 간선을 최소 신장 트리에 추가시켰습니다. 그러므로 최소 신장 트리를 만들어내는데 성공했고 알고리즘은 종료됩니다.
"특정 두 정점이 같은 그룹인지 다른 그룹인지"를 어떻게 판단?
⇒ Union-Find를 이용해서 크루스칼 알고리즘을 구현하면
O(ElgE)로 해결이 가능문제
#297
#299 → 경로 복원
blossun commentedon Sep 2, 2021
플로이드 알고리즘 - 최단 경로 찾기