읽고 나면 진짜 쉬워지는 자료 구조 - 1. 메모리 안 정보

데이터를 메모리에 저장하는 기본 방법

🔖 1.1. 변수

변수는 라벨이다

  • 변수는 종이 문서를 담는 폴더에 붙은 종이 라벨과 같다. 라벨을 붙인 후에는 폴더의 순서나 위치를 기억할 필요가 없다.

  • 따라서 충분한 정보가 포함된 이름을 사용하는 것이 중요하다.

  • 변수는 저장된 데이터의 타입과 연관이 있기도 하다.

🔖 1.2 복합 자료 구조

복잡하니까 묶어야지

  • 복합 자료 구조는 여러 개별 변수를 한 그룹으로 엮은 구조체나 객체 등을 말한다.

  • 명함은 이름, 이메일 등과 같은 여러 정보를 포함하는 데이터 꾸러미다. (좋은 비유!)

🔖 1.3 배열

배열만의 특징

  • 배열 내 상자들은 컴퓨터 메모리에서 서로 인접해 있으므로, 첫 번째 원소로부터 offset을 계산해 해당하는 위치의 메모리를 읽는 방식으로 각 상자에 쉽게 접근할 수 있다.

  • 이는 접근하려는 상자의 위치와 관계 없이 덧셈 한 번과 메모리 접근만 필요하다는 뜻이다.

  • 그래서 배열은 순서가 있는 항목을 저장할 때 특히 편하다.

  • 삽입 정렬은 배열의 일부를 정렬하고, 이 정렬된 범위를 전체 배열이 정렬될 때까지 확장한다. 알고리즘은 정렬되지 않은 배열의 각 원소를 반복하면서 정렬된 부분의 올바른 위치로 이동한다.

책 내용과 연결짓기

  • 인덱스를 1부터 시작하는 것도 가능하며, 일부 프로그래밍 언어는 이 규칙을 따른다고 한다. 새롭게 알게 된 사실! 대표적으로 R이 벡터나 리스트의 인덱스가 1부터 시작한다고 한다. 다만, C, Python, JavaScript 같은 언어는 0부터 시작하는 걸 기본으로 사용한다. 이는 메모리 주소 기반으로 배열이 설계된 컴퓨터 공학적 전통에서 비롯된 것이라 한다.

  • 책에서 배열은 책장처럼 책을 끼워넣을 수 있는 게 아니라, 일렬로 늘어선 가게와 같다고 말한다. 그래서 때로는 배열이 비효울적인 자료구조라고 말하는 거겠지?

삽입 정렬

  • 삽입 정렬은 배열의 일부를 정렬하고, 이 정렬된 범위를 전체 배열이 정렬될 때까지 확장한다. 즉, 삽입 정렬은 처음에는 작은 정렬된 부분을 만들고, 새로운 요소를 하나씩 추가하면서 이 정렬된 범위를 점점 확장해 나간다. 이렇게 해서 결국 배열 전체가 정렬된다.

  • 따라서 i의 반복을 시작하는 시점에 i-1 이하의 위치에 있는 원소는 모두 정렬되어 있다.

삽입 정렬과 선입 선출

  • 책에서 커피를 신선도 순으로 정렬하는 것을 예시로 들었다. 그렇다면 선입선출(FIFO)과 다른 점은 무엇인가?

  • 삽입 정렬은 단순히 들어온 순서대로 정렬하는 것이 아니라, 새로운 상품이 들어올 때마다 이미 정렬된 구간 속에서 알맞은 자리를 찾아 넣어 전체적으로 "유통기한이 빠른 순서"를 유지하려는 전략에 가깝다.

  • 정리하자면, 선입선출은 들어온 순서를 그대로 따르는 것이고, 삽입 정렬은 새로운 요소를 삽입할 때마다 기준에 맞게 위치를 재조정하는 정렬 방식이다.

중첩된 루프로 삽입 정렬 구현

function insertionSort(A: number[]) {
  const N = A.length;
  let i = 1; // 0은 이미 정렬된 상태로 가정

  while (i < N) {
    let current = A[i]; // 삽입하려는 요소를 임시로 저장
    let j = i - 1; // j는 현재 요소 바로 앞 요소부터 비교 시작

    while (j >= 0 && A[j] > current) {
      A[j + 1] = A[j]; // j번째 요소를 뒤로 한 칸 이동
      j = j - 1; // j를 한 칸 앞으로 이동 (더 앞 요소와 비교 위해)
    }

    A[j + 1] = current; // 이동이 끝난 위치에 current 배치
    i = i + 1; // 다음 위치 작업을 위해 i 증가
  }

  return A;
}

