Developer Ahn

- spanning tree

- 그래프 내의 모든 정점을 포함하는 트리

- 트리의 특수한 형태로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다, n개의 정점을 정확히 (n-1)개의 간선으로 연결

- 깊이 우선 탐색이나 너비 우선 탐색 도중에 사용된 간선만 모으면 만들 수 있다.

- 최소 신장 트리 (MST, Minimum spanning tree)
   : 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 트리
   : 도리 건설, 전기 회로, 통신, 배관 등에 이용

- 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조

- 오일러에 의해 착안

- 정점(vertex)과 정점간의 관계 간선(edge)로 표현 

- 방향 그래프 vs 무방향 그래프
   : 표현 (0, 1) vs <0,1>
   : 무뱡향 그래프에서 차수(degree)는 하나의 정점에 인접한 정점의 수
   : 방향 그래프에서 외부에서 오는 간선의 수를 진입 차수(in-degree), 외부로 향하는 간선의 수를 진출 차수(out-degree)

- 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프 또는 네트워크

- 경로 중에서 반복되는 간선이 없을 경우에 이러한 경로를 단순 경로, 단순경로의 시작 정점과 종료 정점이 동일하다면 이러한 경로를 사이클(cylcle)

- 모든 정점쌍에 대하여 하상 경로가 존재하면 연결 그래프, 모든 정점이 서로 연결되어 있는 그래프는 완전 그래프

- priority queue

- 배열, 리스트 사용하여 구현시 최악의경우로 삽입, 삭제에 O(n)

- 힙 (heap)
 : 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료 구조, 더미
 : 일종의 반정렬 상태를 유지
 : 삽입과 삭제에 
 : 최대 힙: 부모 노드 >= 자식 노드, 최소 힙: 부모 노드 <= 자식노드
 : 삽입
  ① 힙의 끝에 새로운 노드 삽입
  ② 삽입된 노드와 그 부모 노드의 키 값을 비교하여 삽입된 노드의 키 값이 부모 노드의 키 값보다 크면 두 노드의 위치를 바꾼다.
  ③ 삽입된 노드의 키 값이 자신의 부모 노드 키 값보다 작아질 때까지 단계 ② 반복
 : 삭제
  ① 루트 노드 삭제하고, 마지막 노드를 루트에 삽입
  ② 자식 노드랑 스왑해나가는데, 이때 왼쪽, 오른쪽 자식노드 중 더 큰 쪽이랑 교환
  ③ 자식 노드들이 작을때까지 ② 반복

 : 허프만 코드에 이용 가능 (최소힙 사용)
   알파뱃의 빈도수를 이용하여 저장하고, 디코딩은 코드 테이블을 이용하여 수행할 수 있다.

- 완전(complete)라는 의미?
  : 노드들이 힙 조건을 만족한다. O
  : 마지막 행만 제외하고 모든 행이 노드로 채워져 있다. X

- 모든 노드가 2개의 서브 트리를 가지고 있는 트리

- n개의 노드를 가진 이진 트리는 정확하게 n-1개의 간선을 가짐

- 포화 이진 트리(full binary tree)
   : 각 레벨에 노드가 꽉 차 있는 이진트리
  완전 이진 트리(complete binary tree)
   : 높이가 k일 때 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만 중간에 빈 곳이 있으면 안 된다. 
  기타 이진 트리

- 배열 사용 시 1부터 사용, 포인터 사용 시 왼쪽, 오른쪽 자식 노드를 가리키는 포인터 필요

- 이진트리 순회
 V: 부모, L: 왼쪽 자식 노드, R: 오른쪽 자식노드
  ■ 전위 순회 : VLR
  ■ 중위 순회 : LVR
  ■ 후위 순회 : LRV
  => 큐, 재귀를 이용하여 구현 가능
 : 수신 트리를 처리하는 데 사용

- 스레드 이진트리 : 중위 후속자를 저장시켜 놓은 트리

