youngmin.log

• [ 목차 ]

• 힙이란 무엇인가 ?
• 힙을 이용한 우선순위 큐 구현
• 힙 구현과 성능
• 힙 정렬
• 제자리 힙 정렬
• 상향식 힙 생성

• 힙이란 무엇인가 ?

• 힙(Heap) : 내부노드에 키를 저장하며 다음 두 가지 속성을 만족하는 이진트리
  
  
  1. 힙 순서(Heap-order) : 루트를 제외한 모든 내부노드 v에 대해
     Key(v) >= Key(parent(v)) => (최소힙 기준)
     Key(v) <= Key(parent(v)) => (최대힙 기준)
  2. 완전이진트리(Complete binary tree) : 힙의 높이가 h라고 하면
     => i = 0, ... , h - 1에 대해 깊이 i인 노드가 2^i개 존재
     => 깊이 h - 1에서, 내부노드들은 외부노드들의 왼쪽에 존재
  3. 힙의 마지막(Last Node) : 깊이 h - 1의 가장 오른쪽 내부노드

• 힙의 높이

• 정리 : n개의 키를 저장한 힙의 높이는 O(log n)이다.
• 증명 : ( 완전이진트리의 성질을 이용 )
  
  
  • n개의 키를 저장한 힙의 높이를 h라 하자.
  • 깊이 i = 0, ... , h - 2 에 2^i개의 키, 그리고 깊이 h - 1에 적어도 한 개의 키가 존재하므로, n >= 1 + 2 + 4 + ... + 2^(h-2) + 1
  • 따라서, n >= 2^(h-1) (등비수열의 합) ,즉 h <= log(n) + 1

• 힙과 우선순위 큐

• 힙을 사용하여 우선순위 큐(Priority queue) 구현 가능
• 전제 : 적정이진트리로 구현
• 마지막 노드의 위치를 관리

• 힙에 삽입

• 우선순위 큐 ADT의 메쏘드 InsertItem 은 힙에 키 k를 삽입하는 것에 해당
• 삽입 알고리즘의 세 단계
  1. 삽입 노드 z, 즉 새로운 마지막 노드를 찾는다.
  2. k를 z에 저장한 후, expandExternal(w) 작업을 사용하여 z을 내부노드로 확장
  3. 힙 순서 속성을 복구

• Upheap ( Continue. 힙 삽입 )

• 새로운 키 k가 삽입된 후, 힙 순서 속성이 위배될 수 있다.
• upheap은 삽입노드로부터 상향경로를 따라가며 키 k를 교환함으로써 힙 순서 속성을 복구
• upheap은 키 k가 루트에 또는 부모의 키가 k보다 작거나 같은 노드에 도달하면 정지 ( 최소힙 기준 ! , 최대힙은 반대 )
• 힙의 높이는 O(log(n))이므로 upheap은 O(log(n))시간에 수행
  (앞서 배운, 선택정렬, 삽입정렬로 우선순위 큐와 비교했을 때 상당히 빠름)

• 힙 삽입 알고리즘 ( PseudoCode )

[ PseudoCode ]
-----------------------------
 
Alg InsertItem(k)
	input Key k, node last
  	output none
    
advanceLast( )	// 마지막 노드위치를 찾음
z <- last		// 마지막 노드를 생성하고
Set node z to k	// 그 노드의 Key k를 대입
expandExternal(z) // z를 내부노드와 시킨다.
upHeap(z)	// 이 노드의 힙 속성에 맞게 재위치
return 
 
------------------------------
 
Alg upHeap(v)		// 최소 힙 기준
	input node v
    output none
 
if(isRoot(v))
	return
