[자료구조] 2주차 - 배열 (Array)

List

리스트의 정의

• 유일한 원소들의 나열
• 각 원소들은 인덱스에 대응됨

List의 구현에는 Array와 Linked list가 있음

• 배열 (Array) : 메모리에 배열의 크기보다 더 큰 공간이 허용 될 때 사용
• 연결 리스트 (Linked list) : 연속된 공간이 없어도 사용 가능

Array

• 리스트를 index를 이용해서 구현한 구조
• 연속적으로 할당된 기억 공간
• 모든 언어에서 기본적으로 제공
• 모든 원소들이 index에 대응
• n개의 자료를 하나의 주소로 접근 가능

기본 연산 - 생성(create), 인출(retrieve), 저장(store)

추가 연산 - 검색(search), 추가(insert), 제거(delete), ···

검색(Search)

찾는 원소(key element)가 배열에 있는지 여부를 판단

또는 해당 원소의 인덱스를 리턴

• 선형 검색(linear search)

  • 완전 검색(exhaustive search) 또는 순차 검색(sequential search)
  • 차례로 방문하면서 원소를 확인
  • 시간 복잡도 : O(n)

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

• 이진 검색(binary search)

  • 분할 정복 (divide & conquer) 알고리즘
  • 배열의 중간 원소와 key element를 비교하여 배열을 분할함으로써 수행
  • 정렬된 배열에서만 적용
  • 시간 복잡도 : O(log n) // T(n) = T(n/2)

  index binary_search ( Arrayarr, indexs, indexe, elt x) {
      //s: start index, e: end index
      if ( s == e ) 
          return (arr[s] == x) ? s : -1;
  
      int mid = (s + e)/2;
      if (x == arr[mid]) 
          return mid;
      else if (     arr[mid] > x ) 
          return binary_search ( arr, s, mid-1, x );
      else     
          return binary_search ( arr, mid+1, e, x );
  }

  index binary_search ( Arrayarr, elt x) { //재귀를 쓰지 않은 방법
      int s = 0; int e = count –1; int mid;
  
      while ( s <= e ) {
          mid = (s + e)/2;
          if (x == arr[mid])
              return mid;
          else if ( arr[mid] > x )
              e = mid –1;
          else 
              s = mid + 1;
      } return -1;
  }

추가(Insert)

배열의 적절한 위치에 새로운 원소를 삽입하는 연산

새로운 원소가 삽입될 위치를 명확하게 지정하지 않음

insert, insert_by_index, insert_by_value

알고리즘 : 새로운 원소 x를 배열 arr에 추가하는 과정

1. x를 추가할 위치를 결정 : x보다 큰 값들 중에서 가장 작은 값의 위치
2. 추가할 위치의 원소를 옮겨서 공간 확보
3. 원소를 추가
4. 배열의 크기(count)를 증가

Array insert_by_value (Array){
    //여러가지 예외 처리 ( count ==0, count == Size, x<arr[0], ···)

    // 1. x를 추가할 위치를 결정 
    for ( i= 0; i< count; i++ ) {
        if ( arr[i] > x ) 
            break; 
    } 
    // 2. 추가할 위치의 원소를 옮겨서 공간을 확보(->)
    for ( j = n-1; j >= i; j--)
        arr[j+1] = arr[j];
    // 3. 원소를 추가
    arr[i] = x;
    // 4. 배열의 크기(count)를 증가
    count++; return arr
}

시간 복잡도 : O(n) //1. O(k) 2. O(n-k) 3. O(1), 4. O(1)

제거(Delete)

배열에서 원소 삭제, 빈 공간이 남지 않도록

delete_by_value, delete_by_index

알고리즘

1. 제거할 원소 x를 배열 arr에서 찾음
2. 제거할 원소 뒤에 있는 원소들을 앞으로 이동
3. 배열의 크기 count를 감소

Arraydelete ( Array arr, eltx) {
    //각종 예외 처리 (count == 0, x == arr[count-1], ···)

// 1. 제거할원소(x)를배열(arr)에서찾음
    for ( inti= 0; i< count; i++ )
        if ( arr[i] ==x )
            break;
    if ( i== count )
        return;
// 2. 제거할원소뒤에있는원소들을앞으로이동(<-)
    for ( intj = i; j < count-1; j++)
        arr[j] = arr[j+1]; 
    // 3. 배열의크기(count)를감소 
    count--;
return arr;
}

시간 복잡도 : O(n) //1. O(k), 2. O(n-k), 3. O(1)