자료구조#1

• #1 What is data structure?

  데이터의 효율적인 접근 및 조작을 가능하게 해주는 저장 및 관리 방식
  자료 구조화 → 데이터를 효율적으로 사용

  base: 데이터가 컴퓨터에 어떻게 저장되는지 이해해야 함.

  1. Storage: 데이터가 영구적으로 저장되는 곳.
     데이터의 저장 & 받아오는 데 오래 걸림
  2. Memory: 데이터가 임시로 저장되는 곳.
     데이터의 저장 & 받아오는 데 빠름

• #2 RAM(random access memory)

  메모리
  -일정한 칸으로 나눠져 있다.
  -각 칸에 데이터를 저장할 수 있다.
  -각 칸에 자신만의 주소가 있다.

  RAM: 임의 접근 메모리
  -임의 접근: 저장 위치를 알면 접근 시 항상 일정한 시간이 걸림.
  -시간복잡도: O(1)

• #3 Reference

  -주소와 레퍼런스는 별개의 개념.
  -데이터에 접근할 수 있게 해주는 값
  -"주소"에 비해 보다 포괄적인 표현
  -but 자료 구조 공부 시 "주소 = 레퍼런스"라고 판단해도 무방.

  python의 id함수는 데이터의 메모리 주소를 정수형으로 알려준다.

    list1 = [0, 1]
    list2 = list1
    list3 = [1, 2, 3]
    print(id(list1)) 
    print(id(list2))
    print(id(list3))
    # Aliasing을 통해 list1과 list2를 같게 한다

• #4 C 배열 VS Python 리스트

  C 배열

  • 크기가 고정돼 있다.

  • 같은 타입의 데이터만 담을 수 있다.

    Python 리스트

  • 크기 고정 X

  • 다양한 타입의 데이터 저장 O

    배열 접근 연산

  • O(1)

    배열 탐색 연산

  • O(n) (선형탐색)

• #5 배열

  정적 배열(통상적인 배열)

  • 크기 고정(요소 수 제한)

    동적 배열(Dynamic Array)

  • 크기 변함(요소 계속 추가 가능)

  • 정적 배열로 만들어짐. 다만 배열의 크기를 상황에 맞게 조절. 미리 여유 있게 생성.

    표

    추가 연산(append operation)
    -case 1: 정적 배열 남는 공간이 있을 때
    ⇒ O(1) best
    -case 2: 정적 배열 꽉 찼을 때
    ⇒ O(n) worst

    #일반적인 시간복잡도 : 최악의 상황을 상정.
    but 동적 배열의 경우 case 1의 경우가 자주 발생. 비합리적.

    → 분할 상환 분석(Amortized Analysis). 연산에 걸리는 시간의 평균을 도출. "할부" 개념.
    → O(1)

    동적 배열의 추가(append) 연산은 최악의 경우 O(n)O(n)이 걸리지만, 분할 상환 분석을 하면 O(1)O(1)이 걸린다.

    삽입 연산(insert operation)
    -case 1: 정적 배열 남는 공간이 있을 때
    ⇒ O(n)
    -case 2: 정적 배열 꽉 찼을 때
    ⇒ O(n)

    삭제 연산 동작
    - O(1) ~ O(n)

    동적 배열에서 맨 끝 데이터를 삭제하는 연산은 최악의 경우 O(n)O(n)이 걸리지만, 분할 상환 분석을 적용하면 O(1)O(1)이라고 할 수 있다.

    낭비하는 공간
    배열: 크기가 고정! 낭비 X!
    동적 배열: 낭비할 수도 있음 → O(n)