bingu일기

일반적으로 하나의 Process는 하나의 Thread를 가지고 작업을 수행한다.
하지만, Multi Thread란 하나의 Process에서 다중의 Thread가 동시에 작업을 수행하는 것을 의미한다.
또한, Multi Process는 여러 개의 CPU를 사용하여 다중의 Process를 동시에 작업을 수행하는 것을 의미한다.

Multi Thread, Multi Process 모두 동시에 어떤 작업을 한다는 점이다.
여기서 둘의 차이는 독립적인 메모리 공간을 갖고 있느냐의 차이이다.
Multi Process는 각자 독립적인 메모리 공간을 갖지만, Multi Thread는 Thread가 상위 Process의 메모리 공간을 공유하여 사용한다.(Stack 메모리 공간은 예외)

이처럼 Multi Thread는 메모리 공간의 낭비가 적고 다수의 작업을 동시에 진행할 수 있다는 장점이 있다.

Context Switching

컴퓨터가 동시에 처리할 수 있는 최대 작업수는 CPU코어의 수와 같다.
그럼 CPU코어 보다 더 많은 Thread를 사용하게 되면 정해진 순서대로 작업을 번갈아가며 수행한다.

이렇게 각각의 Thread가 교체될 때, Thread 간의 Context Switching이라는 것이 발생한다.
현재 Thread의 작업을 하는 중에 다른 Thread의 작업을 하려면 현재 Thread의 작업을 저장하고, 다음 Thread를 불러오는 과정을 말한다.

이런 과정으로 알 수 있는 점은 무조건 Thread가 많다고 좋은 것이 아니라는 것이다.
저장과 불러오기의 과정에서 걸리는 시간이 커지게 되면 효율이 저하될 수밖에 없기 때문이다.

C#의 Thread Pool

사전에 일정 개수의 Thread를 만들어 놓고 작업 요청하게 되면, 사용가능한 Thread를 할당하여 수행하게 된다.
즉, 작업 요청 시에 Thread를 매번 만드는 것이 아니라 대기 중인 Thread를 불러서 작업을 요청하는 것이다.

그러면, Thread Pool의 최대 개수를 넘어선 작업을 요청하게 되면 작업은 점점 쌓이게 된다는 문제가 있다.
또한, Thread가 무한루프를 돌아도 문제가 생긴다.

이야기 예시

사장(CPU)과 알바관리 매니저(Process), 알바(Thread)가 하나의 가게를 맡았다고 하자. 끔찍하네

사장은 매니저에게 이것저것 시키게 된다.
매니저는 사장에게 들은 일거리를 알바에게 시킨다.
근데 알바는 일의 순서대로 차근차근 일을 하지만 몸이 하나기에 한 번에 여러 가지 일을 할 수 없다.
그렇기에 알바가 일을 해도 일이 끊임없이 쌓이게 된다.

매니저는 일이 너무 많이 쌓여서 효율이 없다고 판단하게 되어 알바를 여러 명 쓰게 된다.
근데 하루는 일이 평소보다 많이 안 들어와 놀고 있는 알바가 보이게 된다.
어떤 날은 일이 많고 어떤 날은 일이 많지 않다.
그래서 매니저는 알바들을 합숙시키게 된다.(Thread Pool)
이렇게 일이 밀릴 때마다 한 명씩 내려와 일을 시키는 양상이 돼버린 것이다.

이렇게 사람으로 생각하면 끔찍하지만 하나의 부품들로 생각하면 편하고 효율적인 것이다.

개념 요약

• 한가지 문제를 한번만 풀도록 만드는 알고리즘이다.
• 문제를 여러번 풀어 반복하지 않도록 하여 실행시간을 줄여준다.
• 규칙에 대한 점화식을 도출하여 푸는 방법이다.
• Memoization : 한 번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복 계산을 줄이는 것.

Ex. 피보나치 수열

TOP-DOWN

int	fiboData[100] = {0, };

int	fibo(int n)
{
	if (n <= 2)
		return (1);
	if (fiboData[n] == 0)
		fiboData[n] = fibo(n - 1) + fibo(n - 2);
	return (fiboData[n]);
}

BOTTOM-UP

int	fiboData[100] = {0, };

int	fibo(int n)
{
	fiboData[0] = 0;
	fiboData[1] = 1;
	for (int i = 2; i <= n; ++i)
		fiboData[i] = fiboData[i - 1] + fiboData[i - 2];
	return (fiboData[n]);
}

개념요약

