yongmin

1. 문제해결과 알고리즘

    - 문제해결과정

    - 알고리즘 분석 

2. 데이터 추상화와 자료구조

    - 데이터 추상화

    - 자료구조 : tree, binary tree, stack, queue, heap, union-find, dictionary, ...

4. Sorting

    - 정렬 : insertion sort, quick sort, merge sort, heap sort, radix sort

6.  Dynamic sets & Searching

    - array doubling & amortized analysis

    - BST

    - Red-Black tree

7. Graph and Graph Search

    - Graph

    - Graph traversal : pre-order, in-order, post-order

    - Graph search : DFS, BFS

    - Strongly Connected Components

8. Graph optimization problem & greedy algorithm

    - optimization problem

    - graph optimization problem : MST, shortest path

    - MST -> Prim algorithm, Kruskal algorithm

    - shortest path -> dijkstra algorithm

9. Transitive Closure & All-pairs shortest paths

    - transitive closure, Floyd-Warshall algorithm

    - All-pairs shortest paths

10. Dynamic Programming

    - dynamic programming & recursive algorithm

    - Matrix-chain Multiplication

11. String Match

    - string match

    - Brute-Force

    - KMP

    - Boyer-Moore

13. NP-Complete Problem

    - Optimization problem vs Decision problem 

    - Class P, Class NP, Class NP-hard problem

    - Class NP-Complete problem

1. 단순 문자열 매칭
2. KMP (Knuth-Morris-Pratt) 알고리즘
3. Boyer-Moore 알고리즘

단순 문자열 매칭 알고리즘

• 문자 하나씩 확인하는 알고리즘으로 가장 간단한 형태의 알고리즘
• 의사코드
  • 전체 문자열의 첫번째 문자에서 시작하여 찾을 문자열의  첫번째 문자를 비교
  • 매칭이 이루어지면 찾을 문자열의 다음 문자를 비교
  • 매칭이 이루어지지 않으면 전체 문자열의 두번째 문자에서 다시 시작
  • 위의 과정을 반복하여 문자열을 찾는다
• 시간 복잡도 : O(N*M) // N = 전체 문자열 길이, M = 찾을 문자열 길이

KMP (Knuth-Morris-Pratt) 알고리즘

• 접두사와 접미사의 개념을 활용하여 '반복되는 연산을 얼마나 줄일 수 있는지 판별'하고 매칭할 문자열을 빠르게 점프하는 기법
• 접두사 : 찾을 문자열의 앞에 있는 문자열
• 접미사 : 찾을 문자열의 뒤에 있는 문자열
• 경계(border) : 접두사와 접미사가 일치하는 쌍
• 의사코드
  • 전체 문자열의 첫번째 문자부터 찾을 문자열과 비교시작
  • 매칭이 이루어지지 않은 문자가 발견되면, 발견되기 전까지 전체 문자열과 일치했던 찾을 문자열의 경계를 구한다.
  • 찾을 문자열의 접두사를 전체 문자열의 접미사로 점프하여 비교를 재개
• 시간 복잡도 : O(N) // N = 전체 문자열 길이
• 경계를 찾는데 소요되는 비용은 공짜가 아니므로, 검색을 수행하는 중간에 매번 경계를 찾는것은 고비용
  => 검색을 수행하기 전에 미리 찾을 문자열로 부터 경계의 정보를 갖는 "테이블"을 생성
  • 테이블 인덱스 : 일치 접두부의 길이
  • 테이블 원소 : 일치 접두부의 최대 경계 너비 (첫번째 문자는 일치 접두부가 존재하지 않으므로 항상 -1)
  • 매칭 불일치시 이동 거리 = 일치 접두부의 길이 - 최대경계너비

Boyer-Moore 알고리즘

• 오른쪽에서 왼쪽으로 비교하고 이동은 왼쪽으로 오른쪽으로 하는 방식
• 오른쪽 끝에 문자가 일치 하지 않고 해당 본문 문자가 패턴에 존재하지 않으면 패턴 길이만큼 이동

Greedy Algorithm, 탐욕알고리즘

• 정의 : 당장 눈 앞에 보이는 최적의 상황만을 쫒는 알고리즘
• 특징 : 탐욕알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

예시코드

// boj - 5585 : greedy algorithm

#include<iostream>
using namespace std;