- 이진 탐색 트리(binary search tree)
 : 모든 노드의 키는 유일하다.
 : 왼쪽 서브 트리의 키들은 루트의 키보다 작다.
 : 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
 : 왼쪽과 오른쪽 서브 트리로 이진 탐색 트리이다.
 : 삽입, 삭제 시 노드를 재정렬한다.


 : 높이가 4이면,    
 : 평균 

 : 한 노드만 계속 하위 레벨로 붙어나가는 최악의 경우 O(n)이 발생
  => AVL 트리 등 사용
 : strcmp를 기준으로 사전식 정렬 가능

- tree : 계층적인 구조

- 트리의 구성요소 : 노드(node)

- root, subtree

- 정점(vertex), 간선(edge)

- 부모노드, 자식노드, 형제 노드 (트리 레벨에 따라)

- 비단말 노드, 단말 노드 (=leaf node): 자식의 유무

- double-ended queue = deque, 선형 자료 구조

- front와 rear 모두 삽입 삭제가 가능

- isEmpty(), isFull(), addFront(), deleteFront(), getFront(), addRear(), deleteRear(), getRear() , peek(), front, rear

- queue : 후입선출(LIFO), 선형 자료 구조

- 선형 큐, 원형 큐

- 버퍼로 사용, 생산자, 소비자 패턴에 이용

- isEmpty(), isFull(), enqueue(), dequeue(), peek(), front, rear

- stack : 후입선출(LIFO), 선형 자료 구조

- isEmpty(), isFull(), push(), pop(), peek(), top

- 괄호 검사, 수식의 계산(후위 표기식), 미로 탐색 문제(BFS)

• 배열 vs 리스트
  
  - 배열 (array)
   : 연속된 주소공간, 선형 자료 구조
   : 직접 접근 O(1), 순차 접근 O(n) 가능
   : 정적메모리 할당, 지역변수로는 메모리 제한, 메모리 낭비
  
  - 리스트 (list)
   : 연속된 공간이 아니며, 이전 노드나 다음 노드를 가르키는 주소값 필요, 선형 자료 구조
   : 헤드포인터 필요
   : 순차 접근 O(n) 가능
   : 동적메모리 할당, 필요한 만큼 할당
    

• 가상기억장치
   : 프로그램을 실행하는 동안 종종 프로그램 전체를 모두 사용하지 않는다.
   : 프로그램을 실행할 때 한 순간에 프로그램 전체를 필요로 하지 않는다.
   : overhead의 단점 때문에, VM은 Real-time(embedded) system에 부적합
  
  - 프로그램의 일부만 주기억장치에 있어도 실행이 가능하도록 하면 얻을 수 있는 장점
   : 프로그램은 더 이상 물리적 주기억장치 크기에 제한을 받지 않는다.
   : 각 프로그램이 적은 공간을 차지하므로 동시에 여러 프로그램을 주기억장치에 적재(multiprogramming degree 향상)
   : 프로그램을 적재하는데 걸리는 입출력 비용을 줄일 수 있다.
   : 가상기억장치는 요구 페이징(demand paging)기법을 이용하여 구현한다. 세그먼테이션과 결합하여 사용
  
  
• 요구 페이징
   : 스왑핑 + 페이징을 결합하여 사용
   : 프로세스 전체를 스왑하지 않고, 지연 스왑퍼(lazy swapper = pager)를 사용한다. 이 스왑퍼는 페이지가 필요할 경우에만 적재한다.
   : 주기억장치에 있는 페이지와 디스크에 있는 페이지를 구분하기 위해 유효비트 사용 (1 이면 주기억장치, 0 이면 디스크), TLB, 보호비트, 디스크의 일부분을 스왑 공간으로 사용
  
   
  
   ① 접근하는 페이지에 대해 페이지 테이블을 참조하면 유효비트가 현재 0이므로 페이지 결함 트랩(page fault trap) 발생
   ② 트랩이 발생하면 프로세스의 PCB를 검사하여 참조의 유효성을 검사. 즉, 디스크에 있는 페이지에 대한 참조인지 프로세스의 가상 주소 공간을 벗어난 참조인지를 검사한다. 후자이면 프로세스 종료.
   ③ 빈 프레임을 찾는다.
   ④ 디스크 입출력을 이용하여 페이지를 프레임에 적재한다.
   ⑤ 디스크 입출력이 종료되면 프로세스의 내부 테이블과 페이지 테이블을 수정한다.
   ⑥ 페이지 결합 트랩을 발생시킨 명령어를 다시 수행한다.
  
    ■ Effective Access Time (EAT)
     : (1-p) * Memory Access Time + p * Page Fault Time (p, Page fault rate 0 <= p <= 1)
     : Page Fault Time = page fault overhead + swap page out + swap page in + restart overhead
  
    ■ Copy-on-Write
     : 부모 프로세스가 자식 프로세스를 생성할때 부모 프로세스의 주소 공간을 복사하는 것은 낭비, 변경된 페이지 내용만 복사하고 나머지는 모두 공유
  
   
  
  