• 트리상에서 임의의 두 정점이 있을때 두 정점의 부모노드를 타고 갔을때, 겹치면서 가장 깊은 노드이다.
• 푸른색이 두 정점, 붉은색이 LCA이다.

풀이 방식

1. 모든 노드에 대한 깊이를 계산한다.
2. 최소 공통 조상을 찾을 두 노드를 확인한다.
3. 두 노드의 깊이가 동일할 때까지 거슬러 올라간다.
4. 부모가 같아질 때까지 두 노드의 부모로 거슬러 올라간다.

코드

Node	&LCA(Node lhs, Node rhs)
{
	while(true)
	{
		if (lhs.depth == rhs.depth)
		{
			if (lhs.parent == rhs.parent)
				return (lhs.parent);
			else
			{
				lhs = lhs.parent;
				rhs = rhs.parent;
			}
		}
		else if (lhs.depth > rhs.depth)
			lhs = lhs.parent;
        else if (lhs.depth < rhs.depth)
			rhs = rhs.parent;
	}
}

개념 요약

• 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 배열의 길이가 최대인 부분 수열이다.
• 간편한 풀이법은 DP를 이용하는 것이다.(시간 복잡도 : $O(n^2)$)
• 이분 탐색을 이용한 방법도 가능하다.(시간 복잡도 : $O(nlogn)$)

코드

// DP
void	LIS_DP(vector<int> &arr)
{
	// dp[i] : dp의 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이
	for (int i = 1; i < dp.size(); ++i)
	{
		// 해당 원소 초기화
		dp[i] = 1;
		// 처음부터 끝까지 루프
		for (int i j = 0; j < dp.size(); ++j)
		// 큰 값을 dp[i]에 넣는다.
			dp[i] = max(dp[i], dp[j] + 1);
    }
}

// 이분 탐색
int	binary_search(vector<int> lis, int start, int end, int element)
{
	while (start < end)
	{
		int mid = (start + end) / 2;
		if (element > lis[mid])
			start = mid + 1;
		else
			end = mid;
	}
	return (end);
}

int	LIS_BS(vector<int> &arr)
{
	int	ret = 0;
	vector<int>	list;
	list.push_back(arr[0]);
	for (int i = 1; i < n; ++i)
	{
		if (arr[i] > lis.back())
		{
			lis.push_back(arr[i]);
			ret = lis.size() - 1;
		}
		int pos = binary_search(lis, 0, ret, arr[i]);
		lis[pos] = arr[i];
	}
	return (ret + 1);
}

DFS(깊이 우선 탐색)

개념 요약

• 그래프 알고리즘으로 루트 노드 혹은 임의의 노드에서 다음 분기로 넘어가기 전에 해당 분기를 모두 탐색하는 방법이다.
• 스택, 재귀 함수를 통해 구현할 수 있다.
• 모든 경로를 방문해야 할 경우 사용하기에 적합하다.
• 한 방향으로 갈 수 있을 때까지 계속 전진하며 전진할 수 없을 때, 가장 가까운 갈림길로 돌아와서 다시 한 방향으로 전진한다.
• 방문했는지의 여부를 판단해야 한다.

코드

// 재귀
void	dfs(Node &root)
{
	// 해당 노드가 끝에 도달
	if (root == nullptr)
		return ;
	else
	{
		// 해당 노드의 방문 여부 재설정
		root.visited = true;
		// 해당 노드와 연결된 노드로 재귀
		for (Node &connected_node : root.connect_node)
		{
			// 해당 노드의 방문 여부 확인
			if (connected_node.visited == false)
				dfs(connected_node);
		}
	}
}

--------------------------------------------------------------
// 스택
void	dfs(Node &root)
{
	// 스택 생성
	stack<Node>	store;
	// 스택 초기값 설정
	store.push(root);
	// 스택이 빌때까지 루프
	while (store.empty() == false)
	{
		// 스택의 가장 위의 노드를 현재 노드로 설정
		Node	&curr_node(store.top());
		// 현재 노드의 방문 여부 재설정
		curr_node.visited = true;
		// 스택의 가장 위 pop
		store.pop();
		// 현재 노드와 연결된 노드 스택에 push
		for (Node &connected_node : curr_node.connect_node)
		{
			// 해당 노드의 방문 여부 확인
			if (connected_node.visited == false)
				store.push(connected_node);
		}
	}
}

장단점

• 목표 노드가 깊은 곳에 있는 경우 해를 빨리 구할 수 있지만, 그렇지 않다면 더욱 느리게 탐색된다.

BFS(넓이 우선 탐색)

개념 요약