int main() {
	int monney;
	cin >> monney;
	monney = 1000 - monney;
	int res = 0;

	// 500
	int p = monney / 500;
	res += p;
	monney -= (500 * p);

	// 100
	p = monney / 100;
	res += p;
	monney -= (100 * p);

	// 50
	p = monney / 50;
	res += p;
	monney -= (50 * p);

	// 10
	p = monney / 10;
	res += p;
	monney -= (10 * p);

	// 5
	p = monney / 5;
	res += p;
	monney -= (5 * p);

	// 1
	p = monney / 1;
	res += p;
	monney -= (1 * p);

	cout << res << endl;
	return 0;
}

• Graph
• DFS
• BFS
• Dijkstra 

Graph

• 정의 : 노드의 상하위 개념이 없고, 노드(혹은 버텍스)와 노드들을 잇는 엣지로 구성되어 있는 자료구조
• 용어
  • 정점(vertex): 위치라는 개념. (node 라고도 부름)
  • 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
  • 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
  • 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
    • 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
  • 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
  • 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
    • 방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
  • 경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
  • 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
  • 사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

• 특징
  • 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
  • self-loop 뿐 아니라 loop/circuit 모두 가능하다.
  • 루트 노드라는 개념이 없다.
  • 부모-자식 관계라는 개념이 없다.
  • 순회는 DFS나 BFS로 이루어진다.
  • 트리는 그래프의 한 종류이다.

• 그래프 종류
  • 무방향 그래프(Undirected Graph) : 무방향 그래프의 간선은 간선을 통해서 양 방향으로 갈 수 있다.
  • 방향 그래프(Directed Graph) : 간선에 방향성이 존재하는 그래프
  • 가중치 그래프(Weighted Graph) : 간선에 비용이나 가중치가 할당된 그래프
  • 연결 그래프(Connected Graph) : 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우
  • 비연결 그래프(Disconnected Graph) : 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
  • 사이클(Cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
  • 단순 경로(Simple Path): 경로 중에서 반복되는 정점이 없는 경우
  • 비순환 그래프(Acyclic Graph) : 사이클이 없는 그래프
  • 완전 그래프(Complete Graph) : 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프
• 구현방법

 인접리스트

• 모든 정점(혹은 노드)을 인접 리스트에 저장한다. 즉, 각각의 정점에 인접한 정점들을 리스트로 표시한 것
• 장점
  • 어떤 노드에 인접한 노드들 을 쉽게 찾을 수 있다.
  • 그래프에 존재하는 모든 간선의 수 는 O(N+E) 안에 알 수 있다. : 인접 리스트 전체를 조사
• 단점 : 두 정점을 연결하는 간선의 존재 여부를 아는데 시간이 오래걸린다. O(V) 

인접행렬

• 인접 행렬은 NxN 불린 행렬(Boolean Matrix)로써 matrix[i][j]가 true라면 i -> j로의 간선이 있다는 뜻
• 장점
  • 구현이 쉽다. 
  • 두 정점을 연결하는 간선의 존재 여부를 O(1) 안에 즉시 알 수 있다. : M[i][j]
  • 정점의 차수 는 O(N) 안에 알 수 있다. : 인접 배열의 i번 째 행 또는 열을 모두 더한다
• 단점
  • 특정 노드에 인접한 노드들을 찾기 위해서는 모든 노드를 전부 순회해야 한다. ON)
  • 그래프에 존재하는 모든 간선의 수는 O(N^2) 안에 알 수 있다. : 인접 행렬 전체를 조사한다.
•  

Graph Search

DFS, Depth-First-Search

• 정의 :  시작점에서 노드를 따라 끝까지 간 후, leaf node를 만나게 되면 다시 제자리로 돌아와서 탐색
• 의사코드
  • a 노드(시작 노드)를 방문한다. 방문한 노드는 방문했다고 표시한다.
  • a와 인접한 노드들을 차례로 순회한다. a와 인접한 노드가 없다면 종료한다.
  • a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
  • b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
  • b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
    즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
  • 아직 방문이 안 된 정점이 없으면 종료한다. 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다
• DFS 시간복잡도
  • 인접 리스트로 표현된 그래프: O(N+E)
  • 인접 행렬로 표현된 그래프: O(N^2)

BFS, Breath-First-Search

