Chapter 03. 검색

 

chapter 03 - 1 검색 알고리즘

  데이터 집합에서 원하는 값(key)을 가진 요소를 찾아내는 알고리즘

 

- 특정 항목 (key)에 주목하는 것이 검색의 특징 

  - ex) 국적이 한국인 사람 찾기 : 국적 특성 중 key = "한국"

  - ex) 고등학생 찾기 : 나이 특성 중 key = "17세 이상 20세 미만" (구간이 될 수도 있음)

 

 

** 배열 검색에서 활용하는 알고리즘

    - 선형 검색

        - 무작위의 데이터 집합 속에서 검색 수행

    - 이진 검색

        - 일정한 규칙을 가진 데이터 집합 속에서 아주 빠른 검색 수행

    - 해시법

        - 추가, 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색 수행

        - 체인법 : 같은 해시 값을 가지는 데이터를 선형 리스트로 연결

        - 오픈 주소법 : 데이터의 해시 값이 충돌하는 경우 다시 해시 배정

 

  ** 해당 목적에 대해 알고리즘이 여러 가지인 경우, 

      용도 / 목적 / 수행 속도 / 자료구조 등 고려하여 알고리즘 선택하기 ** 

 

 

 

chapter 03 - 2 선형 검색

 

선형 검색 (linear search; sequential search)

직선 배열에서 원하는 키 값을 가진 요소를 만날 때까지 처음부터, 순서대로 요소를 검색하는 알고리즘

 

- 두 가지 결과 존재 (종료 조건)

    ① 검색한 키 값을 가진 요소 발견한 경우

        → 검색 성공

    ② 검색할 키 값을 가진 요소 발견 실패하여 배열의 끝까지 간 경우

        → 검색 실패

 

  보초법 (sentinel method)

종료 조건 검사 비용을 반으로 줄이는 방법

 

검색 전 key 값 (저장하는 key값을 보초)을 배열의 끝에 저장

→ 보초까지 검색하면 종료 조건 ②이 성립하기 때문에 종료 판단을 한 번만으로도 가능함. 

 

 

 

 

 

 

보초값 추가하기 위해 배열 생성 시 요소 수보다 하나 더 크게 생성

 

 

 

chapter 03 - 3 이진 검색

 

이진 검색 (binary search)

데이터 배열이 이미 정렬되어 있다는 전제 조건 하에 검색하는 알고리즘

이진 검색 진행 할 때마다 검색 범위는 거의 반으로 좁혀짐

 

- leftIndex, rightIndex, centerIndex 변수 생성 // 각각 검색 범위의 왼쪽, 오른쪽, 중앙 인덱스 의미

- 범위 좁혀나가는 과정에서 필요한 조건

  ① array[centerIndex] < key

      - key가 오른쪽 범위에 존재함을 의미하므로 leftIndex = centerIndex + 1로 업데이트

  ② array[centerIndex] > key

      - key가 왼쪽 범위에 존재함을 의미하므로 rightIndex = centerIndex - 1로 업데이트

 

  * 이진 검색의 전제 조건이 정렬이므로 이전 요소보다 작거나 크면 해당 정렬에 따라 다시 입력을 요구함.

 

 

복잡도 (complexity)

알고리즘의 성능을 객관적으로 평가하는 기준

 

① 시간 복잡도 (time complexity) : 실행에 필요한 시간 평가

② 공간 복잡도 (space complexity) : 기억 영역과 파일 공간이 얼마나 필요한가를 평가

 

- ex) 선형 검색의 시간 복잡도

 

 

 

---

  ① int i = 0;                      // 처음 한 번만 실행 하므로 O(1)

  ② while (i < n) {              // 배열의 맨 끝에 도달했는지 판단하는 평균 횟수 n / 2이므로 O(n)

  ③     if (a[i] == key)        // 현재 검사하고 있는 요소와 key 값이 같은지 판단하는 평균 횟수 n / 2이므로 O(n)

  ④         return i;              // 검색 성공 시 한 번 실행 O(1) 

  ⑤     i++;                        // while문 내에서 조건 검사한 만큼 수행되므로 n / 2번 수행 O(n)

      }

  ⑥ return -1;                   // 검색 실패 시 한 번 실행 O(1)

    → 시간 복잡도 : O(n)

* O(f(n)) + O(g(n)) = O(max(f(n), g(n)))

    → 2개 이상의 복잡도로 구성된 알고리즘의 복잡도는 차원이 가장 높은 복잡도 선택

* 왜 O(n / 2)가 아니라 O(n)으로 표기하나요 !? 

    → n이 무한대로 커진다면, n / 2와 n 값의 차이가 큰 영향을 미치지 않기 때문

    → O(100)도 O(1)로 표기하는 것도 비슷한 이유

 

- ex) 이진 검색의 시간 복잡도

 

 

 

 

 