• 루트 노드 또는 임의의 노드에서 인접한 노드부터 먼저 탐색하는 방법이다.
• 큐를 통해 구현한다.
• 최소 비용에 적합하다.

코드

void	bfs(Node &root)
{
	// 큐 생성
	queue<Node>	store;
	// 초깃값 push
	store.push(root);
	// 큐가 빌때까지 루프
	while (store.empty() == false)
	{
		// 큐에 저장된 가장 앞 노드를 현재 노드로 지정
		Node	&curr_node = store.front();
		// 현재 노드의 방문여부 재설정
		curr_node.visited = true;
		// 큐의 저장된 가장 앞 노드 pop
		store.pop();
		// 현재 노드와 인접한 노드 큐에 push
		for (Node &connected_node : curr_node.connect_node)
		{
			// 해당 노드의 방문여부 확인 후 큐에 push
			if (connected_node.visited == false)
				store.push(connected_node);
		}
	}
}

장단점

• 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
• 노드의 수가 늘어나면 탐색해야 하는 노드도 많아지기 때문에 비현실적이다.

개념

해시 테이블은 Key와 Value로 쌍을 이뤄 데이터를 저장하는 자료구조이다.

해시 테이블은 각각의 Key값에 해시함수(Hash Function)를 수행하여 고유한 인덱스를 생성시키며, 해당 인덱스를 활용하여 값을 저장, 검색하게 된다. 이때, 실제 값이 저장되는 장소를 버킷(bucket) 또는 슬롯(slot)이라 한다.

이런 구조로 데이터를 저장할 때, Key값을 해시함수를 수행하여 저장했다. 그렇다면 조회, 삭제할 때도 Key값에 대한 해시함수를 수행하면 된다.

해시 함수는 특정 입력 데이터에서 고정 길이 값을 생성하는 알고리즘이다. 해시 함수를 통해 나온 결과물은 원본으로 변환하지 못한다.
또한, 특정 입력값에는 특정 출력 값을 산출하지만 작은 변화만 줘도 극단적인 출력 값의 변화가 생긴다. 이를 눈사태 효과라 한다.

해시 함수는 원칙적으로는 동일 출력 값이 나오면 안 되지만 다른 입력값에 드물게 동일한 출력 값이 나오는 경우가 있는데 이런 경우를 해시 충돌이라 한다.

해시 충돌이 발생하는 경우

• 분리 연결법(Separate Chaining)
  • 동일한 버킷에 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다.
    이러한 방식은 해시 테이블의 확장이 필요 없고 간단하게 구현 가능하며 손쉽게 삭제할 수 있다는 장점이 있다.
    그러나 데이터의 수가 많아지면 동일한 버킷에 Chaning 되는 데이터가 많아지면서 캐시의 효율성이 감소한다는 단점이 있다.
• 개방 주소법(Open Addressing)
  • 해시 테이블의 공간을 활용하는 방법인데 이 방법에는 3가지 방법이 존재한다.
    1. Linear Probing
       현재 버킷 인덱스로부터 고정된 폭만큼 이동하여 차례대로 검색하여 비어있는 버킷에 데이터를 저장한다.
    2. Quadratic Probing
       해시의 충돌한 수를 제곱으로 저장하는 방식이다.
       예를 들면 처음 충돌한 경우 $1^2$만큼 이동하고 그다음 충돌하면 $2^2$칸, $3^2$칸씩 옮기는 방식이다.
    3. Double Hashing Probing
       해싱된 값을 한번 더 해싱하는 방식인데, 이는 해시함수를 두 번 수행하기 때문에 많은 연산을 하게 된다.

시간 복잡도

각각의 Key값은 해시함수를 수행하여 고유한 인덱스를 갖게 되어 바로 접근할 수 있기 때문에 평균 $O(1)$의 시간 복잡도를 갖는다.
하지만, 해시 충돌이 발생할 경우 $O(n)$까지 시간 복잡도가 증가할 수 있다.

장단점

• 적은 리소스로 많은 데이터를 효율적으로 관리할 수 있다.
• 교유한 인덱스를 사용하여 검색, 삽입, 삭제가 빠르다.
• 중복을 제거하는데 유용하다.
• 충돌이 발생할 경우가 곧 단점이다.
• 공간 복잡도가 커지며 해시함수 의존도가 높아진다.

개념 요약

• 주어진 벡터에서 주어진 값을 찾는 방법
• 정렬이 되어있는 벡터에서 중간값을 기준으로 벡터를 나눠서 찾는다.
• 탐색 범위가 절반씩 줄기 때문에 효율적이다.

진행 순서