• 정의 : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문
• 의사코드
  • a 노드(시작 노드)를 방문한다. (방문한 노드 체크)
  • 큐에 방문된 노드를 삽입(enqueue)한다.
  • 초기 상태의 큐에는 시작 노드만이 저장
  • 즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
  • 큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.
  • 큐에서 꺼낸 노드를 방문한다.
  • 큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
  • 인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
  • 큐에 방문된 노드를 삽입(enqueue)한다.
  • 큐가 소진될 때까지 계속한다.
• BFS 시간복잡도
  • 인접 리스트로 표현된 그래프: O(N+E)
  • 인접 행렬로 표현된 그래프: O(N^2)

Shortest path

Dijkstra algorithm

• 정의 : 그래프에서 노드 사이의 최단 경로를 찾는 알고리즘
• 의사코드 (P[A][B]는 A와 B 사이의 거리라고 가정한다)

1. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무한으로 간주될 수 있는 값을 의미한다.) 보통은 최단거리 저장 배열의 이론상 최대값에 맞게 INF를 정한다. 실무에서는 보통 d의 원소 타입에 대한 최대값으로 설정하는 편.

2. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장한다.

3. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B]와 d[B]의 값을 비교한다. INF와 비교할 경우 무조건 전자가 작다.

4. 만약 d[A] + P[A][B]의 값이 더 작다면, 즉 더 짧은 경로라면, d[B]의 값을 이 값으로 갱신시킨다.

5. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다.

6. A의 상태를 "방문 완료"로 바꾼다. 그러면 이제 더 이상 A는 사용하지 않는다.

7. "미방문" 상태인 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드 하나를 골라서 그 노드를 A에 저장한다.

8. 도착 노드가 "방문 완료" 상태가 되거나, 혹은 더 이상 미방문 상태의 노드를 선택할 수 없을 때까지, 3~7의 과정을 반복한다.

9. 도착 노드에 저장된 값이 바로 A로부터의 최단 거리. 만약 이 값이 INF라면, 중간에 길이 끊긴 것임을 의미.

예시코드

// BOJ 1260 - DFS, BFS

// input
// 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 
// 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.
// 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

// output
// 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>			// sort()함수
using namespace std;

vector< vector<int> > graph;	// 인접리스트로 구현된 그래프
vector<bool> visited;			// 정점 방문여부를 기록하기 위한 배열

void DFS(int start);
void BFS(int start);

int main(void) {

	int N;	//정점(vertex)의 갯수
	int M;	//간선(edge)의 갯수
	int V;	// 탐색 시작할 정점의 번호

	cin >> N >> M >> V;
	graph.resize(N + 1);			// 정점을 번호를 그대로 인덱스로 사용하기 위해 n+1의 크기 할당
	visited.resize(N + 1);			// 정점을 번호를 그대로 인덱스로 사용하기 위해 n+1의 크기 할당

	for (int m = 0; m < M; m++) {	// 두 정점 연결
		int v1, v2;
		cin >> v1 >> v2;
		graph[v1].push_back(v2);
		graph[v2].push_back(v1);
	}

	DFS(V);
	cout << endl;
	visited.resize(0);			// 방문 기록 초기화
	visited.resize(N + 1);
	BFS(V);

	return 0;
}

void DFS(int start) {
	if (visited[start] == true) return;
	visited[start] = true;
	cout << start << " ";
    
     // 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
	sort(graph[start].begin(), graph[start].end());
    
	for (int i = 0; i < graph[start].size(); i++) {
		int next = graph[start][i];
		DFS(next);
	}
}

void BFS(int start) {
	queue<int> q;
	q.push(start);
	visited[start] = true;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << " ";
		for (int i = 0; i<graph[cur].size(); i++) {
			int next = graph[cur][i];
			if (!visited[next]) {
				q.push(next);
				visited[next] = true;
			}
		}
	}
}

Tree

• 정의 : '노드'와 '간선'으로 구성 된 자료구조로, 그래프의 한 종류이다.

용어

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

트리 종류

• Binary Tree (이진 트리) : 각 노드가 최대 두 개의 자식을 갖는 트리 

• Complete Binary Tree (완전이진트리) : 트리의 마지막 레벨을 제외한 모든 레벨이 채워져있고, 마지막 레벨은 왼쪽에서 오른쪽으로 채워진 트리
• Full binary Tree (전이진트리) : 모든 노드가 0개 또는 2개의 자식을 갖는 트리
• Perfect Binary Tree (포화이진트리) : 트리의 모든 레벨이 꽉찬 이진트리. 완전이진트리이자 전이진트리

