면접을 위한 CS 전공지식 노트 (5) - 자료 구조

• 자료구조
  • 효율적으로 데이터를 관리하고 수정, 삭제, 저장할 수 있는 데이터 집합

복잡도

• 시간 복잡도
  • 문제를 해결하는데 걸리는 시간과 입력의 함수 관계
  • 빅오 표기법
    • 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타내는 것
    • 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없앤 것
  • 효율적인 코드로 개선하는 데 쓰이는 척도
• 공간 복잡도
  • 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양
  • 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 하는 경우도 포함

선형 자료 구조

• 요소가 일렬로 나열되어 있는 자료 구조
• 연결 리스트
  • 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 자료 구조
  • 싱글 연결 리스트
    • next 포인터만 가짐
  • 이중 연결 리스트
    • next 포인터와 prev 포인터를 가짐
  • 원형 이중 연결 리스트
    • 이중 연결 리스트와 동일하되 마지막 노드의 next 포인터가 헤드 노드를 가리킴
• 배열
  • 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합
  • 중복 허용, 순서가 있음
  • 랜덤 접근
    • 직접 접근이라고도 불리며 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능
  • 순차적 접근
    • 랜덤 접근과는 반대로 데이터를 저장된 순서대로 검색해야하는 기능
• 벡터
  • 동적으로 요소를 할당할 수 있는 동적 배열
• 스택
  • LIFO(Last In First Out) 성질을 가진 자료 구조
• 큐
  • FIFO(First In First Out) 성질을 가진 자료 구조

비선형 자료 구조

• 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조
• 그래프
  *정점과 간선으로 이루어진 자료 구조
  • 정점에서 나가는 간선을 해당 정점의 'outdegree'라고 하며, 들어오는 간선을 'indegree'라고 함
  • 가중치
    • 간선과 정점 사이에 드는 비용
• 트리
  • 그래프 중 하나이며 계층적 데이터의 집합
  • 루트 노드
    • 트리의 가장 위에 있는 노드
  • 내부 노드
    • 루트 노드와 리프 노드를 제외한 모든 노드
  • 리프 노드
    • 자식 노드가 없는 제일 아래에 있는 노드
  • 이진 트리
    • 자식의 노드 수가 두 개 이하인 트리
    • 정이진 트리(full binary tree)
      • 자식 노드가 0 또는 두 개인 이진 트리
    • 완전 이진 트리(complete binary tree)
      • 왼쪽에서부터 채워져 있는 이진 트리
      • 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있음
    • 변질 이진 트리(degenerate binary tree)
      • 자식 노드가 하나밖에 없는 이진 트리
    • 포화 이진 트리(perfect binary tree)
      • 모든 노드가 꽉 차 있는 이진 트리
    • 균형 이진 트리(balanced binary tree)
      • 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리
  • 이진 탐색 트리
    • 노드의 오른쪽 하위 트리에는 '노드 값보다 큰 값'이 있는 노드만 포함되고, 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어 있는 트리
  • AVL 트리(Adelson-Velsky and Landis tree)
    • 이진 탐색 트리가 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리
    • 두 자식 서브트리의 높이는 항상 최대 1만큼 차이남
    • 삽입, 삭제를 할 때마다 균형을 맞추기 위해서 트리 일부를 왼쪽 또는 오른쪽으로 회전
  • 레드 블랙 트리
    • 각 노드는 빨강 또는 검정의 색상을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중 트리가 균형을 유지하도록 하는데 사용됨
    • "모든 리프 노드와 로트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다." 등의 규칙을 기반으로 균형을 잡는 트리
• 힙
  • 완전 이진 트리 기반의 자료 구조
  • 최소힙, 최대힙 두 가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리
  • 최대힙
    • 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야함
    • 각 노드의 자식 노드와의 관계도 위와 같은 특징이 재귀적으로 이루어져야함
  • 최소힙
    • 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 작아야함
    • 각 노드의 자식 노드와의 관계도 위와 같은 특징이 재귀적으로 이루어져야함
• 우선순위 큐
  • 우선순위가 높은 요소가 낮은 요소보다 먼저 제공되는 자료 구조
• 맵
  • 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조
  • 레드 블랙 트리 자료 구조를 기반으로 형성, 삽입하면 자동으로 정렬됨
• 셋(set)
  • 특정 순서에 따라 고유한 요소를 저장하는 컨테이너
  • 중복되는 요소는 없고 오로지 유니크한 값만 저장하는 자료구조
• 해시테이블
  • 데이터를 해시 값으로 매핑한 테이블
  • 정렬이 보장되지 않음