얼거스 개발 일지

📖 책 정보

모바일 가이드

01. 이진 탐색

• 코드로 구현해보기
• 실행 시간

02. 빅오 표기법

• 많이 사용하는 빅오 실행 시간의 예
• 외판원 문제

---

이진 탐색

입력 : 정렬된 원소 리스트 반환 : null 또는 원소 인덱스

원소 리스트의 중간 값과 찾을 값을 비교하여

중간 값이 더 작으면 왼쪽 구간을 탐색, 중간 값이 더 크면 오른쪽 구간을 탐색 한다.

찾을 값이 나올 때 까지 반복하는 방법!

42개의 원소가 들어있는 리스트에서 7을 찾고자 할 때

맨 처음 원소부터 하나씩 확인한다면 찾는데 7번의 탐색을 하겠지만,

이진 탐색을 사용한다면 4번의 탐색으로 찾을 수 있다.

1. 코드로 구현해보기

public Integer binarySearch(int[] arr, int item) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int guess = arr[mid];

        if (guess == item) return mid;

        if (guess < item)
            low = mid + 1;

        else
            high = mid - 1;

    }

    return null;
}

실행 확인!

public class BinarySearch01 {
    int cnt = 1;

    public static void main(String[] args) {
        BinarySearch01 bs = new BinarySearch01();

        System.out.println(
                "[ result ]___________🚩  " +
                        "index : " +
                        bs.binarySearch(
                                new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42},
                                7
                        ) +
                        " , 탐색 횟수 : " + bs.cnt
        );

    }
}

[ result ]___________🚩  index : 6 , 탐색 횟수 : 4

2. 실행 시간

이진 탐색의 경우 로그시간으로 실행된다.

로그는 거듭제곱의 반대말이다.

log₂16이라는 수는 2를 몇번 곱해야 16이 되는지 묻는것이다. 2x2x2x2 = 16 이므로 log₂16 은 4 이다.

거듭제곱의 반대 행위를 하므로,

로그N 시간이라고 하면

m배로 단축되는 것이다.

N제곱 시간이라고 하면 m배로 늘어나는 것!

    🐢🎈

빅오 표기법

알고리즘이 얼마나 빠른지 표시하는 특별한 방법이다.

1. 많이 사용하는 빅오 실행시간

O(log n)

로그 시간 예 : 이진 탐색

O(n)

선형 시간 예 : 단순 탐색

O(n * log n)

예 : 퀵 정렬과 같이 빠른 정렬 알고리즘

O(n²)

선택 정렬과 같이 느린 정렬 알고리즘

O(n!)

외판원 문제와 같이 정말 느린 알고리즘

간략한 정리

1. 알고리즘의 속도는 시간이 아니라, 연산 횟수가 어떻게 증가하는지로 측정한다.

2. 입력 데이터의 크기가 늘어날 때 알고리즘의 실행 속도가 얼마나 증가하는지 알 수 있다.

3. 알고리즘의 실행 시간은 빅오 표기법으로 나타낸다.

4. O(log n)은 O(n)보다 빠르고, 찾으려는 리스트의 원소의 개수가 증가하면 상대적으로 더 빨라진다.

2. 외판원 문제

외판원 문제는 컴퓨터 과학에서 아주 유명한 문제이다.

왜냐하면 실행시간이 증가하는 것이 너무 엄청나서

아주 똑똑한 사람들도

더 이상 알고리즘을 향상시키는 것이 불가능하다고 생각하기 때문이다.

이 문제를 푸는 한 가지 방법은 도시를 방문하는 모든 경로를 살펴보는 것이다.

그 다음 전체 거리를 더해서 가장 짧은 경로를 선택하면 된다.

도시가 5개이면 120가지 경우가 있으므로 120번의 연산을 하면되고, 도시가 6개가 되면 연산 횟수는 720번이 되고, 도시가 7개가 되면 연산 횟수는 5,040번이 된다.

만약 n개의 도시가 있다면 결과를 계산하는데 n! 번의 연산이 필요하다.

O(n!) 실행 시간이 소요되는 것이다.

이 방법은 아주 안 좋은 방법이지만, 컴퓨터 과학에서 아직 풀지 못한 문제 중 하나이다.

이 문제에 대해 관심이 있다면 이진 탐색 트리를 확인해보면 된다! 이진 탐색 트리는 책의 뒷부분에서 설명!

    🐢🎈