yongmin

• 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; 
}

• selection sort
• insertion sort
• bubble sort

Selection Sort

• 제자리 정렬(in-place sorting) 알고리즘의 하나
  • 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
• 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
  • 첫 번째 순서에는 첫 번째 위치에 가장 최솟값을 넣는다.
  • 두 번째 순서에는 두 번째 위치에 남은 값 중에서의 최솟값을 넣는다.
• 과정 설명
  1. 주어진 배열 중에서 최솟값을 찾는다.
  2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
  3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
  4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.
• time complexity
  • worst : O(n^2)
  • average : O(n^2)
  • best : O(n^2)

//selection sort

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

void selectionSort(vector<int>& arr);

int main() {

  vector<int> arr;
  arr.push_back(9);
  arr.push_back(6);
  arr.push_back(7);
  arr.push_back(3);
  arr.push_back(5);

  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 9 6 7 3 5
  }

  selectionSort(arr);
  cout << endl;
  
  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 3 5 6 7 9
  }
}

void selectionSort(vector<int>& arr){
  int min, minIdx, swap ;

  for(int i=0; i<arr.size(); i++){
    min = arr[i];

    for(int j=i+1; j<arr.size(); j++){
      if(min > arr[j]){
         min = arr[j];    
         minIdx = j;
      }
    }
    
    swap = arr[i];
    arr[i] = arr[minIdx];
    arr[minIdx] = swap;
  }
}

Insertion Sort

• 정의
  • 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 과정 설명
  • 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬
  • 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.
  • 처음 Key 값은 두 번째 자료부터 시작한다.
• time complexity
  • worst : O(n^2)
  • average : O(n^2)
  • best : O(n)

//insertion sort

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

void insertionSort(vector<int>& arr);

int main() {

  vector<int> arr;
  arr.push_back(9);
  arr.push_back(6);
  arr.push_back(7);
  arr.push_back(3);
  arr.push_back(5);

  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 9 6 7 3 5
  }

  insertionSort(arr);
  cout << endl;
  
  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 3 5 6 7 9
  }
}

void insertionSort(vector<int>& arr){
  int key, i , val;
  for(i=1; i<arr.size(); i++){
    key = i-1;
    while(key >= 0 && arr[key] > arr[i]){
      key--;
    }
    val = arr[i];
    arr.erase(arr.begin()+i);
    arr.insert(arr.begin()+key+1, val);
  }
}

Bubble Sort

• 정의
  • 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 과정 설명
  • 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1) 번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.
  • 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
• time complexity
  • worst : O(n^2)
  • average : O(n^2)
  • best : O(n)

//bubble sort


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

void bubbleSort(vector<int>& arr);

int main() {

  vector<int> arr;
  arr.push_back(9);
  arr.push_back(6);
  arr.push_back(7);
  arr.push_back(3);
  arr.push_back(5);

  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 9 6 7 3 5
  }

  bubbleSort(arr);
  cout << endl;
  
  for(int n=0; n<arr.size(); n++){
    cout << arr[n] << " "; // 3 5 6 7 9
  }
}

void bubbleSort(vector<int>& arr){
  for(int i=arr.size(); i>=1; i--){
    for(int j=0; j<i-1; j++){
      if(arr[j+1] < arr[j]){
        int swap = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = swap;
      }
    }
  }
}

0. 작업환경설정

1. UI 구성

2. 프레젠테이셔널 컴포넌트 생성

3. 리덕스 생성

4. 리액트 앱에 리덕스 적용

5. 컨테이너 컴포넌트 생성

6. redux-actions라이브러리 적용

0. 작업환경설정

$ yarn create react-app react-redux-tutorial
$ cd react-redux-tutorial
$ yarn add redux react-redux
// redux 라이브러리 : createStore함수를 사용하여 스토어생성
// react-redux 라이브러리 : connect함수와 Provider컴포넌트를 사용하여 리액트에서 리덕스 관련작업 처리

1. UI 구성