if(Key(v) >= Key(parent(v))
	return
swapElements(v,parent(v))
upHeap(parent(v))
 
-------------------------------

• InsertItem 과 upHeap의 작업 대상 힙은 일반(generic)힙 이다.
  일반 힙이 무엇인지 모르겠다면, "우선순위 큐"

• 힙 삽입 알고리즘 ( Continue. 힙 삽입 )

[ PseudoCode ]
--------------------------------------------
 
Alg expandExternal(z) { 연결리스트 경우만 ! }
	input external node z
    output none
    
l <- getnode()
r <- getnode()
l.right <- NULL
l.left <- NULL
l.parent <- z
r.right <- NULL
r.left <- NULL
r.parent <- z
z.left <- l
z.right <- r
return 
 
--------------------------------------------

: 내부노드화 시킨다는 소리

• 힙 삭제

• 우선순위 큐 ADT의 메쏘드 removeMin은 힙으로부터 루트 키를 삭제하는 것에 해당 ( 최소 힙 기준 ! )
• 삭제 알고리즘의 세 단계
  1. 루트 키를 마지막 노드 w의 키로 대체
  2. reduceExternal(z) 작업을 사용하여 w와 그의 자식들을 외부노드로 축서
  3. 힙 순서 속성을 복구

• DownHeap

• 루트 키를 마지막 노드의 키로 대체한 후, 힙 순서 속성이 위배될 수 있다.
• downheap은 루트로부터 하향 경로를 따라가며 키 k를 교환함으로써 힙 순서 속성을 복구
• downheap은 키 k가 리프노드, 또는 자식의 키가 k보다 크거나 같은 노드에 도달하면 정지 ( 최소 힙 기준 !, 최대 힙은 반대 )
• 힙의 높이는 O(log(n)) 이므로 downheap은 O(log(n)) 시간에 수행

• 힙 삭제 알고리즘 ( 최소 힙 기준 )

[ PseudoCode ]     { 연결리스트 기준 }
----------------------------------------------------------
Alg removeMin()     { 최소 힙 기준 }
	input node last
    output key
    
k <- key(root())
w <- last
Set root to key(w)
retreatLast()
z <- rightChild(w)
reduceExternal(z)
downHeap(root())
return k
 
-----------------------------------------------------------
 
Alg downHeap(v)
	input node v whose left and right substrees are heaps
    out a heap with root v
    
if((isExternal(leftChild(v)) & isExternal(rightChild(v))
	return
smaller <- leftChild(v)
if(isInternal(rightChild(v))
	if(key(rightChild(v) < key(smaller))
    	smaller <- rightChild(v)
if(key(v) <= key(smaller))
	return
swqpElements(v,smaller)
downHeap(smaller)
 
-----------------------------------------------------------

• ( Continue. 삭제 )

[ PseudoCode ] { 연결리스트 }
--------------------------------------------------------------------
 
Alg reduceExternal(z)	// 맨 마지막노드를 해제하고, 마지막노드 위치변경과정
	input external node z
    output the node replacing the parent node of the removed node z
    
w <- z.parent
zs <- sibling(z)
if(isRoot(w))
	root <- zs
    zs.parent <- NULL
else
	g <- w.parent
    zs.parent <- g
    if(w = g.left)
    	g.left <- zs
    else  // w = g.right
    	g.right <- zs
putnode(z)		// 해제 z
putnode(w)		// 해제 w
return zs
 
-----------------------------------------------------------------------

• 마지막 노드 갱신

• O(log(n))개의 노드를 순회함으로써 삽입 노드를 찾을 수 있다. (advanceLast)
  • 현재 노드가 오른쪽 자식인 동안, 부모 노드로 이동
  • 현재 노드가 왼쪽 자식이면, 형제 노드로 이동
  • 현재 노드가 내부노드인 동안, 왼쪽 자식으로 이동
• 삭제 후 마지막 노드를 갱신하는 작업은 위한 반대 방향으로수행 (retreatLast)

• 배열에 기초한 힙 구현

• n개의 키를 가진 힙을 크기 n의 배열을 사용하여 표현 가능
• 첨자 i에 존재하는 노드에 대해
  • 왼쪽 자식은 첨자 2*i 에 존재
  • 오른쪽 자식은 첨자 2*i+1 에 존재
  • 부모는 첨자 i/2에 존재
• 노드 사이의 링크는 명시적으로 저장할 필요가 없다.
  ( 다만, 머리 속으로 링크가 있는 것처럼 상상하자.)
• 외부노드들은 표현할 필요가 없다.
• 첨자 0 셀은 사용하지 않는다. ( 빈 노드 )
• 마지막 노드의 첨자 : 항상 n
  • InsertItem : 작업은 첨자 n + 1위치에 삽입하는 것에 해당
  • removeMin : 작업은 첨자 n 위치에서 삭제하는 것에 해당

• 성능 요약

• 힙 정렬 ( Heap Sort ) ( 최소힙 기준 )

• 힙을 사용하여 구현된 n-항목 우선순위 큐를 고려하면,
  • 공간 사용량은 O(n)
  • InsertItem 메쏘드와 removeMin 메쏘드는 O(log(n))시간에 수행
  • size, isEmpty,minKey,minElement 메쏘드는 O(1)시간에 수행
    ( 힙의 루트노드정보만 조회하면 되니깐 )
• 힙에 기초한 우선순위 큐를 사용함으로써, n개의 원소로 이루어진 리스트를 O(log(n))시간에 정렬할 수 있다.
  • 선택정렬이나 삽입정렬과 같은 2차 정렬 알고리즘보다 훨씬 빠르다.
• 이 알고리즘을 힙 정렬(Heap Sort) 라고 한다.

[ PseudoCode ]
---------------------------------
 
Alg heapSort(L)
	input list L
    output sorted list L
    
H <- empty heap
while(!L.isEmpty())  { 1 단계 }
	k <- L.removeFirst()
    H.insertItem(k)
while(!H.isEmpty())  { 2 단계 }
	k <= H.removeMin()
    L.addLast(k)
return
 
---------------------------------

• 힙 정렬 개선

• Heap Sort 의 성능 향상을 위한 두 가지 개선점
  • 제자리 힙 정렬은 heap sort 의 공간 사용을 줄인다.
  • 상향식 힙 생성은 heap sort의 속도를 높힌다.

• 제자리 힙 정렬

• 이 방식은 정렬되어야 할 리스트가 "배열" 로 주어진 경우에만 적용
• 힙을 저장하는데 리스트 L의 일부를 사용함으로써 외부 힙 사용을 피한다.
• 지금까지 사용했던 최소힙(min-heap) 대신, 최대 원소가 맨위에 오게 되는 최대힙(max-heap)을 사용

[ PseudoCode ]
---------------------------------------------------------------
 
Alg InPlaceHeapSort(A)
	input array A of n Keys
    output sorted array A
    
buildHeap(A)	// { 1 단계 }
for i <- n downto 2	 // { 2 단계 }
	A[1] <-> A[i]
    downHeap(1, i-1)
return
 
----------------------------------------------------------------
 
Alg buildHeap(A)
	input array A of n Keys
    output heap A of size n
 
for i <- 1 to n
	insertItem(A[i])
return
 
----------------------------------------------------------------
 
Alg downHeap(i, last)
	input index i of array A representing a maxheap of size last
    output none
    
left <- 2i
right <- 2i + 1
if(left > last)
	return
greater <- left
if(right <= last)
	if(key(A[right] >= key(A[greater]))
    	greater <- right
if(key(A[i] >= key(A[greater]))
	return
A[i] <-> A[greater]
downHeap(greater,last)
 
---------------------------------------------------------------

• 제자리 힙 정렬 ( Continue. )

• 알고리즘 수행의 어떤 시점에서든
  • L의 첨자 1부터 i까지의 왼쪽 부분을 힙의 원소들을 저장하는데 사용
  • 그리고 첨자 i+1부터 n까지의 오른쪽 부분을 리스트의 원소들을 저장하는데 사용
• 그러므로, L의 (첨자 1, ... , i에 있는) 첫 i개의 원소들은 힙의 배열 표현
  => 즉, 첨자 k의 원소는 첨자 2k 및 2k+1의 자식들보다 크거나 같다.

• 제자리 힙 정렬 ( Continue. )

• 1기
  • 비어 있는 힙으로부터 출발하여 힙과 리스트의 경계를 왼쪽에서 오른쪽으로 한 번에 한칸씩 이동
  • 단계 i(i =1, ... , n)에서, 첨자 i에 있는 원소를 힙에 추가함으로써 힙을 확장
• 2기
  • 비어 있는 리스트로부터 출발하여 힙과 리스트의 경계를 오른쪽에서 왼쪽으로 한 번에 한 칸씩 이동
  • 단계 i(i = n, ... , 2)에서, 힙의 최대 원소를 삭제하여 리스트의 첨자 i에 저장함으로써 리스트를 확장

• 제자리 힙 정렬 예

• 1기의 2기의 각 단계에서, 배열 가운데 힙에 쓰인 부분을 파란색 원소로 표시
• 아래 점선 내에 보인 이진트리 관점의 힙은 가상적일 뿐, 제자리 알고리즘에 의해 실제 생성되지는 않음에 유의 ( 배열로 구현했으니 )
• 1기 작업 시작

• 1기 작업 완료
• 리스트가 최대 힙으로 변환됨

• 2기 작업 시작

 

• 상향식 힙 생성

• heap-sort의 1기에서, n회의 연속적인 InsertItem 작업을 사용하여 O(nlog(n)) 시간에 힙을 생성했다.
• 대안으로, 만약 힙에 저장되어야 할 모든 키들이 미리 주어진다면, O(n)시간에 수행하는 상향식 힙 생성 방식있다. ( 뒤에 기술함. )

[ PseudoCode ]
----------------------------------------------------------------------------------
 
Alg buildHeap(L)		// ( 재귀적, 배열인경우 )
	input list L storing n Keys
    output heap T storing the Keys in L
 
if(L.isEmpty())
	return empty heap
Remove the first key km from L
Split L into two sublists, L1, and L2, each of size (n-2)/2 approximately
 
T1 <- buildHeap(L1)
T2 <- buildHeap(L2)
 
Create a binary tree T with root r storing k, left subtree T1, and right subtree T2
 
downHeap(r)
return T
 
------------------------------------------------------------------------------------

• log n 단계만을 사용하여 주어진 n개의 키를 저장하는 힙 생성 가능
• 단계 i에서, 각각 2^i - 1 개의 키를 가진 두 개의 힙을 2^(i+1) -1개의 키를 가진 힙으로 합병

• 두 개의 힙을 합병

• 두 개의 힙과 키 k가 주어졌을 때
• k를 저장한 노드를 루트로, 두 개의 힙을 부트리로 하는 새 힙을 생성
• 힙 순서 속성을 복구하기 위해 downheap을 수행

• "상향식" 이라 불리는 이유

• 상향식 힙 생성버전은 각 재귀호출이 힙인 부트를 반환하는 방식이기 때문에 "상향식" 이라 불린다.
• 다시 말해, T 의 힙합(heapification)는 외부노드에서 시작하여, 각 재귀호출이 반환함에 따라 트리 위쪽으로 진행
• 이 때문에 종종 힙화한다(heapify)고 말하기도 한다.

• 비 재귀적 상향식 힙 생성

• 상향식 힙생성의 비재귀 버전
• 정렬되어야 할 리스트가 "배열"로 주어진 경우에만 적용
• 비 재귀적 힙 생성 절차가 "내부노드를 왼쪽 자식으로 가지는, 가장 깊은 내부노드 가운데 가장 오른쪽 노드"에서 시작하여 루트로 향하는 후진 방향으로 반복수행
  ( = 리프노드가 아닌, 바로 전 높이에서 가장 오른쪽 노드를 의미함.
  왜냐면, 리프노드는 downheap 할 것이 없으니깐 )
• 시작 노드 : 첨자 [n/2] 인 노드

[ PseudoCode ]
-----------------------------
 
Alg buildHeap(A)		// 비재귀적 힙생성, 배열인 경우
	input array A of n Keys
    output heap A of size n
    
for i <- [n/2] downto 1
	downHeap(i,n)
 
return
 
------------------------------

• 실질적 구현단계 ( 삽입식 힙 생성. C ver. )

• 알고리즘 구현 전에 설계 팁

[ PseudoCode ]
----------------------------------------------
 
Alg InsertItem(key)		// 힙 삽입
	input integer key array H 	// key: 삽입 키
    output array H		// H: 전역배열, heap
    
n <- n + 1		// n 갱신
H[n] <- key		// 힙에 초기 삽입 위치는 n
upHeap(n)		// 힙 조정
return
 
-----------------------------------------------
 
Alg removeMax()			// 힙 삭제 ( 최대 힙 기준 )
	input array H	
    output array H		// H: 전역배열, heap
    
key <- H[1]		// 루트키 보관
H[1] = H[n]		// 힙의 마지막 키를 루트로 이동
n <- n + 1		// n 갱신
downHeap(1)		// 힙 조정
return key
 
------------------------------------------------

• Code

// < 힙생성 >
// 배열(순차트리)의 형태 힙(순차 힙)생성 문제. ( # 연결리스트의 형태 힙 = 연결 힙 )
// 루트의 최소 키 저장 시 = 최소 힙(min-heap)
// 루트의 최대 키 저장 시 = 최대 힙(max-heap)
// 힙 생성 => 1. 삽입식(Insertion) 2. 상향식(bottom-up)
// 1.삽입식 = 모든 키들이 미리 주어진 경우, or 키들이 차례로 주어지는 경우
// 2.상향식 = Only 미리 키들이 미리 주어진 경우
// 동일한 키들의 동일 순서로 구성된 초기 리스트라도 삽입식, 상향식 중 어느 방식을 적요하느냐에 따라 상이한 힙이 생성 될 수 있다.
// 힙은 적정이진트리로 생성하기 떄문에 배열로 구현시 같은 레벨노드들의 키값을 출력하는 것이 쉽다
// ( 삽입식 힙생성, (키 값들이 순서대로 입력되는 경우 )
#include<stdio.h>
 
int n = 0;			// 키 값수 제어 변수 n
int arr[100];		// 빈 초기리스트
 
voidinsertItem(int key);	// 키 삽입
intremoveMax();	// 키 삭제
voidupHeap(int idx);	// idx에 저장된 키를 크기에 맞는 위치로 상향이동
voiddownHeap(int idx);	// idx에 저장된 키를 크기에 맞는 위치로 하향이동
voidprintHeap();	// 힙 요소들 레벨순서에 맞게 출력
 
intmain(){
	int key;
	char op;
 
	do
	{
		scanf("%c",&op);
		switch (op)
		{
		case 'i':
			scanf("%d", &key);
			insertItem(key);
			break;
		case 'd':
			printf("%d\n",removeMax());
			break;
		case 'p':
			printHeap();
			break;
		}
		getchar();
	} while (op != 'q');
	
	return 0;
}
 
voidinsertItem(int key){
	arr[n+1] = key;	// 마지막 노드 위치에 키캆 삽입
	upHeap(n+1);	// upHeap을 통해서 방금 마지막노드의 삽입된 키 값이, 최대힙 기준에 맞게 제자리 위치로 찾아감, 참고로 upHeap은 재귀
	n = n + 1;		// upHeap이 끝난 뒤에 노드의 개수 1증가
	printf("%d\n", 0);
}
intremoveMax(){
	int key = arr[1];	// 삭제될 키 값( 즉, 힙의 루트노드 키값 )을 따로 저장
	arr[1] = arr[n];	// (최대 힙기준) 루트노드에있는 키 값과, 마지막 노드 키값을 교환
	downHeap(1);	// 마지막노드의 키값이 루트노드의 키 값으로 대체된 후, 자기 자리에 맞는 위치로 찾아가게 dowmHeap
	n = n - 1;	// downHeap끝나고 전체 노드수 -1;
	return key;
}
voidupHeap(int idx)// ( 최대힙 생성 기준 ){
	int max;	// 최대값 저장 변수
	if (idx != 1)	// 루트노드 하나있을때 제외하고
	{
		if (arr[idx] >= arr[idx / 2])	// 현재 본인위치의 키값과, 본인의 부모노드의 키값을 비교해서 자기가 더 크면
		{
			max = arr[idx];
			arr[idx] = arr[idx / 2];
			arr[idx / 2] = max;	// 키 값 서로 교환하고
			upHeap(idx / 2);	// 본인의 부모노드 기준으로 upHeap재귀호출
		}
	}
}
voiddownHeap(int idx)// ( 최대힙 생성 기준 ){
	int greater,tmp;
	
	if (n >= idx * 2)	// 전체 노드수가 최소 본인의 왼쪽자식노드는 있을 경우에 들어간다
	{
		greater = idx * 2;	// 최대 키 값 위치 저장
		if (n >= idx * 2 + 1)	// 본인의 오른쪽 자식노드도 존재하면
			if (arr[idx * 2 + 1] > arr[greater])	// 왼쪽 노드와 오른쪽 노드중 키값이 더 큰 노드의 위치 저장
				greater = idx * 2 + 1;
		if (arr[idx] < arr[greater])	// 본인의 키 값과, 본인의 좌우 자식노드중에 더 큰 키값을 가진 노드의 키값과 비교해서 본인이 작으면
		{
			tmp = arr[idx];
			arr[idx] = arr[greater];
			arr[greater] = tmp;	// 더 큰 키값을 본인 위치로 올리고, 본인 키값은 그 자식노드의 키값으로 내린다.
			downHeap(greater);	// 그 후, 그 자식노드 기준으로 downHeap재귀호출
		}
	}
}
voidprintHeap(){
	for (int i = 1; i <= n; i++)
		printf(" %d", arr[i]);
	printf("\n");
}

• 실질적 구현단계 ( 상향식 힙생성 (재귀,비재귀). C ver. )

• 구현전에 설계 팁

[ PseudoCode ]
-------------------------------------------------------------------
 
Alg rBuildHeap(i)		// 힙생성 - 재귀버전
	input integer i, array H		// i: 현재 부트리의 루트 인덱스
	output array H		// H:전역 배열, heap
    
if(i > n)		// n: 전역변수
	return
rBuildHeap(2i)		// 현재 부트리의 좌 부트리를 힙 생성
rBuildHeap(2i + 1)		// 현재 부트리의 우 부트리를 힙 생성
downHeap(i)			// 현재 부트리의 루트와 좌우 부트리를 합친 힙 생성
return
 
---------------------------------------------------------------------
 
Alg buildHeap()		// 힙생성 - 비재귀버전
	input array H	// H: 전역배열, heap
	output array H
    
for i <- n/2 downto 1 	// n: 전역변수, 마지막 내부노드부터 역방향 루트까지
	downHeap(i)
return 
 
---------------------------------------------------------------------

• C Code ( 상향식 힙생성 - 재귀 )

// 상향식 힙생성 ( ver.재귀 )
#include <stdio.h>
 
int arr[100],n= 0;	// 배열의 최대 원소개수는 100개 미만
void rBuildHeap(int idx);	// 재귀형태 상향식 힙 생성
void downHeap(int idx);	// 다운 힙
void printHeap();	// 원소출력
 
int main()
{
	int keyCount;		// key원소 수 
		
	scanf("%d", &keyCount);	// key원소 수 입력
	for (int i = 1; i <= keyCount; i++)	// 0번째 인덱스원소는 비워놓고 1번째 인덱스위치부터 키값 삽입
		scanf("%d", &arr[i]);
	n = keyCount;	// 순차힙 전체크기를 키수 만큼 초기화
	rBuildHeap(1);	// 재귀 상향식 힙 생성
	for (int i = 1; i <= keyCount; i++)	// 생성 된 힙의 키값들 출력
		printf(" %d", arr[i]);
	return 0;	// 메인종료
}
void rBuildHeap(int idx)	// 상향식 힙 생성함수 ( 재귀 )
{
	if (idx <= n)	// 인자로 들어온 인덱스가 전체 키수보다 작거나 같을때까지 ( = 내부노드일 경우 )
	{
		if(idx*2 <= n)	// 현재 인덱스(i)의 왼쪽자식노드인덱스(2i)가 전체 키의 수보다 작거나 같으면
			rBuildHeap(idx * 2);	// 현재 인덱스(현재 노드)의 왼쪽자식인덱스 기준으로 rBuildHeap 재귀호출
		if(idx*2 + 1 <= n)	// 이것은 위에 설명과 같게, 오른쪽 자식노드의 경우
			rBuildHeap(idx * 2 + 1);
	}
	downHeap(idx);	// 부트리 기준으로 downHeap실행 ( root노드부터 리프노드 전 까지 downHeap 실행되는데 )
}
/*
n개의 노드에 대해 height가 0인 리프노드부터  각 height의 노드의 개수는 (n/2^(h+1))개이고 
상향식 힙생성에서 Height에 대해 리프노드들은 downHeap을 실행하지않는다 == 0
그 다음 높이부터는 자신의 바로 아래 자식노드까지만 downHeap을 하면되고 == 1
이 방식대로 높이가 h인 루트노드에 대해서는 downHeap을 h번하면 된다.
이 과정을 정리하면 리프노드부터 downHeap이 실행되니깐
( n/2^(1) * 0 ) + ( n/2^(2) * 1 ) + ... + ( n/2^(h+1) * h ) ==> O(n)만큼의 downHeap이 실행될 것이다.
downHeap코드의 가장 바깥쪽 조건문에서 이 과정이 진행된다.
*/
void downHeap(int idx)	// (최대힙기준)downHeap
{
	int greater, tmp;	// 본인의 왼쪽,오른쪽 자식노드중 더 큰 키값을 가진 자식노드의 인덱스(노드) 위치를 저장변수
 
	if (n >= idx * 2)	// 최소 자신의 왼쪽자식노드가 존재할경우 
	{
		greater = idx * 2;	// 일단 최대 키 인덱스는 왼쪽 자식으로하고
		if (n >= idx * 2 + 1)	// 오른쪽 자식도 있는데
			if (arr[idx * 2 + 1] > arr[greater])	// 왼쪽 자식보다 키값이 크면
				greater = idx * 2 + 1;	// 최대 키 인덱스 오른쪽자식노드로 변경
		if (arr[idx] < arr[greater])	// 이제 본인의 키값과 비교해서 자기 자식의 노드보다 작으면
		{
			tmp = arr[idx];
			arr[idx] = arr[greater];
			arr[greater] = tmp;	// 두 노드의 키값을 swap
			downHeap(greater);	// swap 한 자식을 기준으로 downHeap재귀
		}
	}
}
void printHeap()		// 생성 된 힙 키 값 출력
{
	for (int i = 1; i <= n; i++)	
		printf(" %d", arr[i]);
	printf("\n");
}

• C Code ( 상향식 힙생성 - 비재귀 )

// 상향식 힙 생성 ( ver.비재귀 )
#include <stdio.h>
 
int arr[100], n = 0;
 
void buildHeap();	// 비재귀형태 상향식 힙 생성
void downHeap(int idx);
void printHeap();
 
int main()
{
	int keyCount;		// key원소 수 
 
	scanf("%d", &keyCount);	// key원소 수 입력
	for (int i = 1; i <= keyCount; i++)	// 0번째 인덱스원소는 비워놓고 1번째 인덱스위치부터 키값 삽입
		scanf("%d", &arr[i]);
	n = keyCount;	// 순차힙 전체크기를 키수 만큼 초기화
	buildHeap();	// 비재귀 상향식 힙 생성
	for (int i = 1; i <= keyCount; i++)	// 생성 된 힙의 키값들 출력
		printf(" %d", arr[i]);
	return 0;	// 메인종료
}
 
void buildHeap()	// 상향식 힙생성 ( 비재귀적 )
{
	for (int i = n / 2; i >= 1; i--)	// 리프노드 바로 위층 내부노드중에 왼쪽 자식노드가 있는 순서상 가장 마지막 내부노드부터 시작해서 루트노드까지 downHeap을 실행한다.
		downHeap(i); 
}
/*
n개의 노드에 대해 height가 0인 리프노드부터  각 height의 노드의 개수는 (n/2^(h+1))개이고
상향식 힙생성에서 Height에 대해 리프노드들은 downHeap을 실행하지않는다 == 0
그 다음 높이부터는 자신의 바로 아래 자식노드까지만 downHeap을 하면되고 == 1
이 방식대로 높이가 h인 루트노드에 대해서는 downHeap을 h번하면 된다.
이 과정을 정리하면 리프노드부터 downHeap이 실행되니깐
( n/2^(1) * 0 ) + ( n/2^(2) * 1 ) + ... + ( n/2^(h+1) * h ) ==> O(n)만큼의 downHeap이 실행될 것이다.
downHeap코드의 가장 바깥쪽 조건문에서 이 과정이 판단된다.
*/
void downHeap(int idx)	// 재귀적 상향식 힙생성의 downHeap설명과 동일해서 생략
{
	int greater,tmp;
	if (n >= idx * 2)
	{
		greater = idx * 2;
		if (n >= idx * 2 + 1)
			if (arr[greater] < arr[idx * 2 + 1])
				greater = idx * 2 + 1;
		if (arr[idx] < arr[greater])
		{
			tmp = arr[idx];
			arr[idx] = arr[greater];
			arr[greater] = tmp;
			downHeap(greater);
		}
	}
}
void printHeap()	// 재귀적 상향식 힙생성의 printHeap설명과 동일해서 생략
{
	for (int i = 1; i <= n; i++)
		printf(" %d", arr[i]);
	printf("\n");
}

• [ 장르 ] Heap or ★ Priority_queue
• [ 문제 ]

• My Code ( 최소 순차 힙(순차리스트,배열) 구현 ver. )

#include <iostream>
using namespace std;
int arr[100000], n = 0;
 
void insertItem(int data);
int removeMin();
void upHeap(int idx);
void downHeap(int idx);
 
int main()
{
	int N,data;
 
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> N;
	while (N)
	{
		cin >> data;
		if (data != 0)
			insertItem(data);
		else
			if (data == 0 && n == 0)
				cout << 0 << '\n';
			else
				cout << removeMin() << '\n';
		N--;
	}
}
void insertItem(int data)
{
	arr[n + 1] = data;
	upHeap(n + 1);
	n = n + 1;
}
int removeMin()
{
	int removeData = arr[1];
 
	arr[1] = arr[n];
	downHeap(1);
	n = n - 1;
	return removeData;
}
void upHeap(int idx)
{
	int tmp;
	if (idx != 1)
	{
		if (arr[idx / 2] > arr[idx])
		{
			tmp = arr[idx];
			arr[idx] = arr[idx / 2];
			arr[idx / 2] = tmp;
			upHeap(idx / 2);
		}
	}
}
void downHeap(int idx)
{
	int smaller,tmp;
	
	if (n >= idx * 2)
	{
		smaller = idx * 2;
		if (n >= idx * 2 + 1)
			if (arr[smaller] > arr[idx * 2 + 1])
				smaller = idx * 2 + 1;
		if (arr[smaller] < arr[idx])
		{
			tmp = arr[idx];
			arr[idx] = arr[smaller];
			arr[smaller] = tmp;
			downHeap(smaller);
		}
	}
}

• ★ My Code ( Priority_queue < greater > ver. )

#include <iostream>
#include <queue>
 
using namespace std;
 
int main()
{
	int N, data;
	priority_queue<int, vector<int>, greater<int>> pq;		// ★ 내림차순 ( 기본옵션은 
 
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> N;
	while (N)
	{
		cin >> data;
		if (data != 0)
			pq.push(data);
		else
			if (data == 0 && pq.size() == 0)
				cout << 0 << '\n';
			else
			{
				cout << pq.top() << '\n';
				pq.pop();
			}
		N--;
	}
}

• [ CheckPoint ]

• 먼저, 힙 생성에 대해서, 힙 생성은 1. 삽입식 힙생성, 2.상향식 힙생성이 있다.
  1. 삽입식 힙생성 : 힙에 value에 대한 정보가 순차적으로 제시되는 경우
  2. 상향식 힙생성 : 힙에 value가 한번에 제시되는 경우
• 이 문제는 그 중 삽입식 힙 생성이고, 최대 힙, 최소 힙중에 "최소 힙" 생성이다.
• 참고로, 힙은 순차힙( 배열에 의한 )과 연결 힙( 연결리스트에 의한 )이 있는데, 구현의 편의성을 위해 "순차 힙"으로 구현했다.
  ( 사실, 현재 이 글을 작성하는 시점에서의 힙을 나는 순차힙으로만 구현해 봐서, 순차 힙으로 구현했다..^^;; )
• ver.1 ( 구현한 힙 )은 기본적인 힙 생성 절차이기 때문에 천천히 코드를 읽어보면 이해가 될 것이다.
  
• 포인트는 ver.2 ( Priority_queue )로 구현한 것인데, 중요한 걸 먼저 짚고가면, 정확히 이것은 힙이 아니다 !
  힙에 대한 성질은 내부적으로보면 전혀 맞지 않고, 오로지 이 문제가 "최소 힙"이지만 결론적으로, 출력할 때 힙의 최소값만 출력하면 되는 방식이기 때문에, 내부적으로 어떤지는 중요하지 않다. ( 다시한번, 강조하지만 이 문제에만 초점을 맞췄다. )
• 다음은, 어찌 됬든 Priority_queue를 사용할 것을 알았다면, C++에서 Priority_queue에 대한 사용법을 알아야 한다.
  
• 헤더파일 : include <queue>
  선언시 : priority_queue<자료형, 구현체, 비교연산자>
  ex) priority_queue< int , vector<int> , greater<int> > pq  >>> 작은순서( top( ) 기준 오름차순 )
       priority_queue< int , vector<int> , less<int> > pq  >>> 큰 순서( top( ) 기준 내림차순 )
  이 부분을 알고가자.

• [ 장르 ] 탐색
• [ 문제 ]

• My Code

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
int main()
{
	int N,M,data;
	vector<int> arr, check;
	
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
 
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> data;
		arr.push_back(data);
	}
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> data;
		check.push_back(data);
	}
	//sort(arr.begin(), arr.end());   // 처음엔 두 벡테를 정렬해놓고
	//sort(check.begin(), check.end());	// 비교하는 과정을 손볼려했는데 생각해보면 출력할 때 순서가 맞지 않는거 처럼 나온다.
	for (int i = 0; i < check.size(); i++)
	{
		auto iter = find(arr.begin(), arr.end(), check[i]);
		if (iter == arr.end()) 
			cout << 0 << '\n';
		else  
			cout << 1 << '\n';
	}
	return 0;
}

• CheckPoint

• 정답률이 낮아서, 성능을 높이는 문제인가하고 겁을 먹었다.
  그래서 일단 C++에 대한 입출력 성능을 높이기 위해 상단부에 선언을 해주고 개행도 '\n'으로 처리했다.
  
• 문제 포인트는 첫번째 받은 리스트안에 두번째 받은 리스트의 정수가 있는지 "들어온 순서대로" 체크해서 있으면 '1' 아니면 '0'을 출력하는 문제이다.
• 처음에는 뭔가 무작위로 들어오니 sort( )함수로 정렬 시킨 후 조건을 조작하면 최소한으로 탐색하지 않을까 했는데, 생각은 좋으나 이렇게하면 결과를 출력할 때, 기존의 리스트 순서가 바뀌어서 결과순서도 바뀌게 된다.
• 그래서 sort( )부분만 주석처리하고 제출했더니 정답이었다.
• 무엇보다 이 과정에서 check 벡터( 리스트로 생각하고 씀 )요소마다 arr 벡터( 리스트로 생각하고 씀 )내부에 존재하는지 for문을 통해 작성을 할 수도 있지만, find( )함수가 생각이나서 활용했다.
• ★ find( iter.begin( ), iter.end( ), 찾을 원소 ) 함수는 찾을 원소를 기준으로 iterator에 끝까지 조사해서 존재하면 그 위치의 iter를 반환하고 끝까지 조사했는데 찾을 원소가 없으면 v.end( ) (== 이것도 iterator ) 를 리턴한다. 이를 이용해서 if 문을 작성해서 처리했다.   

• [ 장르 ] deque
• [ 문제 ]

• My Code

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
 
using namespace std;
int main()
{
	int queSize, selectCnt,want,answer = 0;
	deque<int> dq;
	vector<int> element;
 
	cin >> queSize >> selectCnt;
	for (int i = 0; i < queSize; i++)
		dq.push_back(i + 1);
 
	for (int i = 0; i < selectCnt; i++)
	{
		cin >> want;
		element.push_back(want);
	}
 
	for (int i = 0; i < selectCnt; i++)
	{
		
		if (element[i] == dq.front())
			dq.pop_front();
		else
		{
			int index = find(dq.begin(), dq.end(), element[i]) - dq.begin();	// ★
			if (index <= dq.size() - index)
			{
			//	cout << index << endl;
				while (dq.front() != element[i])
				{
					dq.push_back(dq.front());
					dq.pop_front();
					answer++;
				}
			}
			else
			{
			//	cout << index << endl;
				while (dq.front() != element[i])
				{
					dq.push_front(dq.back());
					dq.pop_back();
					answer++;
				}
			}
			dq.pop_front();
		}
		//for (auto iter = dq.begin(); iter != dq.end(); iter++)
			//cout << *iter << ' ';
		//cout << endl;
	}
	cout << answer << endl;
	return 0;
}

• [ CheckPoint ]

• 처음에는 문제가 어떤 걸 원하는지 제대로 이해를 못했다. 문제가 "회전하는 큐"라서 원형 큐를 쓰면 되는 건가 생각했다.
  
• 이 문제가 묻는 것은 원소의 값이 무엇인지는 상관없다. 단지 처음 큐에서 2번째 줄에 입력되는 원소의 위치 순서에 대해 우선순위를 주고
  이 우선순위에 따라서 첫번째 원소를 뽑아내는 과정에서 왼쪽 오른쪽 이동 연산을 몇번하는지 Count하는게 문제이다.
  이렇게 말해놓고 나도 뭔소린지 이해 못한다. 그냥 이 첨부자료를 보는 것이 좋겠다.
  
• 문제가 어느정도 이해가 가면, 이건 맨 앞에 요소를 뽑아 낼 때만, Count가 누적이 안되고, queue의 범위가 줄어들기 때문에 queue에서
  매 차례 원하는 원소를 뒤에서든 앞에서든 이동시킬수 있도록 deque를 써야한다는 것을 인지하게 될 것이다.
• 그 다음 포인트는, 문제를 풀다보면, 매 차례 왼쪽(front) 과 오른쪽(back) 방향 중 어느쪽으로 이번 차례에는 pop()을하면서 front로 정답 요소를 이동시켜야 할까이다.
  이것은 문제의 이동연산의 최솟값을 출력하라고 했으니, 매 시점의 deque에서 원하는 원소의 index위치를 구하고 이를 front와 back중에 더 가까운 쪽으로 pop( )하면서 이동하면 된다.
  단, 어찌됬든 원하는 원소는 결국 front에서 pop( )되기 때문에 back 방향으로 pop 을하면서 front로 보낼때는 이동연산을 한번 더 해야하는 것을 알아야한다.
• 결국 우리는 매 과정에서 변화하는 기존에 원소값 인덱스를 찾아야한다. 그렇기 때문에 나는 find( )연산자를 생각했다.
• [ 형식 ]
  find( iterator.begin( ), iterator.end( ), 찾길 원하는 원소 값 ) 
  [ 반환 값 ]
  원소의 위치에 iterator를 반환 !
• 결국 현재 내가 원하는 원소의 "인덱스"를 알고 싶다면, 리턴된 값 - 전체 iterator.begin( )을 해줘야 연산 결과가 인덱스 값이 된다.
  ( 코드의 ★ 부분 참고하길 바란다. )
• 그리고 이 인덱스 값은 0부터가 아닌 1부터임을 알자.

• [ 목차 ]

• 우선순위 큐 ADT
• 우선순위 큐를 이용한 정렬
• 제자리 정렬
• 선택 정렬과 삽입 정렬 비교

• 우선순위 큐란 무엇일까 ?

• 우선순위 큐는 각 항목에 대해 ( 키, 원소 ) 쌍으로 저장되는 자료구조다.
• 일반적인 큐와 달리 들어오는 순서 (FIFO)가 아닌 일정한 키 값의 기준에따라서 큐 안에 데이터가 정렬되서 사용한다.

• 우선순위 큐 ADT 메쏘드

• 주요메쏘드
  
  • InsertItem(k,e) : 키 k인 원소 e를 큐에 삽입
  • element removeMin( ) : 큐로부터 최소 키를 가진 원소를 삭제해서 반환
    ( removeMax( ) 로 하냐 removeMin( )으로 하냐에 따라 우선순위의
    내부적인 정렬 상태가 내림차순 or 오름차순으로 결정된다. )
• 일반 메쏘드
  • integer size( ) : 큐의 항목수를 반환
  • boolean isEmpty( ) : 큐가 비어 있는지 여부를 반환
    ( 비어있으면 0(false), 그렇지 않으면 1(true) 리턴 ( 사용자 구현에 따라 이는 달라 질수 있다. )
•  접근 메쏘드
  • element minElement( ) : 큐에 최소 키를 가진 원소를 반환
  • element minKey( ) : 큐에서 최소 키를 반환
• 예외처리
  • emptyQueueException( ) : 비어 있는 큐에 대해 삭제나 원소 접근을 시도 할 경우 발생
  • fullQueueException( ) : 가득 찬 큐에 대해 삽입을 시도할 경우 발생
    ( 주로, 배열을 통한 우선순위 큐를 구현했을 경우 자주 발생한다. )

• 일반적(generic)인 우선순위 큐를 이용한 정렬

[ pseudocode ]
---------------------------------
Alg PQ-Sort(L)
	input list L
    Output sorted list L
    
P <- empty priority queue
while(!L.isEmpty())
	e <- L.removeFirst()
    P.insertItem(e)		// ★
while(!P.isEmpty())
	e<- P.removeMin()	// ★
    L.addLast(e)
return
----------------------------------
★로 표시한 부분, 외부 리스트 P 를 하나두고, 기존의 리스트 L의 요소들을 하나씩 빼내어 insertItem과
P에 들어간 요소들을 삭제하면서, 다시 원본리스트 L에 최소값을 넣어주는식의 방식 
( 이는 오름차순 정렬인 상황, 만약 내림차순으로 우선순위큐를 정렬시에는 removeMax()라는 함수가 필요할 것 )

• 여기서 일반적(generic)함수란 ?

• 함수의 인자타입,반환타입 상관없이 여려가지 타입에도 작동하는 함수

• 리스트에 기초한 우선순위 큐

• 무순리스트로 구현
  • 우선순위 큐의 항목들을 리스트에 임의 순서로 저장
  • [ 성능 ]
    • InsertItem : O(1) 시간 소요.
      => 항목을 리스트의 맨 앞 또는 맨뒤에 삽입할 수 있기 때문이다.
    • removeMin, minKey, minElement ( Max도 해당 ) : O(n) 시간 소요
      => 최소(최대) 키를 찾기 위해 전체 리스트를 순회해야 하기때문.
    • 비유하면, 시험지를 겉을 때는 막 쌓으면서 걷음.
      후에 시험지를 정리할 때 순서(ex.학번)에 맞게 정리
• 순서리스트로 구현
  • 우선순위 큐에 항목들을 리스트에 키 정렬 순서로 저장
  • [ 성능 ]
    • InsertItem : O(n) 시간 소요.
      => 항목을 삽입할 곳을 찾고 넣어야하기 때문.
    • removeMin,minKey, minElement ( Max도 해당 ) : O(1) 시간 소요
      => 최소(최대) 키가 리스트의 맨앞에 이미 정렬되어 있으므로.
    • 비유하면, 시험지를 걷을 때부터 (ex.학번)순서대로 정리하고
      후에는 이미 정리했으므로 순설대로 쓰기만 하면 된다.

• 선택 정렬 ( Selection-Sort )

• PQ-Sort의 일종
• 우선순위 큐를 "무순리스트"로 구현
• [ 실행시간 ]
  • n회 InsertItem 작업을 사용해서 원소들을 외부에 우선순위 큐에 삽입하는데 O(n) 시간 소요
  • n회의 removeMIn(Max) 작업을 사용하여 원소들을 우선순위 큐로 부터 정렬 순서로 삭제하면서 원래의 리스트에 다시 넣는다.
    n + (n-1) + (n-2) + ... + 2 + 1
  • Total : O(n^2)

• 삽입정렬 ( Inserttion Sort )

• PQ-Sort의 일종
• 우선순위 큐를 "순서리스트"로 구현
• [ 실행시간 ]
  • n회의 InsertItem 작업을 사용하여 원소들을 우선순위 큐에 삽입하는데 다음 비례하는 시간 소요. 애초에 기존 리스트에서 우선순위 큐에 넣을 때 우선순위에 맞게 넣어야하기 떄문이다.
    1 + 2 + ... + (n-2) + (n-1) + n
  • n회의 removeMin(Max) 작업을 사용하여 원소들을 우선순위 큐로부터 정렬 순서로 삭제하는데 O(n)시간 소요
  • Total : O(n^2)

 

• 제자리 정렬 ( In-Place Sort )

• 선택정렬,삽입정렬 모두 O(n) 공간을 차지하는 "외부의" 우선순위 큐를 사용하여 리스트를 정렬했다.
• 만약, 원래 리스트 자체를 위한 공간 이외에 O(1) 공간만을 사용한다면
  이를 "제자리(In-Place)"에서 수행한다고 말한다.
  = ★ 정렬 ( 리스트 내 ) 영역을 조정해 간다 생각하자.
• 일반적으로, 어떤 정렬 알고리즘이 정렬 대상 개체를 위해 필요한 메모리에 추가하여 오직 "상수 메모리"만을 사용한다면, 해당 정렬 알고리즘이 "제자리"에서 수행한다고 말한다.

• 제자리 선택 정렬 ( In-Place Selection-Sort )

• Selection-Sort가 외부 데이터구조를 사용하는 대신, "제자리"에서 수행하도록 구현 가능
• ★ 우선순위 큐 : 입력 리스트의 일부 ( 초록색 점선부분 )

• 제자리 선택정렬을 위해서는
  • 이 설명에 경우, 리스트의 앞부분을 정렬 상태로 유지
    ( 사용자 기준에 따라, 뒷부분을 정렬 상태로 유지해도 된다.
  • 리스트를 변경하는 대신에 SwapElements를 사용한다.

• 제자리 삽입 정렬 ( In-Place Insertion-Sort )

• Insertion-Sort가 외부 데이터구조를 사용하는 대신, 제자리에서 수행하도록 구현 가능
• ★ 우선순위 큐 : 입력 리스트의 일부 ( 초록색 점수부분 )

• 제자리 삽입정렬을 위해서는
  • 이 설명에 경우, 리스트의 앞부분을 정렬 상태로 유지
    ( 사용자 기준에 따라, 뒷부분을 정렬 상태로 유지해도 된다.
  • 리스트를 변경하는 대신 SwapElements를 사용한다.

• 제자리 선택정렬 vs 제자리 삽입정렬

[ pseudocode ]
---------------------------
 
Alg InPlaceSelectionSort(A)
	input array A of n Keys
    output sorted array A
 
for pass <- 0 to n - 2
	minLoc <- pass
    for j <- (pass + 1) to n -1
    	if(A[j] < A[minLoc]
        	minLoc <- j
        A[pass] <-> A[minLoc]
    A[pass] <-> A[minLoc]
return
 
---------------------------
 
Alg InPlaceInsertionSort(A)
	input array A of n Keys
    output sorted array A
 
for pass <- to n - 1
	save <- A[pass]
    j <- pass - 1
    while((j>=0) & (A[j] > save))
    	A[j+1] <- A[j]
        j <- j - 1
    A[j+1] <- save
return
 
---------------------------

• C Code

// clock()을 통해 시간 측정할때 현재 코드에 쓴 QueryPerformanceFrequency() => ms 단위로측정
// 외에도, nanosec단위로도 셀수있고, window()함수에서가 아닌 다른 환경에서 측정할수있는 방법도
// 임있을 상기하자.
#include <stdio.h>
#include <stdlib.h>
#include <Windows.h>
#include <time.h>
 
int* InPlaceSelectionSort(int* arr, int N);
int* InPlaceInsertionSort(int* arr, int N);
void SwapElement(int* a, int* b);
int* RegularArrangement(int* arr, int N);
int* InverseArrangement(int* arr, int N);
 
int main()
{
	int N, elem;
	int* arr1 = NULL, * arr2 = NULL;
	LARGE_INTEGER ticksPerSec;
	LARGE_INTEGER start, end, diff;
 
	srand(time(NULL));
	scanf("%d", &N);
	arr1 = (int*)malloc(sizeof(int) * N);
	arr2 = (int*)malloc(sizeof(int) * N);
 
	for (int i = 0; i < N; i++)
	{
		elem = rand() % N + 1;	// 그냥 이렇게되면 ,N이 32767이하에 수에서만 랜덤으로
		arr1[i] = elem;			// 입력하기때문에 중복이 많이 발생할 수 있다.
		arr2[i] = elem;		
	}
 
	// 정배열 , 역배열로 전환
	//arr1 = RegularArrangement(arr1,N);
	//arr2 = RegularArrangement(arr2,N);
	//arr1 = InverseArrangement(arr1, N);
	//arr2 = InverseArrangement(arr2, N);
 
	// 정렬 되었는지 확인용 출력
	/*for (int i = 0; i < N; i++)
		printf(" %d", arr1[i]);
	printf("\n");
	for (int i = 0; i < N; i++)
		printf(" %d", arr2[i]);
	printf("\n");*/
 
	QueryPerformanceFrequency(&ticksPerSec);
	QueryPerformanceCounter(&start);
	arr1 = InPlaceSelectionSort(arr1, N);
	QueryPerformanceCounter(&end);
 
	// 측정 값으로부터 실행시간 계산
	diff.QuadPart = end.QuadPart - start.QuadPart;
	printf("선택정렬 : %.9f ms\n", ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
 
	QueryPerformanceFrequency(&ticksPerSec);
	QueryPerformanceCounter(&start);
	arr2 = InPlaceInsertionSort(arr2, N);
	QueryPerformanceCounter(&end);
 
	diff.QuadPart = end.QuadPart - start.QuadPart;
	printf("삽입정렬 : %.9f ms\n", ((double)diff.QuadPart / (double)ticksPerSec.QuadPart) * 1000);
 
	// 선택,삽입정렬결과 출력부분
	/*for (int i = 0; i < N; i++)
		printf(" %d", arr1[i]);
	printf("\n");
	for (int i = 0; i < N; i++)
		printf(" %d", arr2[i]);*/
 
	free(arr1);
	free(arr2);
	return 0;
}
int* InPlaceSelectionSort(int* arr, int N)	// 제자리 선택정렬
{
	int minLoc, save;
	for (int i = N - 1; i > 0; i--)
	{
		minLoc = i;
		for (int j = i - 1; j >= 0; j--)
		{
			if (arr[j] > arr[minLoc])
				minLoc = j;
		}
		SwapElement(&arr[i], &arr[minLoc]); // 쿼리 퍼포먼스사이 시간측정에 함수를 넣지않고
	}										// 원래의 형태를 넣어주는것이 시간측정에 더 정확
	return arr;
}
int* InPlaceInsertionSort(int* arr, int N)	// 제자리 삽입정렬
{
	int save, j;
 
	for (int i = 1; i < N; i++)
	{
		save = arr[i];
		j = i - 1;
		while (j >= 0 && arr[j] > save)
		{
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = save;
	}
	return arr;
}
void SwapElement(int* a, int* b)
{
	int tmp;
 
	tmp = *a;
	*a = *b;
	*b = tmp;
}
int* RegularArrangement(int* arr, int N)	// 제자리정렬전에 정배열리스트 만들기 ( by.버블정렬 )
{
	int tmp;
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < N - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
	return arr;
}
int* InverseArrangement(int* arr, int N)	// 제자리정렬전에 역배열리스트 만들기 ( by.버블정렬 )
{
	int tmp;
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 0; j < N - 1; j++)
		{
			if (arr[j] < arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}
	return arr;
}

• 선택정렬 vs 삽입정렬

• 공통점
  • 전체적으로 O(n^2) 시간
    => 내부 반복문 : O(n) 선형탐색
    => 외부 반복문 : O(n) 패스
  • 제자리 버전은 O(1) 공간소요
  • 구현이 단순
  • 작은 n에 대해 유용 ( n이 클수록 삽입정렬에 관심을 보여야한다. )
• 초기 리스트가 완전히 또는 거의 "정배열"로 정렬된 겨우
  • ★ "제자리 삽입정렬" 이  더 빠르다.
  • 내부 반복문이 O(1)시간 소요
    => 따라서 전체적으로 O(n)시간에 수행된다.
  • 기존 리스트가 "역배열"로 정렬된 경우
    => swapElements 작업이 많이 소요되는경우
  • "제자리 선택정렬" 이 더 빠르다.
    => swapElements 작업이 패스마다 O(1)시간 수행되는데 반해,
    제자리 삽입정렬은 동일한 작업이 패스마다 최악의 경우 O(n)시간
    수행되기 떄문이다. 

• 실제 실행결과 ( 삽입정렬 vs 선택정렬 )

• 분석 결과

• 참고사항

• 실행시간을 측정하는 과정이 코드안에 있다.
  아래는 이에 대한 참고사항을 정리한 내용이다.
  
  

화이팅 !! Let's go M F !! Algorithm !! 

• [ 장르 ] Deque
• [ 문제 ]

• My Code

#include <iostream>
#include <deque>
 
using namespace std;
int main()
{
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int opcnt,i = 0,data;
	string str;
	deque<int> que;
	
	cin >> opcnt;
	while (i < opcnt)
	{
		cin >> str;
		if (!str.compare("push_back"))
		{
			cin >> data;
			que.push_back(data);
		}
		else if (!str.compare("push_front"))
		{
			cin >> data;
			que.push_front(data);
		}
		else if (!str.compare("front"))
		{
			if (que.empty()) cout << -1 << '\n';
			else cout << que.front() << '\n';
		}
		else if (!str.compare("back"))
		{
			if (que.empty()) cout << -1 << '\n';
			else cout << que.back() << '\n';
		}
		else if (!str.compare("pop_front"))
		{
			if (que.empty()) cout << -1 << '\n';
			else
			{
				cout << que.front() << '\n';
				que.pop_front();
			}
		}
		else if (!str.compare("pop_back"))
		{
			if (que.empty()) cout << -1 << '\n';
			else
			{
				cout << que.back() << '\n';
				que.pop_back();
			}
		}
		else if (!str.compare("size"))
			cout << que.size() << '\n';
		else
			cout << que.empty() << '\n';
		i++;
	}
	return 0;
}

[ CheckPoint ]

• 기본적인 Deque기능문제이다. C++은 Deque Container가 있기 때문에 deque연산을 쉽게 할 수 있다.
• Deque는 일반 queue와 달리 queue는 FIFO( First In First Out )으로
  들어가고 나가는 방향이 하나로, 보통 front, rear(back)으로 연산을 진행한다. 먼저 들어간 정보가 나올때도 가장 먼저 나간다.
• Deque는 들어가고 나가는 방향이 양방향이다. front,back 두 방향에서
  연산이 가능하다. 

• [ 장르 ] 재귀함수
• [ 문제 ]

• My Code

#include <iostream>
using namespace std;
 
void HanoiCount(int n);
void Hanoiprint(int start, int from, int end, int n);
int main()
{
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int num;
	cin >> num;
	HanoiCount(num);
	Hanoiprint(1, 2, 3, num);
	return 0;
}
void HanoiCount(int n)	// 하노이 탑 과정 수는 N개의 원반 수에 대해 (2^N -1)번
{
	int Pow = 1;
	for (int i = 0; i < n; i++)
		Pow *= 2;
	cout << Pow - 1 << '\n';
}
void Hanoiprint(int start, int from, int end, int n)
{
	if (n == 1)
		cout << start << ' ' << end << '\n';	// 기둥에 원반이 하나 남았을 경우
	else
	{
		Hanoiprint(start,end,from,n - 1);	// 그렇지 않으면 기둥의 마지막을 제외한 n-1개의 원반을 가운데 기둥에 옮기고
		cout << start << ' ' << end << '\n';	// 하나남은거 옮기고
		Hanoiprint(from, start, end, n - 1);	// 가운데 옮겼던 나머지기둥 목적지 기둥에 옮김
	}
}

• [ CheckPoint ]
  

1. 재귀함수의 대표적인 문제 중 하나인 하노이탑 문제이다. 하노이 탑의 성립 조건은 3개의 기둥 ( A,B,C ) 이라고 치자.
   A기둥의 크기가 다른 N개의 원반이 크기가 큰 순으로 쌓여있다. 목표는 C 기둥에 처음 상태 그대로 원반을 옮기는 것이다.
   
2. 주의사항은, 하노이탑의 원반들은 자기보다 큰 원반을 위에 쌓지 못한다. 그리고 한번에 한개의 원반만 옮길 수 있다.
3. N개의 원반을 하노이탑을 통해 처리하면, 항상 총 실행횟수는 (2^N - 1) 회 실행하게 된다.
4. 재귀함수 성질을 이용하는 것이 포인트인 문제. 재귀는 쉽게 생각할수록 좋다. 뭔가 반복적인 일을 수행할 때, 가장 작은 일의 단위인Base Case만 잘 생각하고, 나머지 많은 작업들은 또 다시 재귀를 통해 해결한다는 생각으로 코드를 작성하면 해결된다.
5. 이 문제 역시 로직을 잘 짜도, C++로 풀 경우 출력실행시간때문에 시간초과가 발생하기 떄문에, 코드 도입부에 C++입출력 개선코드를 삽입하고 개행도 endl보다 '\n'을 사용하면 해결 된다.
   
   

• [ 장르 ] Queue
• [ 문제 ]

• My Code

#include <iostream>
#include <queue>
#include <string>
using namespace std;
 
int main()
{
	int cnt,i = 0,data;
	queue<int> que;
	string str;
 
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);	 // ★ 입출력속도개선선언부
	cin >> cnt;
	while (i < cnt)
	{
		cin >> str;
		if (!str.compare("push"))
		{
			cin >> data;
			que.push(data);
		}
		else if (!str.compare("pop"))
		{
			if (!que.empty())
			{
				cout << que.front() << '\n';	// ★ 개행마다 endl이 아닌 '\n'
				que.pop();
			}
			else
				cout << -1 << '\n';
		}
		else if (!str.compare("front"))
		{
			if (!que.empty())
				cout << que.front() << '\n';
			else
				cout << -1 << '\n';
		}
		else if (!str.compare("back"))
		{
			if (!que.empty())
				cout << que.back() << '\n';
			else
				cout << -1 << '\n';
		}
		else if (!str.compare("size"))
			cout << que.size() << '\n';
		else
			cout << que.empty() << '\n';
		i++;
	}
}

[ CheckPoint ]

• 기본적인 큐(Queue) 기능문제이다. C++에선 <queue> container에 모든 왠만한 queue연산은 제공되 있으므로 이를 잘 인지하고 있는지
  확인하는 정도의 문제이다.
• 다만, 이 문제 역시 실행속도 문제때문에 메인 본문에 코드에 주석처리로 된 ★ 부분이 선언부를 작성해주고, 하나 더 C++의 endl개행보다 
  '\n'  을 사용하는것을 지향한다.

• [ 장르 ] 트리

• My Code ( 트리생성 및 순회를 구현 )

#include <iostream>
using namespace std;
 
typedef struct Node
{
	char data;
	struct Node* left;
	struct Node* right;
}Node;
 
void MakeTree(Node* root,int n);
void MakeSubTree(Node* node, char MyData, char LData, char RData);
int IsInternal(Node* node);
void PreOrderPrint(Node *node);
void InOrderPrint(Node* node);
void PostOrderPrint(Node* node);
 
int main()
{
	Node root;
	int Nodecount;
 
	cin >> Nodecount;
	MakeTree(&root, Nodecount);
	return 0;
}
void MakeTree(Node* root,int n)
{
	char MyData, LData, RData;
	int i = 0;
	root->left = NULL;
	root->right = NULL;
	
	cin >> MyData >> LData >> RData;
	root->data = MyData;
	if (LData != '.')
	{
		Node *newNode = (Node*)malloc(sizeof(Node));
		newNode->data = LData;
		newNode->left = NULL;
		newNode->right = NULL;
		root->left = newNode;
	}
	if (RData != '.')
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->data = RData;
		newNode->left = NULL;
		newNode->right = NULL;
		root->right = newNode;
	}
	while (i < n - 1)
	{
		cin >> MyData >> LData >> RData;
		MakeSubTree(root, MyData, LData, RData);
		i++;
	}
	PreOrderPrint(root); cout << endl;
	InOrderPrint(root); cout << endl;
	PostOrderPrint(root); cout << endl;
}
void MakeSubTree(Node* node, char MyData, char LData, char RData)
{
	if (node->data == MyData)
	{
		if (LData != '.')
		{
			Node* newNode = (Node*)malloc(sizeof(Node));
			newNode->data = LData;
			newNode->left = NULL;
			newNode->right = NULL;
			node->left = newNode;
		}
		if (RData != '.')
		{
			Node* newNode = (Node*)malloc(sizeof(Node));
			newNode->data = RData;
			newNode->left = NULL;
			newNode->right = NULL;
			node->right = newNode;
		}
	}
	else
	{
		if (!(IsInternal(node)))
		{
			if (node->left != NULL)
				MakeSubTree(node->left, MyData, LData, RData);
			if (node->right != NULL)
				MakeSubTree(node->right, MyData, LData, RData);
		}
	}
}
int IsInternal(Node* node)
{
	return (node->left == NULL) && (node->right == NULL);
}
void PreOrderPrint(Node* node)
{
	cout << node->data;
	if (node->left != NULL)
		PreOrderPrint(node->left);
	if (node->right != NULL)
		PreOrderPrint(node->right);
}
void InOrderPrint(Node* node)
{
	if (node->left != NULL)
		InOrderPrint(node->left);
	cout << node->data;
	if (node->right != NULL)
		InOrderPrint(node->right);
}
void PostOrderPrint(Node* node)
{
	if (node->left != NULL)
		PostOrderPrint(node->left);
	if (node->right != NULL)
		PostOrderPrint(node->right);
	cout << node->data;
}

• Another Code ( 문제의 취지에 맞는 순차리스트(배열)을 이용한 풀이 )

#include <cstdio>
 
char tree[26][2] = { '.', };
 
void preorder(char root) {
    if (root == '.') return;
    else {
        printf("%c", root);
        preorder(tree[root-'A'][0]);
        preorder(tree[root-'A'][1]);
    }
}
 
void inorder(char root) {
    if (root == '.') return;
    else {
        inorder(tree[root-'A'][0]);
        printf("%c", root);
        inorder(tree[root-'A'][1]);
    }
}
 
void postorder(char root) {
    if (root == '.') return;
    else {
        postorder(tree[root-'A'][0]);
        postorder(tree[root-'A'][1]);
        printf("%c", root);
    }
}
 
int main() {
 
    int n, i;
    char root, left, right;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++) {
        scanf(" %c %c %c", &root, &left, &right);
        tree[root-'A'][0] = left;		// [][0] => 왼쪽자식 
        tree[root-'A'][1] = right;		// [][1] => 오른쪽자식을 의미
    }
 
    preorder('A');
    printf("\n");
    inorder('A');
    printf("\n");
    postorder('A');
    printf("\n");
 
    return 0;
}