[알고리즘과 자료구조] 자료구조 ' 배열'에 대해 알아보기

📖 '누구나 자료구조와 알고리즘'책을 공부한 내용을 담고 있습니다.

1장. 자료 구조가 중요한 까닭

코딩을 처음 배울 때의 목표는 우선 제대로 돌아가게 하는 것이지만, 경험이 쌓이면서 코드 품질 측면에 대해 생각해야 한다. 코드 품질의 척도에는 코드 유지 보수성과 코드 효율성이 있다. 그 중 코드의 효율성을 높이기 위해서 자료구조와 성능의 관계에 대해서 이해해야 한다.

1-1. 자료 구조

데이터를 조직하는 방법

각각의 자료 구조가 프로그램의 성능에 미치는 영향이 크다.

1-2. 배열: 기초 자료 구조

• 자료 구조 연산

1. 읽기: 배열의 특정 인덱스의 값을 찾는 것
2. 검색: 특정 값이 배열에 있는지, 그 값의 인덱스를 알아보는 것
3. 삽입: 배열 내 슬롯을 더 만들어 새 값을 추가하는 것
4. 삭제: 배열의 값 중 하나를 삭제하는 것

1-3. 속도 측정

연산은 얼마나 "빠른가"가가 아니라 얼마나 많은 "단계"가 필요한지를 논해야 한다.

시간은 하드웨드에 따라 다르기 때문에 시간을 기준으로 한 속도는 신뢰할 수 없다. 연산의 속도는 계산 단계로 측정한다. 이것이 즉, 연산의 시간 복잡도이다.

1-4. 읽기

배열의 읽기는 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾아보는 것

배열은 값의 위치에 상관없이 한 단계로 특정 값을 읽을 수 있다. 그렇기 때문에 배열 읽기는 매우 효율적인 연산이다.

다음과 같은 컴퓨터의 특징 덕분에 배열에 효율적으로 읽을 수 있다.

1. 컴퓨터는 모든 메모리 주소에 한번에 갈 수 있다.

2. 컴퓨터는 배열을 할당할 때 해당 메모리 주소를 기록해 둔다.

컴퓨터 메모리는 셀로 구성되어 있고, 각 셀에는 특정 주소가 있다. 그 주소에 별도의 검색 과정 없이 바로 접근할 수 있다.

1-5. 검색

배열 검색은 배열에 특정 값이 있는지 알아본 후, 어떤 인덱스에 있는지 찾는 것

배열 검색은 읽기와 반대로 컴퓨터에 값을 제공하고 그 값의 인덱스를 반환하라고 요청한다. 효율성 측면에서도 읽기와 검색은 큰 차이가 있다.
일반적인 배열 검색은 인덱스 0번부터 차례대로 한 셀씩 확인하는 선형 검색을 사용한다. 만약 N개의 셀로 이뤄진 배열 내 찾은 값이 없거나 가장 마지막 셀에 있다면, 최대 N개의 단계가 걸린다.

1-6. 삽입

삽입의 경우, 어느 위치에 삽입하느에 따라 효율성이 다르다.
가장 마지막 위치에 삽입하는 경우 한 단계이지만, 맨 처음이나 중간에 데이터를 삽입하면 삽입할 공간을 만들기 위해 많은 데이터가 이동해야하기 때문에 단계가 늘어난다. 맨 앞의 데이터를 삽입하는 경우, N개의 배열에서 N개의 배열을 이동시키고 삽입하기 때문에 N + 1 단계가 걸린다.

1-7. 삭제

맨 앞과 중간의 셀의 데이터를 삭제할 경우, 삭제 연산은 비어있는 셀을 채워주기 위해 데이터의 이동이 필요하기 때문에 최대 N 단계가 걸린다.
마지막 셀의 데이터를 삭제하는 경우는 데이터를 삭제만 하기 때문에 한 단계가 걸린다.

1-8. 집합

중복 값을 허용하지 않는 자료 구조

배열 기반 집합은 중복을 허용하지 않는 배열이다. 일반 배열과의 연산의 효율성을 비교해보면, 읽기, 검색, 삭제는 일반 배열과 똑같다. 하지만, 삽입 연산은 일반 배열과 다르다.