• Binary Search Tree (이진탐색트리) : 왼쪽 자식 <= 부모 <= 오른쪽 자식 을 만족하는 이진트리
• Balanced Tree (균형트리) : AVL tree, red-black tree
• Binary Heap (이진 힙) : min heap, max heap

Traversal, 순회

• pre-order (전위 순회) : 부모노드 -> 왼쪽자식노드 -> 오른쪽자식노드
• in-order (중위 순회) : 왼쪽자식노드 -> 부모노드 -> 오른쪽자식노드
• post-order (후위 순회) : 왼쪽자식노드 -> 오른쪽자식노드 -> 부모노드

예시코드

// binary search tree

#include <iostream>
#include <vector>
using namespace std;

class Node {
public:
	int data;
	Node* left;
	Node* right;
	Node(int d=-1, Node* pleft=NULL, Node* pright=NULL){
		data = d;
		left = pleft;
		right = pright;
	}
};

class BinarySearchTree {
public:
	Node* root;
	BinarySearchTree() {
		root = NULL;
	}
	void search(Node* par, int data) {
		if (par == NULL) {
			cout << data << ": 노드 존재 X" << endl;
			return;
		}
		else if (par->data == data) {
			cout << data << ": 노드 발견!" << endl;
			return;
		}
		else if (par->data > data) {
			cout << "left" << endl;
			search(par->left, data);
			return;
		}
		else if (par->data < data) {
			cout << "right" << endl;
			search(par->right, data);
			return;
		}
	}
	void insert(Node* & par, int data) {
		if (par == NULL) {
			par = new Node(data, NULL, NULL);
			return;
		}
		else {
			if (par->data <= data) {
				insert(par->right, data);
			}
			else if (par->data > data) {
				insert(par->left, data);
			}
			return;
		}
	}
	void remove(Node*& par, int data) {
		if (par == NULL) {
			cout << data << " 삭제 실패(노드 존재 X)" << endl;
			return;
		}
		else if (par->data == data) {
			cout << data << " 삭제 성공" << endl;
			delete par;
			par = NULL;
			return;
		}
		else if (par->data > data) {
			remove(par->left, data);
			return;
		}
		else if (par->data < data) {
			remove(par->right, data);
			return;
		}
	}
	void preOrder(Node* cur) {
		if (cur == NULL) {
			return;
		}
		cout << cur->data << " ";
		if (cur->left != NULL) {
			preOrder(cur->left);
		}
		if (cur->right != NULL) {
			preOrder(cur->right);
		}
	}
	void inOrder(Node* cur) {
		if (cur == NULL) {
			return;
		}
		if (cur->left != NULL) {
			inOrder(cur->left);
		}
		cout << cur->data << " ";
		if (cur->right != NULL) {
			inOrder(cur->right);
		}
	}
	void postOrder(Node* cur) {
		if (cur == NULL) {
			return;
		}
		if (cur->left != NULL) {
			postOrder(cur->left);
		}
		if (cur->right != NULL) {
			postOrder(cur->right);
		}
		cout << cur->data << " ";
	}
};

int main() {
	// binary search tree 생성
	BinarySearchTree bst;
	
    //노드 생성
	bst.insert(bst.root,100);
	bst.insert(bst.root, 123);
	bst.insert(bst.root, 32);
	bst.insert(bst.root, 77);
	bst.insert(bst.root, 15);
	bst.insert(bst.root, 453);
	bst.insert(bst.root, 46);
	bst.insert(bst.root, 84);
	bst.insert(bst.root, 256);
	
    // 탐색연산
	bst.search(bst.root, 99);
	cout << endl;
	bst.search(bst.root, 15);
	cout << endl;
    
	// 제거연산
	bst.remove(bst.root, 15);
	cout << endl;
	bst.remove(bst.root, 99);
	cout << endl;
	bst.search(bst.root, 15);
	cout << endl;
	
    // 순회
	cout << "pre-order : ";
	bst.preOrder(bst.root);
	cout << endl;

	cout << "in-order : ";
	bst.inOrder(bst.root);
	cout << endl;

	cout << "post-order : ";
	bst.postOrder(bst.root);
	cout << endl;
    
	return 0;
}

'

용어 정의 

해시함수 : 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. 균일하게 매핑할수록 좋은 해시함수이다.

해시 : 해시 함수에 얻어지는 값

해시 테이블 : 해시 값을 인덱스로 하여 데이터를 저장하고 있는 자료구조

