[탐색]

[blossun]

이분탐색

구현

• 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;
    }

• 강의자료

문제

#253

이분탐색 활용

• 배열에 target이 여러 번 들어있을 경우, 제일 왼쪽의 인덱스 혹은 제일 오른쪽의 인덱스를 반환
• target이 삽입되어도 오름차순 순서가 유지되는 제일 왼쪽/오른쪽의 인덱스를 찾는 문제
  ⇒ 오름차순 순서가 유지되는 제일 왼쪽/오른쪽의 인덱스의 차이 == 해당 배열 내에 target의 등장 횟수

구현

• st와 en : target이 있는 모순이 생기지 않는 인덱스로 가능한 범위

구현

• list가 [1, 2, 3]이고 target이 4일 때 target을 index 3에 삽입해야함을 알 수 있습니다.
  즉, 가장 오른쪽이 len-1이 아니라 len이기 때문에 처음에 en을 len으로 둡니다.

• 인덱스는 mid 이하에 존재한다는 사실을 기록하고 다음 단계를 진행 == 이는 곧 en = mid 로 변경이 가능함을 의미

탐색 범위 변화

1. 제일 왼쪽 인덱스 구하는 과정
   

2. 제일 오른쪽 인덱스 구하는 과정
   

구현 시 주의사항

• 잘못된 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문을 탈출함
    }

문제

#255

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);
    }

• 참고

---

최단 경로

• 한 정점에서 모든 정점으로의 거리를 구할 때 → 다익스트라
  • 21.09.03 [백준] 1753 최단경로 - 다익스트라 알고리즘 #300
• 모든 정점간의 거리를 구할 때 → 플로이드
  • 21.09.02 [백준] 11780 플로이드 2 #299
  • 21.09.02 [백준] 11404 플로이드 #298

[blossun]

Union-Fine(합집합 찾기)

package dev.solar.algorithm;

public class UnionFind {
    public static void main(String[] args) {
        int[] parent = new int[11];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
        union(parent, 1, 2);
        union(parent, 2, 2);
        union(parent, 3, 4);
        union(parent, 5, 6);
        union(parent, 6, 7);
        union(parent, 7, 8);
        System.out.println("1과 5는 연결되어 있나요 ?" + isEqualParent(parent, 1, 5));
        union(parent, 1, 5);
        System.out.println("1과 5는 연결되어 있나요 ?" + isEqualParent(parent, 1, 5));

    }

    // 각 부모 노드를 합친다.
    private static void union(final int[] parent, final int prev, final int cur) {
        int prevParent = getParent(parent, prev);
        int curParent = getParent(parent, cur);
        if (prevParent < curParent) {
            parent[curParent] = prevParent;
        } else {
            parent[prevParent] = curParent;
        }
    }

    // 부모노드 정보를 가져온다.
    private static int getParent(final int[] parent, final int x) {
        if (parent[x] == x) {
            return x;
        }
        return getParent(parent, parent[x]);
    }

    // 같은 부모 노드를 가지는지 확인
    private static int isEqualParent(final int[] parent, int a, int b) {
        a = getParent(parent, a);
        b = getParent(parent, b);
        return a == b ? 1 : 0;
    }
}

[blossun]

최소신장 트리 - 크루스칼 알고리즘

최소 신장 트리 정의

신장트리 ?

신장 트리는 주어진 방향성이 없는 그래프의 서브그래프(Subgraph)들 중에서 모든 정점을 포함하는 트리

• 트리 ? 사이클이 없고 연결된 그래프

왼쪽과 같은 그래프가 있을 때, 오른쪽에 있는 그래프들은 전부 왼쪽 그래프의 신장 트리입니다. 일단 모든 정점을 포함한 서브그래프이고, 트리이기 때문입니다.

• 그래프의 정점이 V개일 때 신장 트리는 V-1개의 간선을 가지고 있음
• 주어진 그래프가 연결 그래프일 때만 신장 트리가 존재함

최소 신장 트리

신장 트리 중에서 간선의 합이 최소인 트리를 의미

• 최소 신장 트리는 동일한 그래프에서 딱 한 개로 정해지지 않고 여러 개일 수 있습니다.

크루스칼 알고리즘

• Union-Find 알고리즘을 알아야 효율적으로 구현할 수 있다.

1. 간선을 크기의 오름차순으로 정렬하고 제일 낮은 비용의 간선을 선택한다.

2. 현재 선택한 간선이 정점 u, v를 연결하는 간선이라고 하자. 만약 u와 v가 같은 그룹이라면 아무 것도 하지 않고 넘어간다. u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가한다.

3. 최소 신장 트리에 V-1개의 간선을 추가시켰다면 과정을 종료한다. 그렇지 않다면 그 다음으로 비용이 큰 간선을 선택한 후 2, 3번 과정을 반복한다.

Union-Find(합집합 찾기)

https://blog.naver.com/ndb796/221230967614

• code

1. 간선을 크기의 오름차순으로 정렬

2. 제일 낮은 비용의 간선을 선택

• 3인 간선은 3개가 있지만 그 중 아무거나 선택 → 1과 4를 연결하는 간선을 선택

3. 같은 그룹으로 만든다.

4. 1과 4를 연결하는 간선을 최소 신장 트리에 추가

5. 그 다음 가장 작은 비용의 간선을 선택해서 1~4 반복

6. 3인 간선은 3과 4를 연결하는 간선만 남았습니다. 3과 4을 연결하는 간선을 택하겠습니다. 색에서 알 수 있듯 3과 4는 그룹이 동일합니다. 그렇기 때문에 아무 것도 하지 않고 넘어갑니다. 당연히 이 간선은 최소 신장 트리에 추가되지 않습니다.

7. 정점이 총 5개인데 4개의 간선을 최소 신장 트리에 추가시켰습니다. 그러므로 최소 신장 트리를 만들어내는데 성공했고 알고리즘은 종료됩니다.

"특정 두 정점이 같은 그룹인지 다른 그룹인지"를 어떻게 판단?

• Flood Fill을 이용 → 최종 시간복잡도는 O(ElgE + VE)가 되어 많이 비효율적
• Union-Find를 사용 → 상수 시간에 확인 O(1)

⇒ Union-Find를 이용해서 크루스칼 알고리즘을 구현하면 O(ElgE)로 해결이 가능

문제

#297
#299 → 경로 복원

[blossun]

플로이드 알고리즘 - 최단 경로 찾기