집합은 값을 삽입하기 전에 전체 데이터를 확인해서 중복을 체크해야 한다. 기본적으로 N개의 셀의 집합에서 N단계의 검색 과정을 거친다. 그 후 값을 삽입하기 때문에 일반 배열보다 많은 단계가 걸린다.

집합의 마지막에 삽입할 경우 최대 N + 1 단계가 필요하다. 하지만, 맨 앞에 삽입하면, N개의 데이터를 확인하고, N개의 데이터를 옭긴 후 삽입하기 때문에 총 2N + 1 단계가 걸린다.

2장. 알고리즘이 중요한 까닭

2-1. 정렬된 배열

값이 정렬된 상태를 유지하는 배열

• 정렬된 배열에서의 삽입
  • 배열 앞 또는 중간에 삽입: N + 2
    • 비교 값이 적더라도 이동해야 할 수가 많아지기 때문에 단계 수가 동일
  • 배열의 맨 끝에 값을 삽입: N + 1
    • 검색 후 기존 값을 이동하지 않아도 되기 때문에 N+1

2-2. 정렬된 배열의 (선형) 검색

• 정렬된 배열과 일반 배열의 비교
  • 배열에 찾는 값이 존재하지 않을 때, 정렬된 배열이 조금 더 효율적이다.
    • 일반 배열은 모든 값을 검색
    • 정렬된 배열은 해당 값보다 큰 값을 발견하면 검색을 중단
  • 찾는 값이 마지막 값이거나 마지막 값보다 큰 경우, 둘다 N단계 ( 최대 N단계 )

function solution(array, search_value) {
  let result = null;

  for (let idx = 0; idx < array.length; idx++) {
    const value = array[idx];

    if (value === search_value) {
      result = idx;
      break;
    } else if (value > search_value) {
      // 찾고 있던 값보다 큰 원소에 도달하면 루프를 일찍 종료
      break;
    }
  }

  return result;
}

2-3. 이진 검색

이진 검색은 정렬된 배열에서 배열의 중간값을 이용하여 연산의 효율성을 높인다.

function solution(array, search_value) {
  // 찾는 값의 상한선과 하한선을 정한다.
  // 최초의 상한선은 배열의 첫 번째 값, 하ㄴ선은 마지막 값
  let lower_bound = 0;
  let upper_bound = array.length - 1;

  //상한선과 하한선의 사이의 가운데 값을 확인하는 루프
  while (lower_bound <= upper_bound) {
    // 상한선과 하한선 사이에 중간 지점 구하기
    let midpoint = Math.floor((lower_bound + upper_bound) / 2);
    let value_at_midpoint = array[midpoint];

    if (search_value === value_at_midpoint) {
      return midpoint;
    } else if (search_value < value_at_midpoint) {
      upper_bound = midpoint - 1;
    } else if (search_value > value_at_midpoint) {
      lower_bound = midpoint + 1;
    }
  }
  // lower_bound = upper_bound면 null을 return
  return null;
}

2-4. 이진 검색 대 선형 검색

• 선형 검색은 최대 검색 단계가 원소 개수만큼 걸린다. 원소의 개수가 두 배면, 최대 검색 단계도 두 배.

• 이진 검색은 배열의 원소 수를 두 배로 늘릴 때마다 1 단계만 늘어난다.

• 100개의 값 갖는 배열에서 최대 단계 수

  • 선형 검색: 100단계
  • 이진 검색: 7단계

• 삽입이 많은 서비스면 일반 배열, 검색이 많은 서비스면 정렬된 배열이 성능에 좋다.

2-6. 연습문제

1. 정렬되노 배열 [2, 4, 6, 8, 10, 12, 13]에서 선형 검색으로 숫자 8를 찾는 데 몇 단계가 걸릴까?

• 4단계, 인덱스 0부터 차례대로 값을 찾아서 4단계가 걸린다.

2. 이진 검색으로 1번 문제를 풀면 몇 단계까 걸릴까?

• 1단계, 이진 검색은 배열의 중간 인덱스를 계산해서 값을 찾기 때문에 중간 인덱스에 해당하는 8를 1단계로 찾을 수 있다.

3. 크기가 100,000인 배열에는 이진 검색에 최대 몇 단계가 걸릴까?

• 17단계, 이진 검색은 배열의 크기가 두 배로 늘릴 때마다 단계가 1단계씩 늘어나는 점을 고려한다.