Developer Ahn

- selection sort

- 오른쪽 리스트(정렬 안 된)에서 가장 작은 숫자를 선택하여 왼쪽 리스트(정렬 된)로 이동하는 작업을 반복

- 시간 복잡도 : 



- 코드

void selectionSort(int* list, size) {
    int indexMin, temp;

    for (int i = 0; i < size; i++) {
        indexMin = i;
        for (int j = i + 1; j < list.length; j++) {
            if (list[j] < list[indexMin]) {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

- 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) 가능
   : 동적메모리 할당, 필요한 만큼 할당
    

• 재귀 함수 구현
  1. 기저 파악 (재귀를 멈추는 부분, 끝 조건)
  2. 조건문 파악 (재귀 호출 조건)
  3. 구현
  
  - 거듭제곱 값, 피보나치 수열, 하노이탑
  
  - 반복 vs 재귀
   : 상황에 따라 속도가 더 빠른 것을 선택
   : 재귀는 스택오버플로우가 일어날 수 있다.

• 빅오 표기법
  
  
  
  

  
  

  O(1)	상수	항상 일정한 속도를 가진다.
  O(Log(N))	로그	N이 증가함에 따라 조금식 시간이 늘어난다.
  O(N)	선형	N이 증가하면 시간도 일정하게 증가한다.
  O(NLog(N))	선형로그	N이 2배로 증가하면 실행 시간은 두배 보다 약간 더 많이 늘어 난다.
  O(N^2)	평방형	N이 증가시 2 제곱만큼 실행 시간이 늘어 난다.(이중 루프 처리시)
  O(2^N)	지수형	N이 증가할수록 실행 시간은 급격히 늘어 난다.
  O(N!)	계승형	N이 증가할수록 실행 시간은 졸라 급격히 늘어 난다.(팩토리얼)

  
  

• 표기법
  

  - O(Big-O)
  

   : 상한, 최악의 경우(Worst Case)를 나타내는 표기법으로 알고리즘 분석에서 가장많이 사용하는 표기법이다.
  
  

  - Ω(Omega)
   : 하한, 최상의 경우(Best Case)를 나타내는 표기법이다.
  
  - θ(Theta)
   : 평균의 경우(Average Case)를 나타내는 표기법이다.