---

 ① int leftIndex = 0;                                                             // O(1)

 ② int rightIndex = n - 1;                                                     // O(1)

     do {

 ③     int centerIndex = (leftIndex + rightIndex) / 2;           // O(log n)

 ④     if (a[centerIndex] == key)                                           // O(log n)

 ⑤        return centerIndex;                                                  // 검색 성공 시 O(1)    

 ⑥     else if (a[centerIndex] > key)                                      // O(log n)

 ⑦         rightIndex = centerIndex - 1;                                 // O(log n)

         else

 ⑧         leftIndex = centerIndex + 1;                                   // O(log n)

 ⑨ } while (leftIndex <= rightIndex);                                    // O(log n)

 ⑩ return -1;                                                                         // 검색 실패 시 O(1)  

    → 시간 복잡도 : O(log n)

 

- 연습문제

   - 실습 예제 3-3 참고하여 seqSearchSen 메서드가 for문 사용하는 프로그램

        (ⓒⓞⓓⓔ) ex01.java

   - 선형 검색의 스캐닝 과정 상세하게 출력하는 프로그램

        (ⓒⓞⓓⓔ) ex02.java

   - 요솟수가 n인 배열 a에서 key와 일치하는 모든 요소의 인덱스를 배열 idx의 맨 앞부터 순서대로 저장한 후, 일치한 요솟수 반환하는 메서드 작성

        (ⓒⓞⓓⓔ) ex03.java

   - 이진 검색 과정 상세하게 출력하는 프로그램

        (ⓒⓞⓓⓔ) ex04.java

   - 이진 검색 알고리즘 참고하여 중복되는 경우 가장 앞의 요소를 찾는 프로그램

        (ⓒⓞⓓⓔ) ex05.java

 

 

Arrays.binarySearch에 의한 이진 검색

- Java에는 이진 검색하는 메서드 표준 라이브러리로 제공 (import java.util.Arrays;)

- binarySearch 메서드

   - 오름차순으로 정렬된 배열 a를 가정, 키 값은 key로 이진검색

   - 자료형에 따라 9가지 방법으로 오버로딩되어 있음. 

   - static int binarySearch(byte[] a, byte key)

      - byte, char, double, float, int, long, short, Object 등의 자료형에 따라 오버로딩

      - static int binarySearch(Object[] a, Object key)

        - 자연정렬 방법으로 요소의 대소 관계 판단

        - 정수, 문자열 배열에서 검색할 때 적당

      - static <T> int binarySearch(T[ ] a, T key, Comparator<? super T> c)

        - "자연순서"가 아닌 순서로 정렬된 배열, 논리적으로 갖지 않는 클래스 배열에서 검색 시 적당

   - 검색 성공한 경우, key와 일치하는 요소의 index return

   - 검색 실패한 경우, - (key보다 큰 요소 중 첫번째 요소의 index) - 1 return

 

- 연습문제

   - 실습 예제 3-5 수정하여 검색 실패 시 삽입 포인트 값 출력하는 프로그램

        (ⓒⓞⓓⓔ) ex06.java

 

 

 

* 참고 내용 *

  무한 루프 구현

 

 

 

 

 

 

   - 무한 반복 구조이지만, break문 혹은 return문 통해 빠져나올 수 있음

   - do-while문에서는 끝까지 읽지 않으면 무한 루프인지 알 수 없기 때문에 권장하지 않음

 

  시간 복잡도

    -  1 < log n < n < n log n < n^2 < n^3 < n^k < 2^n  (2^n : 2의 n제곱 의미)

 

  클래스 메서드와 인스턴스 메서드

  - Java 메서드는 클래스 메서드와 인스턴스 메서드 두 가지가 존재

    ① 인스턴스 메서드 (비정적 메서드)

        - static 없이 선언한 메서드

        - "클래스형 변수 이름.메서드 이름"으로 호출

    ② 클래스 메서드 (정적 메서드)

        - static을 붙여 선언한 메서드

        - "클래스 이름.메서드 이름"으로 호출

 

  제네릭

  - 처리 대상의 자료형에 의존하지 않는 클래스(인터페이스) 구현 방식

  - 제네릭 클래스 선언

    - class 클래스이름 <파라미터> { // }

    - interface 인터페이스 이름 <파라미터1, 파라미터2, ... > { // }

  - 파라미터 이름 작성 방법

    - 1개의 대문자 사용

    - 컬렉션 : E, 맵의 키와 값 : K, V, 일반적으로는 T 사용

  - <? extends T> // 클래스 T의 서브 클래스 전달받음

    <? super T> // 클래스 T의 슈퍼 클래스 전달받음

 

  자연 정렬

문자열 정렬보다 사람들에게 더 자연스럽고 익숙한 정렬

- 문자열 정렬의 경우, 1.txt 10.txt 100.txt 2.txt 등으로 정렬

- 자연 정렬의 경우, 1.txt 2.txt 10.txt 100.txt 등으로 정렬

- 자연 정렬을 하려면 클래스 선언 시 따로 선언 필요

  - class A implements Comparable<A> {

        public int compareTo(A c) { // compareTo 메서드 구현 }

        public boolean equals(Object c) { // equals 메서드 구현 }

    }

- 자연 정렬로 정렬되지 않은 경우 제네릭 메서드 사용

  - 제네릭 메서드(generic method)

    - 첫 번째 매개변수는 검색 대상, 두 번째 매개변수는 key 값

       세 번째 매개변수는 배열 요소의 순서, 대소관계 판단 여부 등을 전달

    - 자료형에 구애 받지 않는 메서드