Hashing

• 정의 : 데이터를 담을 해시 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시함수에 의해 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 과정
• 장점 : 데이터 접근 속도가 빠르다.
• 단점 : 충돌(collision)발생 - 서로 다른 입격 값에 대해 동일한 해시 테이블 주소를 반환하는 경우
• 해결법
  • chaining : 충돌되는 데이터들을 해당 주소에 링크드 리스트로 연결
  • open addressing : 충돌 발생시 해당 주소에 고정 폭 만큼을 더한 주소 값에 데이터 저장
    • linear probing : 고정 폭의 값을 1로 설정하여 선형적으로 빈 주소를 탐색
    • double hashing : 제 2의 해시함수의 값을 고정 폭의 값으로 설정하여 해시테이블 내의 클러스터를 방지
• 예시코드

// double hashing

#include <iostream>
#include <vector>

using namespace std;
#define AVAILABLE 0
#define OCCUPIED 1

class Node {
public:
	int key;
	int value;
	bool state;
	Node(int k, int v) {
		key = k;
		value = v;
		state = OCCUPIED;
	}
};

class hashmap {
public:
	int cap;
	vector<Node*> bucketArr;

	hashmap() {
		cap = 353333;
		bucketArr.resize(cap, NULL);
	}

	int hashCode(int k) { // key ->integer
		return k;
	}

	int compFunc(int in) { //integer -> hashvalue
		int ret = in % cap;
		return ret;
	}

	int hashFunc(int k) { //key -> hash value
		return compFunc(hashCode(k));
	}

	int doubleHashFunc(int k) {
		return (17 - (hashCode(k) % 17));
	}

	int insert(int k, int v) { //key, value 저장하고 저장한 위치 반환

		int idx = hashFunc(k);
		int dHashVal = doubleHashFunc(k);

		while (1) {
			if (bucketArr[idx] == NULL) {
				bucketArr[idx] = new Node(k,v);
				break;
			}
			idx = (idx + dHashVal) % cap;
		}

		return idx;
	}

	int search(int k) { //double hashing's search : 해당 키값의 위치 반환
		int idx = hashFunc(k);
		int probnum = 1;
		int dhashVal = doubleHashFunc(k);

		for (int i = 0; i < cap; i++) {

			if (bucketArr[idx] == NULL) {
				idx = -1;
				break;
			}
			else if (bucketArr[idx]->state == AVAILABLE) {
				idx = (idx + dhashVal) % cap;
				probnum++;
			}
			else if (bucketArr[idx]->key == k) {
				break;
			}
			else {
				idx = (idx + dhashVal) % cap;
				probnum++;
			}
		}
		if (idx <= -1)
			cout << 0 << ' ' << probnum << endl;
		else
			cout << 1 << ' ' << probnum << endl;

		return idx;
	}

	void remove(int k) {
		int idx = search(k);
		if (idx == -1)
			return;
		else
			bucketArr[idx]->state = AVAILABLE;
		return;
	}
};


int main() {

	int testcase = 0;
	cin >> testcase;

	for (int i = 0; i < testcase; i++) {
		hashmap map;
		int size = 0;
		cin >> size;
		for (int a = 0; a < size; a++) {
			int k = 0;
			int v = 0;
			cin >> k;
			cin >> v;
			map.insert(k, v);
		}

		int num = 0;
		cin >> num;

		for (int b = 0; b < num; b++) {
			int search = 0;
			cin >> search;
			map.search(search);
		}
	}
	return 0;
}

탐색의 분류

1. 선형 자료구조 ( 어레이, 리스트, ...) 내에서의 탐색

• 선형탐색 (linear search) 또는 순차탐색 (sequential search) 
• 이분탐색 (binary search) : 분할정복을 이용한 탐색
• 해싱 (hashing)

2. 비선형 자료구조 ( 트리, 그래프, ...) 내에서의 탐색

• tree traversal
• DFS
• BFS

선형탐색, linear Search

• 정의 : 데이터의 집합을 처음부터 끝까지 차례대로 하나씩 검색하는 방법
• 장점 : 구현하기 쉽고 데이터 집합이 정렬되어 있지 않아도 된다
• 단점 : 검색시간이 오래걸린다
• 시간복잡도
  • worst : O(n)
  • average : O(n)
  • best : O(1)     // 첫번째 인덱스의 값이 찾고자 하는 값인 경우
• 예시코드

