[자료구조] 05. Array

본 내용은 필자가 학부 자료구조 수업내용을 공부하기 위해 정리한 것임을 알려드립니다.

5.1. 배열 (Array)

배열의 성질

• list를 index를 이용하여 구현
• 연속적으로 할당 된 공간
• 프로그램 언어에서 기본적으로 제공
• 배열의 모든 원소는 index에 대응
• n개의 자료를 하나의 주소로 접근 가능
  • 배열의 첫번째 요소의 메모리 주소를 기본 주소라고 한다.
  • arr[0] 메모리 주소에 접근하면 배열의 끝까지 접근 가능하다.

메모리에서 배열의 구현

int mylist[5];를 C언어에서 선언했다고 가정하자.

1. int mylist[5]; 선언
2. OS에 배열 요청
3. OS는 메모리에게 여유 공간이 있는 지 묻는다.
4. Memory 승인
5. 주소를 할당

mylist 배열은 시작주소로 23040번지를 할당했다고 가정해보자.

5개의 메모리를 선언했으므로 23040 ~ 23044번지 까지 연속된 메모리를 할당받는다.

mylist 배열의 주소 == mylist[0]의 주소, n개의 자료를 하나의 주소로 접근 가능하다.

배열의 친구들

• arr : 배열의 주소
• size : 배열의 크기 (할당받은 메모리의 크기)
• count : 배열에 저장된 현재 원소의 갯수
  • count <= size
  • 반드시 0으로 초기화 하여 사용할 것

정적 배열 할당

#define SIZE 100 
{
    int count = 0;
    int arr[SIZE];
}

동적 배열 할당

#define SIZE 100
{
    int count = 0;
    int *arr = calloc(SIZE,sizeof(int)); 
}

배열의 연산

• 생성(Create) : int L[10];
• 인출(Retrieve) : int x = L[5];
• 저장(Store) : L[5] = x;

---

5.2. 배열의 검색

• 정렬된 배열

1. linear_search(A,x)
2. binary_search(A,x)

• 정렬되지 않은 배열

1. linear_search(A,x)

검색(Search)

내가 찾는 원소의 index를 return. 원소가 없으면 -1 또는 NULL return

선형 검색(Linear Search)

• 완전 검색, 순차 검색
• 첫번째 원소부터 차례로 방문
• Unsorted Array 적용 가능

index linear_search(Array arr, elt x)
{
    for (int i=0; i<n; i++) {
        if (arr[i] == x)
            return i;
        else
            return -1;
    }
}

• 최악의 경우 : O(n)
• 평균의 경우 : O(n/2)
  • 배열의 중간에서 key값을 찾은 경우
  • O(n)
• 최선의 경우 : O(1)
  : 바로 key값을 찾은 경우

이진 검색(Binary Search)

• 정렬 된 배열에서만 사용 가능
• Divide & Conquer(분할 정복) 알고리즘
  • 배열 중간 원소와 key element 비교.
  • 배열 분할 하며 검색.
• 배열의 중간 원소(mid)를 찾아 배열을 절반으로 Divide, 탐색을 재귀적으로 수행

  index binary_search(Array arr, index s, index e, elt x)
  {
      if (s==e)
          return (arr[s] == x) ? s : -1;
          //원소가 1개인 배열, start와 end가 같을 때
      int mid = (s + e) / 2;
      
      if (x == arr[mid])
          return mid;
      else if (arr[mid] > x) //key는 mid보다 작기 때문에
          return binary_search(arr, s, mid-1, x);
                                      //end를 mid-1로 설정 (Divide)
      else
          return binary_search(arr, mid+1, e, x);
                                  //key가 mid보다 크므로 mid+1을 start로 설정 (Divide)
  }

• recursive 구현
  • T(n) = T(n/2) + O(1)

Recursive의 단점을 보완한 Iterative 이진 검색 구현

index binary_search(Array arr, elt x)
{
    int s = 0;
    int e = count-1;
    int mid;

    while(s<=e) {
        mid = (s + e) / 2;
        
        if (x == arr[mid])      //mid 값이 x값과 일치하면 리턴
            return mid;

        else if (arr[mid] > x)  //mid 인덱스 값보다 x값이 작으면
            e = mid - 1;        // Divide
        
        else                    //mid 인덱스 값보다 x값이 크면
            s = mid + 1;        //Divide
    }
    return -1;
}

• 최악의 경우 : O(logn)
• 최선의 경우 : O(1) - key값을 바로 탐색했을 때