1. 주어진 벡터의 중간값을 뽑는다.
2. 중간값보다 크다면 중간값을 최솟값으로, 작다면 최댓값으로 설정하고 재귀를 시행.
3. 찾았다면 인덱스 반환

코드

int	binary_search(const std::vector<int> &vec, const int &num, const int start, const int last)
{
	// 처음 인덱스보다 마지막인덱스보다 크다면 없음
	if (start > last)
		return (-1);
	// 중간값 인덱스 저장
	int	mid = (start + last) / 2;
	// 중간값이 주어진 숫자와 같다면 인덱스 리턴
	if (vec[mid] == num)
		return (mid);
	// 중간값이 주어진 숫자보다 크다면 시작 인덱스 조정
	else if (vec[mid] < num)
		return (binary_search(vec, num, mid + 1, last));
	// 중간값이 주어진 숫자보다 작다면 마지막 인덱스 조정
	else
		return (binary_search(vec, num, start, mid - 1));
}

시간 복잡도

• $O(log_2 n)$

장단점

• 주어진 벡터가 정렬되어있을 때만 사용 가능하다.
• 비교 범위를 반으로 잘라가면서 하기 때문에 효율적이다.

개념 요약

• 벡터 내의 원소는 양수만 가능하며 값의 범위가 너무 크지 않아야 한다.
• 해당 벡터에 각 숫자가 몇 개가 나오는지 세서 차례대로 다시 저장한다.

정렬 과정

1. 주어진 벡터 내의 원소의 개수를 센다.
2. 차례대로 다시 벡터에 넣는다.

코드

void	counting_sort(std::vector<int> &unsorted_array)
{
	int	max_num = 0;
	// 원소중 최댓값을 뽑는다.
	for (auto &elem : unsorted_array)
		if (max_num < elem)
			max_num = elem;
	// 최댓값만큼의 공간을 가진 벡터 생성
	std::vector<int>	counting(max_num + 1, 0);
	// 원소의 해당하는 인덱스의 값을 증가
	for (auto &elem : unsorted_array)
		++counting[elem];
	// 원래 배열 초기화
	unsorted_array.clear();
	// 인덱스를 확인하면서 차례대로 원래 배열에 push
	for (int idx = 0; idx < max_num + 1; ++idx)
	{
		while ((counting[idx]--) != 0)
			unsorted_array.push_back(idx);
	}
}

시간 복잡도

• $O(n + k)$
  • k는 주어진 벡터 내 원소의 최댓값

공간 복잡도

• $O(k)$
  • k는 주어진 벡터 내 원소의 최댓값

장단점

• 시간 복잡도가 O(n)이다.
• 벡터 내의 원소의 최댓값만큼의 벡터를 생성해야 한다.

개념 요약

• 비교 없이 수행하는 정렬 알고리즘이다.
• 기수로는 정수, 낱말 등 다양한 자료로 사용 가능하지만 크기가 유한하며 사전 순으로 정렬할 수 있어야 한다.
• 기수에 따라 원소를 버킷에 집어넣기 때문에 비교 연산이 없다.
• 정수 같은 자료의 정렬 속도가 매우 빠르지만, 데이터 전체 크기에 기수 테이블의 크기만 한 메모리가 필요하다.
• 부동소수점 실수처럼 특수한 비교 연산이 필요한 경우엔 사용하지 못한다.
• MSD(최상위 유효숫자)와 LSD(최하위 유효숫자) 방식이 있다.
• MSD
  • 문자열이나 고정 길이 정수 표현 정렬에 전합니다.
  • 가장 큰 자릿수부터 정렬을 진행한다.
  • 중간에 정렬이 완료될 수 있다는 장점이 있지만 추가 작업이 필요하다.
• LSD
  • 가장 작은 자릿수부터 정렬을 진행한다.
  • MSD에 비해 간결하다.

정렬 과정

정수를 예로 과정 설명을 진행한다.

1. 특정 자릿수가 정렬된 결과를 넣을 큐 A(0~9), 정렬된 결과를 넣을 임시 큐 B(0~9)을 선언한다.
2. 원소를 차례대로 꺼내서 i번째 자리를 정렬하여 A에 넣는다.
3. A에서 원소를 차례대로 꺼내서 i번째 자리를 정렬하여 B에 넣는다.( i = 1, i < 최대 자릿수)
4. B에서 원소를 차례대로 꺼내서 A에 넣는다.
5. 3~4를 반복한다.
6. B에서 차례대로 원소를 꺼내서 원래 벡터에 초기화시킨다.

코드

