[algorithm] 자료구조와 알고리즘

• 자료구조와 알고리즘의 관계
  • 자료구조 
    • 컴퓨터에서 데이터 사이의 논리적 관계를 표현하고 조직화하는 방법
    • 프로그램 <- 자료구조 + 알고리즘
  • 기본 자료구조
    • 선형(linear) 자료구조
      • 배열, 연결 리스트, 스택, 큐
    • 비선형(non-linear) 자료구조
      • 트리, 그래프
  • 선형 자료구조
    
    • 배열
      
      • 논리적인 순서와 물리적인 순서가 같음
      • 각각의 원소에 접근하기위해서 인덱스를 사용(임의적인 접근)
      • 삽입/삭제가 발생하면 자료의 이동이 발생하며 자료가 많을 경우 부담이 될 수 있음
        • 삽입/삭제가 빈번히 발생하는 경우 적절하지 않을 수 있음
    • 연결 리스트
      • 논리적인 순서와 물리적인 순서가 같지 않음
      • 인덱스로 접근하지 않기 때문에 데이터가 많은경우 데이터를 찾기가 어려움
      • 링크필드를 조작하여 삽입/삭제
        • 배열에 비해 삽입과 삭제가 용이함
    • 스택
      • 후입선출(Last In First Out)
      • push, pop
    • 큐
      • 선입선출(First In First Out)
      • front, rear
  • 비선형 자료구조
    • 트리
      • 하나이상의 노드로 구성된 유한집합
      • 조건1: T의 원소 가운데 단 하나의 루트노드가 존재함
      • 조건2: 루트 노드를 제외한 나머지 노드는 n개의 서로다른 부분집합 T1, T2, ... , Tn으로 나누어지며 각 Ti(서브트리)는 트리가 됨
      • 주요용어
        • 차수(degree): 노드의 차수, 트리의 차수
        • 리프 노드(leaf)/단말 노드(terminal): 마지막에 있는 노드
        • 비단말 노드
        • 부모노드(parent), 자식노드(child), 형제 노드(sibling)
        • 조상(ancester): 선조, 후손(descendant): 자손
        • 레벨(level): 루트노드로부터의 거리
        • 높이(height)/깊이(depth): 트리의 깊이
        • 숲(forest)
    • 이진 트리
      • 각 노드의 차수가 2이하인 순서트리
      • 레벨 i에서 최대 노드의 개수 -> 2^i
      • 높이 h인 이진 트리의 최대 노드의 개수-> 2^h - 1
      • n0 = n2 + 1(n0: 단말 노드의 수, n2: 차수가 2인 노드의 수)
      • 포화(perfect)이진트리
      • 완전(complete)이진트리
        • 맨마지막 레벨전까지는 포화이진트리이며 맨 마지막레벨에서는 빈자리
      • 전(full)이진트리
        • 각 노드의 차수가 0 또는 2인 경우
      • 균형(balanced) 이진트리
        • 왼쪽 서브트리와 오른쪽 서브트리의 높이가 1이내인 것
      •   경사(skewed) 이진트리
        • 각 노드의 가지가 하나밖에 없는 것
    • 그래프
      • V: 정점의 집합, E: 간선의 집합
      • 무방향 그래프, 방향 그래프
      • 그래프의 구현
        • 인접행렬, 인접 리스트
• 정리
  • 기본자료구조
    • 배열, 연결리스트
      • 정의, 논리적 개념 및 구조, 연산(삽입, 삭제, 접근)
    • 스택, 큐
      • 정의, 특징(LIFO, FIFO), 동작
    • 트리, 그래프
      • 정의, 용어, 이진트리(정의, 특성, 종류), 구현