260326_강의 정리

■  C

• array(배열)
  • 같은 type의 데이터를 연속된 메모리에 저장
  • 인덱스를 통한 접근이 빠름
  • 삽입 / 삭제가 느리고 불편함

• linked list
  • 포인터 저장을 위해 앞뒤로 추가 공간을 가지고 있음
  • 삽입 / 삭제가 빠르고 쉬움
  • 순차접근으로 인해 느림

■ Python의 자료 구조

• list
  • 동적 배열
  • 다양한 type이 저장 가능
  • 확장 가능 (미리 여유공간을 두고 확장)
  • 순차 접근에 효율적이고 인덱스를 통한 접근이 빠름
  • 수정 가능 / 순차적 접근 가능
• tuple
  • list와 비슷하게 순서를 가지는 자료 구조
  • 수정 불가능 / 순차적 접근 가능
  • 함수의 반환값/매개변수로 자주 사용
• dict (dictionary)
  • key:value 구조
  • key를 이용한 검색이 빠름
  • key를 hash 함수로 변환하여 데이터를 저장
  • 수정 가능 / 순차적 접근 불가능
• set
  • 중복없는 데이터를 저장하는 자료 구조
  • dict 형태에서 key만 저장(ex. {1,2,3})
  • 집합 연산에 최적화
  • 수정 가능 / 순차적 접근 불가능(순서 보장 x)

■ 수정 가능 여부

• 수정 가능 (mutable) : list, dict, set
• 수정 불가능 (immutable) : tuple, string, int, float

■ 순차 접근 여부

• 순차적 접근 가능 (ordered) : list, tuple, string
• 순차적 접근 불가능 (unordered) : dict, set

■ 선형/비선형

• 선형 자료 구조 (Linear Data Structure)
  • 데이터가 1차원으로 순차적으로 연결된 구조
  • Stack
    • LIFO (Last In First Out) → 마지막에 넣은 데이터가 먼저 나감
    • 한쪽이 막혀 있음 => push/pop이 한쪽 끝에서만 일어남
    • 함수 호출 시 복귀 주소 저장
  • Queue
    • FIFO (First In First Out) → 먼저 넣은 데이터가 먼저 나감
• 비선형 자료 구조 (Non-linear Data Structure)
  • 데이터가 1차원 순서가 아니라 계층적, 복잡하게 연결된 구조
  • Node(노드) : 데이터를 담고 있는 개체 단위, 하나의 점으로 이해하면 편
  • Tree
    • 계층적 구조
    • 검색을 빠르게 하기 위해 사용
    • ex) 이진 검색 트리(Binary Search Tree)
    • 한 방향으로 흐름(루트 -> 리프)
  • Graph
    • 노드 간 양방향
    • 다중 연결 가능
    • 네트워크, 딥러닝 등 활용