int	get_digit_num(int num, int i)
{
	int	d = std::pow(10, i);
	return ((num / d) % 10);
}

int	get_max_count(int max_elem)
{
	int	count = 0;
	while (max_elem)
	{
		max_elem /= 10;
		++count;
	}
	return (count);
}

void	radix_sort(std::vector<int> &unsorted_array)
{
	std::vector<std::queue<int>>	A(10);
	int	max_elem = unsorted_array[0];

	// 최댓값 구하기, 1의 자리 정렬해서 A에 넣기
	for (int &elem : unsorted_array)
	{
		max_elem = (max_elem < elem ? elem : max_elem);
		A[elem % 10].push(elem);
	}
	// 원래 벡터 초기화
	unsorted_array.clear();
	int	temp = max_elem, count = get_max_count(max_elem);
	// 1(10의 자리)부터 시작해서 최대 자릿수까지 진행
	for (int idx = 1; idx < count; ++idx)
	{
		// 임시로 저장할 queue 생성
		std::vector<std::queue<int>>	B(10);
		// 0~9까지 해당하는 큐 불러오기
		for (int i = 0; i < 10; ++i)
		{
			// 해당 인덱스의 큐가 빌때까지 루프
			while (A[i].empty() == false)
			{
				// 가장 앞의 원소를 자릿수 구분하여 넣어주기
				int	num = A[i].front();
				B[get_digit_num(num, idx)].push(num);
				A[i].pop();
			}
		}
		// 기존 queue 초기화
		A.clear();
		// B를 그대로 A로 옮김
		for (int i = 0; i < 10; ++i)
			A.push_back(B[i]);
	}
	// 정렬이 완료된 큐벡터를 기존 벡터의 주소에 push
	for (int idx = 0; idx < 10; ++idx)
	{
		while (A[idx].empty() == false)
		{
			unsorted_array.push_back(A[idx].front());
			A[idx].pop();
		}
	}
}

시간 복잡도

• $O(d * n)$
  • d는 정렬한 자릿수

장단점

• 문자열, 정수 정렬 가능하다.
• 자릿수가 없는 것은 정렬할 수 없고 중간결과를 저장할 메모리 공간이 필요하다.

개념 요약

• 완전 이진트리를 기본으로 하는 힙을 기반으로 한 정렬 방식
• 힙(Heap)
  • 완전 이진트리의 일종으로 최댓값과 최솟값을 쉽게 추출할 수 있는 자료 구조
• 내림차순을 위함은 최대 힙, 오름차순을 위함은 최소 힙을 이용한다.

정렬 과정

1. 절렬하기 위한 n개의 요소들로 최대 힙을 만든다.
2. 루트에 최댓값이 있기 때문에 힙의 가장 마지막과 교체한다.
3. 교체한 원소를 제외하고 다시 최대 힙을 만든다.
4. 2번 3번의 연속.

코드

void	swap(std::vector<int> &heap, int a, int b)
{
	int	temp = heap[a];
	heap[a] = heap[b];
	heap[b] = temp;
}

void	heapify(std::vector<int> &heap, int n, int i)
{
	// 부모, 왼쪽, 오른쪽 순으로 저장
	int	parent = i, l_c = i * 2 + 1, r_c = i * 2 + 2;
	// 왼쪽 자식과 비교해서 인덱스 교환
	if (l_c < n && heap[parent] < heap[l_c])
		parent = l_c;
	// 오른쪽 자식과 비교해서 인덱스 교환
	if (r_c < n && heap[parent] < heap[r_c])
		parent = r_c;
	// 무언가 변환이 되었다면 교환후 재귀과정
	if (i != parent)
	{
		swap(heap, parent, i);
		heapify(heap, n, parent);
	}
}

void	heap_sort(std::vector<int> &unsorted_array)
{
	int	n = unsorted_array.size();
	// 트리에 넣기.
	for (int i = n / 2 - 1; i <= 0; --i)
		heapify(unsorted_array, n, i);
	// 최댓값을 뒤로 빼는 작업
	for (int i = n - 1; i > 0; --i)
	{
		swap(unsorted_array, 0, i);
		heapify(unsorted_array, i, 0);
	}
}

시간 복잡도

• 평균, 최선, 최악의 경우 $O(nlogn)$

공간 복잡도

• 추가적 메모리 사용이 없기 때문에 $(On)$

장단점

• 효율적이며 가장 큰 값, 작은 값을 구하기에 용이하다.
• 같은 데이터 상태에 같은 시간 복잡도를 가진 정렬 방식보다 조금 느리다.