• 프레젠테이셔널 컴포넌트 : 상태관리가 이루어지지 않고, 그저 props를 받아 와서 화면에 UI를 보여 주기만 하는 컴포넌트
• 컨테이너 컴포넌트 : 리덕스와 연동되어 있는 컴포넌트. 리덕스로 부터 상태를 받아오기도 하고 리덕스 스토어에 액션을 디스패치 함.

2. 프레젠테이셔널 컴포넌트 생성

// src/components/Todos.js

import React from 'react';

const TodoItem = ({ todo, onToggle, onRemove }) => {
  return (
    <div>
      <input type="checkbox" />
      <span>text</span>
      <button>remove</button>
    </div>
  );
};

const Todos = ({
  input,
  todos,
  onChangeInput,
  onInsert,
  onToggle,
  onRemove,
}) => {
  const onSubmit = e => {
    e.preventDefault();
  };

  return (
    <>
      <form onSubmit={onSubmit}>
        <input />
        <button type="submit">register</button>
      </form>
      <div>
        <TodoItem />
        <TodoItem />
        <TodoItem />
        <TodoItem />
      </div>
    </>
  );
};

export default Todos;

// src/App.js

import React from 'react';
import Todos from './components/Todos';
import './App.css';

function App() {
  return (
    <div>
      <Todos />
    </div>
  );
}

export default App;

3. 리덕스 생성

• 일반적인 디렉토리 구조 : actions, constatns, reducers 3개의 디렉토리를 만들고 그안에 기능별로 파일을 하나씩 만든다
• Ducks패턴 : 액션타입, 액션생성함수, 리듀서 모두를 '모듈'이라는 하나의 파일에 몰아서 작성하는 방식

// 모듈 생성
// src/modules/Todos.js : Ducks패턴

//action type
const CHANGE_INPUT = 'todos/CHANGE_INPUT';
const INSERT = 'todos/INSERT';
const TOGGLE = 'todos/TOGGLE';
const REMOVE = 'todos/REMOVE';

//action creator
export const changeInput = input => ({
  type: CHANGE_INPUT,
  input,
});

let id = 3; //insert가 호출될 때마다 1씩 증가
export const insert = text => ({
  type: INSERT,
  todo: {
    id: id++,
    text,
    done: false,
  },
});

export const toggle = id => ({
  type: TOGGLE,
  id,
});

export const remove = id => ({
  type: REMOVE,
  id,
});

// initial state
const initialState = {
  input: '',
  todos: [
    {
      id: 1,
      text: 'todo job 1',
      done: true,
    },
    {
      id: 2,
      text: 'todo job2',
      done: false,
    },
  ],
};

//reducer
function todos(state = initialState, action) {
  switch (action.type) {
    case CHANGE_INPUT:
      return {
        ...state,
        input: action.input,
      };
    case INSERT:
      return {
        ...state,
        todos: state.todos.concat(action.todo), //concat : 배열에 원소추가
      };
    case TOGGLE:
      return {
        ...state,
        todos: state.todos.map(todo =>
          todo.id === action.id ? { ...todo, done: !todo.done } : todo,
        ),
      };
    case REMOVE:
      return {
        ...state,
        todos: state.todos.filter(todo => todo.id !== action.id), // filter의 파라미터로 전달된 함수의 조건을 만족하는 요소들로만 구성된 새로운 배열 반환
      };
    default:
      return state;
  }
}

export default todos;

// 루트 리듀서 생성
// src/modules/index.js

import { combineReducers } from 'redux';
import Todos from './Todos';

// 스토어를 만들 때는 리듀서를 하나만 사용해야 하므로
// 리듀서가 여러개인 경우 combinereducers함수를 통해 하나로 묶는다.
const rootReducer = combineReducers({
  Todos,
});

export default rootReducer;

4. 리액트 앱에 리덕스 적용

// src/index.js

import React from 'react';
import ReactDOM from 'react-dom';
import './index.css';
import App from './App';
import * as serviceWorker from './serviceWorker';

import { createStore } from 'redux';
import rootReducer from './modules';
import { Provider } from 'react-redux';

const store = createStore(rootReducer);	// 스토어 생성