// linear search

#include <iostream>
#include <vector>
#define MAX_SIZE 15
using namespace std;

int linearSearch(vector<int>& arr, int find);

int main() {
	vector<int> arr;

	for (int i = 0; i < MAX_SIZE; i++)
		arr.push_back((i + 1));

	cout << linearSearch(arr, 7) << endl;	// 7값의 인덱스 출력

	return 0;
}

int linearSearch(vector<int>& arr, int find) {
	int res = -1;
	for (int j = 0; j < arr.size(); j++) {
		if (arr[j] == find) {
			res = j;
			break;
		}
	}
	return res;
}

이분탐색, Binary Search

• 정의 : 데이터 집합의 범위를 반씩 나누어 가면서 분할정복하여 탐색하는 방법
• 장점 : 탐색 속도가 빠르다
• 단점 : 데이터집합 안의 값들이 정렬되어 있어야 한다.
• 시간복잡도 
  • worst : O(logn)
  • average : O(logn)
  • best : O(1)      // 중간 인덱스의 값이 찾고자 하는 값인 경우
• 예시코드

// binary search

#include <iostream>
#include <vector>
#define MAX_SIZE 15
using namespace std;

int binarySearch(vector<int>& arr, int find);

int main() {
	vector<int> arr;

	for (int i = 0; i < MAX_SIZE; i++)
		arr.push_back((i + 1));

	cout << binarySearch(arr, 7) << endl;	// 7값의 인덱스 출력

	return 0;
}

int binarySearch(vector<int>& arr, int find) {
	int res = -1;
	int left = 0;
	int right = arr.size() - 1;
	int mid;

	while (left <= right) {
		mid = left + (right - left) / 2;	// 오버플로우를 방지한 (left+right)/2 연산
		if (arr[mid] == find) {
			res = mid;
			break;
		}
		else if (arr[mid] < find) {
			left = mid+1;
		}
		else { // arr[mid] > find
			right = mid-1;
		}
	}
	return res;
}

Heap Sort

• 최대 힙 트리나 최소 힙 트리를 이용해 정렬을 하는 방법
• heap : 반정렬 상태 ( 부모노드 >= 자식노드 or 부모노드 <= 자식노드)를 만족하는 완전 이진트리
• 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.
• 과정 설명

1. 정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.

2. 내림차순을 기준으로 정렬

3. 그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다

4. 삭제되는 요소들(최댓값부터 삭제)은 값이 감소되는 순서로 정렬되게

Max Heap 삽입

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질 (반정렬상태)을 만족시킨다.

Max Heap 삭제

1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
2. 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
3. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
4. 힙을 재구성한다.

시간 복잡도

• worst : O(nlogn)
• average : O(nlogn)
• best : O(nlogn)

예시코드

//heap sort

#include <iostream>
#include <vector>
#define MAX_SZIE 11
using namespace std;

void heapInsert(vector<int>& arr, int val);
int  heapRemove(vector<int>& arr);

int main() {

    vector<int> minHeap;

    for (int i = 0; i < MAX_SZIE; i++) {
        int random = (601 * (i + 3)) % 271;
        heapInsert(minHeap, random);
    }

    for (int i = 0; i < MAX_SZIE; i++) {
         cout << heapRemove(minHeap) << " ";
    }
    cout << endl;

    return 0;
}

void heapInsert(vector<int>& arr, int val) {
    arr.push_back(val);
    int idx = arr.size() - 1;

    //heapify_up
    do {
        int parIdx = idx / 2;

        if (arr[parIdx] > arr[idx]) {
            swap(arr[parIdx], arr[idx]);
            idx = parIdx;
        }
        else {
            break;
        }

    } while (idx > 0);
}

int  heapRemove(vector<int>& arr) {
    int res = arr[0];
    swap(arr[0], arr[arr.size() - 1]);
    arr.pop_back();
    int idx = 0;
    
    //heapify_down
    do {
        int left = (idx * 2) + 1;
        int right = (idx * 2) + 2;

        if (right < arr.size()) {   // 자식 2개 존재
            int small = arr[left] < arr[right] ? left : right;  // 둘 중 더 작은 자식
            if (arr[small] < arr[idx]) {    // 작은 자식이 부모 보다 더 작은 경우
                swap(arr[small], arr[idx]);
            }
            idx = small;
        }
        else if (left < arr.size() && arr[left] < arr[idx]) {   //자식 1개 존재
            // 자식이 더작은 경우
            swap(arr[left], arr[idx]);
            idx = left;
        }
        else {  //자식이 없거나 자식 있어도 더 자식 값이 더 큰 경우
            break;
        }
    } while (idx < arr.size());

    return res;
}