• 페이지 교체
   : 10 페이지 크기의 프로세스가 실제 5 페이지만 사용하면 요구 페이징 기법은 디스크 입출력을 줄일 수 있고, 다중 프로그래밍의 정도를 높일 수 있다.
   : but, 다중 프로그래밍의 정도를 높이면 프레임 공간이 부족할 수 있다. 또한 주기억장치의 모든 프레임을 사용자 프로세스에게 할당해줄 수 없다.
   : 프로세스 종료, 프로세스 스왑 아웃, 페이지 교체 등으로 해결
   - 페이지 교체(page replacement)
     : 적재되어 있는 기존 페이지를 새 페이지로 교체한다.
     : 페이지 결함이 발생할 때 페이지 교체 절차
    
  
     ① 디스크에서 페이지의 위치를 찾는다.
     ② 빈프레임을 찾는다.
       : 있으면, 거기에 페이지를 적재
       : 없으면, 페이지 교체 알고리즘을 이용하여 희생 프레임을 선택한 다음 희생 프레임에 있는 페이지를 디스크에 쓰고, 프레임에 새 페이지를 적재한다. 
     ③ 페이지 테이블과 프레임 테이블을 변경한다.
     ④ 프로세스를 재개한다.
      : 빈 프레임이 없으면 항상 두 번의 디스크 입출력이 필요하다. 디스크 입출력은 변경 비트를 이용하여 줄 일 수 있다.(하드웨어적으로 구현)
      : 제공되어야 하는 두 가지 알고리즘
      - 프레임 할당 알고리즘
        : 한 프로세스에게 할당할 프레임의 수를 결정하는 알고리즘
        : Fixed allocation vs Priority allocation
        : Global allocation vs Local allocation (다른 프로세스의 페이지 vs 자신의 페이지)
    - 페이지 교체 알고리즘
     : 빈 프레임이 없을 때 희생자를 선택하는 알고리즘
    
   ■ FIFO (First-In-First-Out)
    : 가장 오래전에 들어온 페이지가 선택
    : Belady의 모순: 프레임 수가 증가하면 페이지 결함 발생 수는 감소해야 정상인데 증가하는 경우가 있음
   ■ Optimal
    : 가장 오래 동안 사용되지 않을 페이지가 희생자로 선택
    : 미래를 예측하기 힘들다
   ■ LRU (Least-Recently Used)
    : 가장 오래전에 참조한 페이지가 희생자로 선택
    : 가장 널리 사용 됨 
   ■ LRU-Approximation
    : 충분한 하드웨어 지원이 없을 경우
    : Additional-Reference-Bits, Second-Chance, Enhanced Second-Chance
   ■ Counting-Based
    : LFU, MFU


• 스레싱
   : 계속하여 페이지 결함이 발생하는 현상을 스레싱이라 한다. 실행하는 시간보다 페이지 결함을 처리하는 시간이 더 많아지면 이 현상이 발생하였다고 한다.
   : 프로세스에 할당된 프레임 수가 필요한 최소의 프레임 수 이하로 내려가면 스레싱 발생
   : 다중 프로그래밍 정도 <-> CPU 사용 효율, 반비례 관계
   : 지역성 모델(locality model): 이 모델에 의하면 프로세스는 실행되는 동안 한 지역에서 다른 지역으로 이동한다. 여기서 지역이란 현재 활동적으로 사용하고 있는 페이지들의 집합을 말한다. 현재 프로세스의 지역을 수용할 수 있는 만큼의 프레임을 할당해주면 스레싱은 발생하지 않는다.
   ■ 작업 집합 모델 
    : 지역성 가정에 기반한 모델