// Provider 컴포넌트로 리액트 프로젝트에 리덕스 적용
ReactDOM.render(
  <Provider store={store}>		
    <App />
  </Provider>,
  document.getElementById('root'),
);

// If you want your app to work offline and load faster, you can change
// unregister() to register() below. Note this comes with some pitfalls.
// Learn more about service workers: https://bit.ly/CRA-PWA
serviceWorker.unregister();

5. 컨테이너 컴포넌트 생성

• 컨테이너 컴포넌트와 리덕스를 연동하려면 react-redux에서 제공하는 connect함수를 사용
  => connect( mapStateToProps, mapDispatchToProps)(연동할컴포넌트)
  • mapStateToProps : 리덕스 스토어 안의 상태를 컴포넌트의 props로 넘겨주기 위한 함수. 현재 스토어 안의 state를 파라미터로 받는다
  • mapDispatchToProps : store의 내장함수 dispatch를 파라미터로 받아 이를 이용하여 액션생성함수를 컴포넌트의 props로 넘겨주기 위한 함수. 액션생성함수를 객체형태로 전달만 해도 connect 함수가 자동bindActionCreators 작업을 수행하므로 dispatch를 파라미터로 받지 않아도 된다.
  • mapStateToProps 와 mapDispatchToProps 에서 반환하는 객체 내부의 값들은 컴포넌트의 props로 전달된다.

// src/containers/TodosContainer.js

import React from 'react';
import { connect } from 'react-redux';
import { changeInput, insert, toggle, remove } from '../modules/Todos';
import Todos from '../components/Todos';

const TodosContainer = ({
  input,
  todos,
  changeInput,
  insert,
  toggle,
  remove,
}) => {
  return (
    <Todos
      input={input}
      todos={todos}
      onChangeInput={changeInput}
      onInsert={insert}
      onToggle={toggle}
      onRemove={remove}
    />
  );
};

const mapStateToProps = state => {
  return {
    input: state.todos.input,
    todos: state.todos.todos,
  };
};

// dispatch를 파라미터로 받지 않고, 액션생성함수를 객체형태로 전달만 해도
// connect 함수가 자동bindActionCreators 작업을 수행한다.
const mapDispatchToProps = {
  changeInput,
  insert,
  toggle,
  remove,
};

export default connect(mapStateToProps, mapDispatchToProps)(TodosContainer);

// src/App.js

import React from 'react';
import TodosContainer from './containers/TodosContainer';
import './App.css';

function App() {
  return (
    <div>
      <TodosContainer />
    </div>
  );
}

export default App;

// src/components/Todos.js

import React from 'react';

const TodoItem = ({ todo, onToggle, onRemove }) => {
  return (
    <div>
      <input
        type="checkbox"
        onClick={() => onToggle(todo.id)}
        checked={todo.done}
        readOnly={true}
      />
      <span style={{ textDecoration: todo.done ? 'line-through' : 'none' }}>
        {todo.text}
      </span>
      <button onClick={() => onRemove(todo.id)}>remove</button>
    </div>
  );
};

const Todos = ({
  input,
  todos,
  onChangeInput,
  onInsert,
  onToggle,
  onRemove,
}) => {
  const onSubmit = e => {
    e.preventDefault();
    onInsert(input);
    onChangeInput('');
  };
  const onChange = e => onChangeInput(e.target.value);
  return (
    <>
      <form onSubmit={onSubmit}>
        <input value={input} onChange={onChange} />
        <button type="submit">register</button>
      </form>
      <div>
        {todos.map(todo => (
          <TodoItem
            todo={todo}
            key={todo.id}
            onToggle={onToggle}
            onRemove={onRemove}
          />
        ))}
      </div>
    </>
  );
};

export default Todos;

6. redux-actions 라이브러리 적용

• 액션생성함수, 리듀서를 작성할 때 redux-actions 라이브러리 활용하여 리액트 앱에서 리덕스를 훨씬 편하게 사용할 수 있다.
• createAction : 매번 객체를 직접 만들어 줄 필요 없이 간단하게 액션 생성 함수 선언 가능
• handleAction : 첫 번째 파라미터에는 각 액션에 대한 업데이트 함수, 두 번째 파라미터에는 초기 상태 전달.