분할정복을 이용한 정렬

• Merge Sort
• Quick Sort

Merge Sort

• pseudo algorithm

1. 정렬할 데이터 집합을 반으로 나눈다

2. 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1번 작업을 반복한다

3. 원래 같은 집합에서 나뉘어진 두 개의 하위 데이터 집합의 원소들을 크기 순서에 맞춰 정렬하고 병합.

4. 데이터 집합이 하나가 될 때까지 3번작업을 반복

• 시간복잡도
  • worst : O(nlogn)
  • average : O(nlogn)
  • best : O(nlogn)

• 예시 코드

// merge sort

#include <iostream>
#include <vector>
#define MAX_SIZE 9
using namespace std;

vector<int> arr(MAX_SIZE);
vector<int> sortedArr(MAX_SIZE);
void mergeSort(vector<int>& arr, int left, int right);
void merge(vector<int>& arr, int left, int mid, int right);

int main() {

    for (int i = 0; i < arr.size(); i++) 
        arr[i] = (601 * (i + 3)) % 271;
    cout << "before sorting : ";
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";

    mergeSort(arr, 0, (MAX_SIZE-1));

    cout << endl << "after sorting : ";
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";

    return 0;
}

//divide
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) { // 원소 최소 2개 이상
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

//conquer
void merge(vector<int>& arr, int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int k = left;

    // 정렬
    while (i<=mid && j<=right){
        if (arr[i] < arr[j])
            sortedArr[k++] = arr[i++];
        else
            sortedArr[k++] = arr[j++];
    }

    // 남은 부분 복사 : 왼쪽이 남은경우
    while (i <= mid) {
        sortedArr[k++] = arr[i++];
    }

    // 남은 부분 복사 : 오른쪽이 남은 경우
    while (j <= right) {
        sortedArr[k++] = arr[j++];
    }

    // 정렬된 결과를 원래 배열로 복사
    for (int l = left; l <= right; l++) {
        arr[l] = sortedArr[l];
    }
}

Quick Sort

• 분할 정복 알고리즘을 이용한 매우 빠른 수행 속도를 자랑하는 정렬
• 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.
• psuedocode

1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽, 피벗보다 큰 요소들은 피벗의 오른쪽으로 나눈다 
3.  피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
   • 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
   • 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다. 리스트의 크기가 0이나 1이 될 때까지 반복한다.

• 시간복잡도
  • worst : O(n^2)
  • average : O(nlogn)
  • best : O(nlogn)
• 예시코드

// quick sort

#include <iostream>
#include <vector>
#define MAX_SIZE 9
using namespace std;

vector<int> arr(MAX_SIZE);
void quickSort(vector<int>& arr, int start, int end);
int partition(vector<int>& arr, int start, int end);

int main() {

    for (int i = 0; i < arr.size(); i++)
        arr[i] = (601 * (i + 3)) % 271;
    cout << "before sorting : ";
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";  // 177 236 24 83 142 201 260 48 107

    quickSort(arr, 0, (MAX_SIZE - 1));

    cout << endl << "after sorting : ";
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i] << " ";  // 24 48 83 107 142 177 201 236 260 

    return 0;
}

void quickSort(vector<int>& arr, int start, int end) {
    if (start < end) {
        int idx = partition(arr, start, end);
        quickSort(arr, start, idx - 1);
        quickSort(arr, idx + 1, end);
    }
    else
        return;
}

int partition(vector<int>& arr, int start, int end) {
    int pivot = arr[end];   // 정렬의 기준 : 정렬할 구간의 맨 오른쪽 원소 선택
    int idx=start;          // 피봇값을 정렬할 구간을 둘로 나누는 위치값
    int temp;              

    for (int i = start; i < end; i++) {
        if (arr[i] <= pivot) {
            temp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = temp;
            idx++;
        }
    }

    temp = arr[idx];
    arr[idx] = arr[end];   
    arr[end] = temp;
    
    // idx 기준으로 idx 보다 작은 인덱스는 모두 arr[idx]값 보다 작은원소들
    // idx 보다 큰 인덱스는 모두 arr[idx] 값 보다 크다.
    return idx; 
}