시간 복잡도

  • 삽입 정렬의 시간 복잡도는 평균적으로 O(N²)다.

  • 이미 거의 정렬되어 있는 상태라면 최선의 경우는 O(N) 정도로 더 빨라질 수 있지만.. 최악의 경우와 평균적인 경우에 대략 N²번 정도의 비교와 이동 연산을 수행한다.

  • 이처럼 그다지 효율적이지 않지만, 책에서도 말하듯 배열을 다루는 방식을 이해하는 데 도움을 주는 정렬 알고리즘이다.

  • 삽입 정렬을 통해 알아본 배열의 특징은 세 가지로 정리할 수 있다. 인덱스로 원소 접근하는 것, 새 원소 삽입 시 값을 교환한다는 것, 모든 원소를 반복할 수 있어야 한다는 것.

🔖 1.4 문자열

문자열과 배열의 연관성

  • 문자열은 종종 특수한 종류의 배열로 생각할 수 있는, 순서가 지정된 문자의 리스트다.

  • 문자열은 내부적으로 문자들이 순서대로 나열된 구조를 지니고 있기 때문에 "문자들의 배열" 이라 볼 수 있다. (물론 실제 구현이나 특성은 다름)

  • 정리하자면, str[0]와 arr[0] 모두 "인덱스를 이용해 순서 있는 데이터에 접근한다"는 면에서 비슷하지만, 이 둘을 동일하다고 하기엔 자료형과 언어에 따른 구현상 차이가 있다.

const arr = [1, 2, 3, 4];
const str = 1234;

console.log(arr[1]); // 2
console.log(str[1]); // undefined

두 문자열의 동등성 확인 알고리즘

function stringEqual(str1: string, str2: string): boolean {
  // 두 문자열의 길이가 다르면 바로 false return
  if (str1.length !== str2.length) {
    return false;
  }

  // 길이가 같다면 각 문자를 비교
  for (let i = 0; i < str1.length; i++) {
    // 하나라도 다른 문자가 있으면 false return
    if (str1[i] !== str2[i]) {
      return false;
    }
  }

  // 모든 문자가 같다면 true return
  return true;
}

시간 복잡도

  • 최선의 경우, 첫 문자가 다르면 한 번의 비교로 끝나므로 O(1)다.

  • 하지만 평균적으로 또는 최악의 경우. 모든 문자를 비교해야 하므로 O(N)이다.

배열 vs. 문자열

그렇다면 알고리즘 문제를 해결 할 때, 배열과 문자열 둘 중 어떤 쪽이 더 효율적일까? 문제의 상황에 따라 적절한 자료구조를 선택하면 될듯 하다.

구분

배열(Array)

문자열(String)

장점

• 임의 접근 (O(1)): 인덱스를 사용해 원하는 위치의 요소에 즉시 접근 가능 • 유연성: 다양한 데이터 타입 저장 가능 • 다양한 연산 지원: 삽입, 삭제, 정렬 등 다양한 알고리즘 효율적 구현 가능

• 특수한 연산 지원: 서브스트링, 분할, 결합 등 문자열 전용 함수 제공 • 불변성: 안전하게 공유 가능 • 텍스트 처리 최적화: 패턴 매칭, 정규 표현식 등 텍스트 처리에 유리

단점

• 고정 크기: 일부 언어에서는 크기 고정, 변경 시 새로운 배열 생성 필요 • 메모리 사용: 연속된 메모리 필요, 큰 배열은 메모리 낭비 가능

• 수정의 어려움: 불변인 경우 수정 시 새로운 문자열 생성 필요 • 제한된 데이터 타입: 주로 문자만 저장 가능, 다양한 타입 저장 불가

TC

• 접근 및 수정: 임의 접근 및 수정이 빠름 (O(1)) • 삽입/삭제: 중간에 삽입/삭제 시 O(N) 소요

• 접근: 인덱스 접근은 O(1)이지만, 수정 시 전체 문자열 복사 필요 (O(N)) • 검색/패턴 매칭: 최적화된 알고리즘 사용 시 효율적 (일반적으로 O(N))

효율성

• 데이터 조작: 정렬, 삽입, 삭제 등 일반적인 데이터 조작에 유리 • 다양한 타입: 여러 데이터 타입을 다뤄야 할 때 적합

• 텍스트 처리: 검색, 패턴 매칭 등 텍스트 관련 작업에 최적화 • 문자열 전용 함수 활용: 문자열 관련 기능을 쉽게 구현 가능

메모리

• 유연한 타입 저장: 다양한 타입 저장 가능, 메모리 사용이 유동적 • 연속 메모리: 큰 배열은 메모리 낭비 우려

• 고정된 문자 타입: 문자만 저장, 메모리 사용이 일정 • 불변성: 문자열 변경 시 추가 메모리 사용

📚 관련 문제와 풀이

Previous읽고 나면 진짜 쉬워지는 자료구조Next읽고 나면 진짜 쉬워지는 자료 구조 - 2. 이진 탐색

Last updated