MVC vs Flux 

• MVC
  • 정의 : 애플리케이션 개발시 가장 많이 사용되는 디자인패턴으로, 컨트롤러(Controller)는 모델(Model)의 데이터를 조회하거나 업데이트하는 역할을 하며, 모델(Model)의 변화는 뷰(View)에 반영한다. 또한, 사용자는 뷰를 통해 데이터를 입력하는데 사용자의 입력​은 모델에 영향을 준다.
  • 문제점 : 페이스북과 같은 대규모 애플리케이션에서는 Model이나 Model과 관련한 View가 대량으로 시스템에 추가되면 복잡도가 폭발적으로 증가하는데, 이 같은 의존성과 순차적 업데이트는 종종 데이터의 흐름을 꼬이게 하여 예기치 못한 결과를 불러일으킨다.

• Flux
  • 정의 : MVC 패턴의 문제를 해결하기 위해 고안된 아키텍쳐
  • 단방향 데이터 흐름(unidirectional data flow) : Flux의 가장 큰 특징으로, 데이터의 흐름은 언제나 디스패처(Dispatcher)에서 스토어(Store)로, 스토어에서 ​뷰(View)로, 뷰에서 액션(Action)으로 다시 액션에서 디스패처로 흐른다.
  • 구성요소
    • dispatcher : Flux 애플리케이션의 모든 데이터 흐름을 관리하는 허브 역할. 
    • action : 액션생성자에의해 생성되고 상태 업데이트 할 때 참고해야 할 값을 가진 객체
    • store : 애플리케이션의 상태를 저장및 action객체를 수신하여 새로운 상태를 만들어서 반환

Redux

• 정의 : React에서 State를 좀더 효율적으로 관리하는데 사용하는 flux 패턴의 상태관리 라이브러리
• 기존에는 부모에서 자식의 자식의 자식까지 상태가 흘렀었는데, 리덕스를 사용하면 스토어를 사용하여 상태를 컴포넌트 구조의 바깥에 두어 스토어를 중간자로 두고 상태를 업데이트 하거나, 새로운 상태를 전달받음. 따라서, 여러 컴포넌트를 거쳐서 받아올 필요 없이(종속성 제거) 아무리 깊숙한 컴포넌트에 있다 하더라도 직속 부모에게서 받아오는 것 처럼 원하는 상태값을 골라서 props 를 편리하게 받아올 수 있음.
• 리덕스 구조
  • action : 상태변화를 일으킬 때 참조하는 객체
  • action creator : 액션객체를 생성하는 함수
  • reducer : 현재상태와 액션객체를 파라미터로 받아 새로운 상태를 반환하는 함수
  • store : 애플리케이션의 상태, 리듀서, 몇가지 함수들을 내장
  • dispatch : 스토어에 내장된 함수로 액션객체를 파라미터로 받아 액션객체를 스토어에게 전달한다. 이후, 스토어는 리듀서 함수를 실행.
  • subscribe : 스토어의 내장 함수. 파라미터로 리스너 함수를 전달하여 subscribe함수를 호출하면, 액션이 디스패치되어 상태가 업데이트될 때마다 리스너함수를 실행.
• 리덕스 라이프 사이클
  • event 발생 -> action creator 호출
  • action creator는 action(object) 생성
  • 생성된 action은 모든 middleware를 거쳐 모든 reducer들에게 전달
  • reducer는 action type에 따른 state반환
  • state는 app의 state에 덮어쓰이고 모든 container들에게 전달
  • 컴포넌트 리렌더링 
• 상태업데이트 예시

• 리덕스 규칙
  • 단일 스토어 : 하나의 애플리케이션에는 하나의 스토어만 존재
  • 읽기 전용 : 리덕스의 상태는 항상 읽기 전용
  • 리듀서는 의존성 없는 순수함수 : 리듀서 함수는 인전상태와 액션 객체를 파라미터로 받고 파라미터 외의 값에는 의존하지 않는 순수함수이다.

참고 : https://velopert.com/3528