[자료구조] Java 검색 알고리즘 + 스택, 큐

 검색

  선형 검색 

    - 완전검색, 순차검색 이라고 불리기도 한다.
    - 배열의 가장 좌측부터 시작하여 찾으려는 값과 하나씩 배열의 각 요소를 비교하는 방법이다.
    - 찾으려는 값을 발견하면 배열의 해당 인덱스를 반환하며, 찾으려는 값이 없다면 -1을 반환한다.
    - 찾으려는 값이 여러개라면 최초 발견된 인덱스를 반환하고 검색이 종료된다.
    - 정렬되지 않은 배열에서도 적용할 수 있다.
    - 시간복잡도는 평균 n/2회로 O(n) 이다.
    - 검색의 종료 조건
     1. 검색할 값과 같은 요소를 발견한 경우 (n회, 평균 n/2회)
     2. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 (n+1 회)

  소스코드는 다음과 같다.

int search(int arr[], int n, int x) { // 매개변수 : 배열이름, 배열의 길이, 찾으려는 값
    for (int i = 0; i < n; i++) { 
        if (arr[i] == x) { // 종료조건 1 
            return i; 
        }
    }
    return -1; // 종료조건 2 
}

//출처: https://yeolco.tistory.com/74 [열코의 프로그래밍 일기]

 

 보초법(Sentinel Method)

   - 선형검색은 종료조건을 모두 판단하기 때문에 검사 비용이 많이 든다고 볼 수 있다. 원하는 key값을 찾지 못하는 경우에 관한

     종료조건을 제거함으로 종료 판단횟수를 1로 줄이는 방법이 보초법이다.

   - 검색 전, 검색하고자 하는 key 값을 배열의 맨 끝 요소에 저장한다.

   - 검색 결과, key 값이 원래 data에 존재하지 않아도 검색결과가 없는 경우에 관한 종료조건이 필요 없다.

 

 소스코드는 다음과 같다.

int sentinelSearch(int arr[], int n, int x) { // 매개변수 : 배열이름, 배열의 길이, 찾으려는 값
    arr[n] = x;
 
    for (int i = 0; i < n; i++) { 
        if (arr[i] == x) { 
            return i; 
        }
    }
    //return -1; 마지막 인덱스에 찾는 값이 있으므로 종료조건 2번이 필요 없다.
}

 

 이진검색

  - 검색 반경을 반으로 나뉘어 반복하는 검색 방법이다.

  - 정렬 된 배열에서만 사용 가능 하다.

  - 찾으려는 값을 배열의 중간값과 비교하여 그 값이 더 작다면 우측배열, 크다면 좌측 배열로 이동하여 반복한다.

  - 분할 정복 알고리즘의 규칙에 따라 설계된 방법이다.

  - 시간 복잡도는 평균 k = 2ⁿ 을 log 씌운 logk = n 으로 O(logⁿ) 이다.

 

 소스코드는 다음과 같다.

int binarySearch(int arr[], int l, int r, int x) { // 매개변수 : 배열이름, 배열 시작 인덱스, 배열 끝 인덱스, 찾으려는 값
   if (r >= l) { 
        int mid = l + (r - l)/2; // 중간 값 선택

		if (arr[mid] == x) return mid; // 검색 성공
        
        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x); // 좌측 배열 탐색
        else return binarySearch(arr, mid+1, r, x); // 우측 배열 탐색
   }
   return -1;  // 검색 실패
} 

//출처: https://yeolco.tistory.com/74 [열코의 프로그래밍 일기]

 

---

스택과 큐

 추상자료형(Abstract Data Type - ADT)

    - 추상자료형은 수학적 모델을 가졌으며 구현 방법을 따로 명시하고 있지 않다는 점이 자료 구조와 다르다.

   - 인터페이스와 구현을 분리하여 추상화 계층을 둔 것이다. 

   - 대표적으로 복소수, 리스트, 스택, 큐, 맵, 우선순위 큐, 집합 등이 있다.

 

 스택 (Stack)

   - 후입선출(Last In First Out - LIFO) 형태의 자료구조이다.

 

  일반적으로 구현에 필요한 메서드

• pop
  스택의 마지막에 위치한 데이터를 추출한 후 스택에서 삭제.
• push
  스택의 마지막에 데이터를 삽입.
• isEmpty
  스택이 비어있는지 확인.
• peek
  스택의 마지막에 위치한 데이터를 추출. (삭제하지 않음)

 

큐 (Queue)

  - 선입선출(First In First Out - FIFO) 형태의 추상자료형이다.

 

 일반적으로 구현에 필요한 메서드

• add
  큐의 마지막에 데이터를 삽입하고 성공하면 true를 반환.
• peek
  큐의 맨 앞에 데이터를 반환, 큐가 비어있으면 null을 반환.
• element
  큐의 맨 앞에 데이터를 반환, 큐가 비어있으면 Exception을 발생.
• poll
  큐의 맨 앞에 있는 데이터를 추출한 후 큐에서 삭제. 비어있으면 null을 반환.
• remove
  큐의 맨 앞에 있는 데이터를 추출한 후 큐에서 삭제, 비어있으면 Exception을 발생.