컴퓨터알고리즘#5

LeeMir, 17 March 2021

기본 추상자료형

추상자료형
  • 추상자료형(Abstract Data Type, ADT) : 데이터구조의 추상형
  • ADT는 다음을 명세함
    • 저장된 데이터
    • 데이터에 대한 작업들
    • 작업 중 발생 가능한 에러 상황들
리스트 ADT
  • 연속적인 임의 개체들을 모델링
  • 원소들의 순서(ordered) 집단을 저장하기 위한 기초적이고, 일반적 목적의 데이터 구조
  • 원소(Element)에 대한 접근 도구
    • 순위(rank)
  • 응용
    • 스택, 큐, 집합 등의 더 복잡한 데이터구조를 구축하기 위한 재료로 사용
    • 소규모 데이터베이스(ex : 주소록)
  • 일반 메쏘드
    • integer size()
    • boolean isEmpty()
    • iterator elements()
  • 접근 메쏘드
    • element get(r)
  • 갱신 메쏘드
    • element set(r, e)
    • add(r, e), addFirst(e), addLast(e)
    • element remove(r), element removeFirst(), element removeLast()
  • 예외
    • invalidRankException()
    • fullListException()
    • emptyListException()
  • 배열을 이용한 구현
    • 삽입 / 삭제할 때마다 shift 연산을 해야해 자유롭지 않음 => O(n)
      • 첫번째 인덱스에 삽입/삭제 : O(n)
      • 마지막 인덱스에 삽입/삭제 : O(1)
    • 탐색은 빠른 편 => O(1)
  • 단일 연결 리스트를 이용한 구현
    • Head Pointer와 NodeList 구조체를 만들어 구현
집합 ADT
  • 유일한 개체들을 담는 용기를 모델링
    • 중복이 없으며, 순서가 존재하지 않음
  • 집합 ADT 관련 작업들의 효율적인 구현을 위해, 집합을 집합 원소들의 정렬된 리스트로 표현
  • 주요 메쏘드
    • set union(B) : 집합 B와의 합집합 반환
    • set intersect(B) : 교집합 반환
    • set subtract(B) : 차집합 반환
  • 응용
    • 키워드 검색엔진
    • 집합론에 관련된 다양한 계산
    • 알고리즘을 위한 보조 데이터구조
    • 다른 데이터구조를 구성하는 요소
스택 ADT
  • 임의의 개체를 저장
  • 삽입과 삭제는 후입선출(Last-In First-Out, LIFO) 순서를 따름
  • 삽입과 삭제는 스택의 top이라 불리는 위치에서 수행
  • 가장 최근에 했던 작업의 취소(Ctrl+Z)에 쓰임
  • 주요 메쏘드
    • push(e) : 원소를 삽입
    • element pop() : 가장 최근에 삽입된 원소를 삭제 및 반환
  • 응용
    • 웹브라우저에서 방문한 웹페이지들의 기록
    • 문서편집기에서 되돌리기 기록
    • 윈도 운영체제에서 겹쳐진 윈도우들
    • C++ 실행환경 또는 자바가상기계에서 메쏘드의 연쇄적인 호출
    • 재귀의 구현
    • 알고리즘 수행을 위한 보조 데이터구조
    • 다른 데이터구조를 구성하는 요소
큐 ADT
  • 임의의 개체를 저장
  • 삽입과 삭제는 선입선출(First-In First-Out, FIFO) 순서를 따름
  • 삽입은 큐의 뒤(rear), 삭제는 큐의 앞(front)이라 불리는 위치에서 수행
  • 주요 메쏘드
    • enqueue(e) : 큐의 뒤에 원소를 삽입
    • element dequeue() : 큐의 앞에서 원소를 삭제하고 반환
  • 응용
    • 대기열
    • 공유자원에 대한 접근(프린터)
    • 멀티프로그래밍
    • 알고리즘 수행을 위한 보조 데이터구조
    • 다른 데이터구조를 구성하는 요소
  • 배열로 구현할 경우, 선형으로 사용하면 비효율적이므로 원형으로 사용해야함
    • 빈 큐를 만원 큐와 구분하기 위해
      • 한 개의 빈 방을 예비로 둠
      • 대안 : 원소 개수를 유지
트리 ADT
  • 계층적으로 저장된 데이터원소들을 모델링
  • 맨위의 원소를 제외하고, 각 트리 원소는 부모 원소와 0개 이상의 자식 원소들을 가짐
  • 전제 : 트리는 비어 있지 않음(알고리즘 단순화)
  • 용어
    • 루트 : 부모가 없는 노드
    • 내부노드 : 적어도 한 개의 자식을 가진 노드
    • 외부노드(또는 리프) : 자식이 없는 노드
    • 형제 : 같은 부모를 가진 노드들
    • 노드의 조상 : 부모, 증부모, 증조부모 등
    • 노드의 자손 : 자식, 손주, 증손주 등
    • 부트리(서브 트리) : 노드와 노드의 자손들로 구성된 트리
    • 경로 : 조상 또는 자손을 따라 이어진 노드 시퀀스
    • 경로길이 : 경로 내 간선(Edge)의 수
    • 노드의 깊이 : 루트로부터 노드에 이르는 유일한 경로의 길이
    • 노드의 높이 : 노드로부터 외부노드에 이르는 가장 긴 경로의 길이
    • 트리의 높이 : 루트의 높이
  • 순서트리
    • 각 노드의 자식들에 대해 선형 순서가 정의되어 있는 트리
  • 이진트리
    • 순서트리를 모델링
    • 전제 : 적정이진트리로 구현, 이진트리는 비어있지 않음
      • 트리의 각 내부노드가 두 개의 자식을 가짐
    • (재귀적 정의) 루트가 자식의 순서쌍을 가지며, 내부노드인 자식은 이진트리
  • 응용
    • 조직구성도
    • 파일시스템
    • 프로그래밍 환경
    • 알고리즘을 위한 보조 데이터구조
    • 다른 데이터구조를 구성하는 요소
  • 순회
    • 선위(전위)순회, preorder
      • VLR
    • 중위순회, inorder
      • LVR
    • 후위순회, postorder
      • LRV