bingu일기

개념 요약

• 한가지 문제를 한번만 풀도록 만드는 알고리즘이다.
• 문제를 여러번 풀어 반복하지 않도록 하여 실행시간을 줄여준다.
• 규칙에 대한 점화식을 도출하여 푸는 방법이다.
• 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)$

장단점

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

개념 요약

• 분할 정복을 통해 구현한다.
• 빠른 정렬로 분류되며 퀵 정렬같이 많이 언급된다.
• 정렬되지 않은 배열을 각각 하나의 원소만 포함하는 n개로 분할한다.(결국 원소 하나씩 분할)
• 분할했던 역순으로 정렬하면서 병합한다.

정렬 과정

1. 배열의 길이가 1이라면 정렬된 것으로 본다.
2. 가져온 배열을 이등분하여 분할한다.
3. 분할한 배열을 재귀적으로 다시 분할한다.
4. 위 과정에서 이등분한 배열을 다시 하나의 정렬된 배열로 합병한다.(임시 배열)
5. 임시 배열의 결과를 원래 배열에 복사한다.

코드

void	merge(std::vector<int> &unsorted_array, int left, int mid, int right)
{
	// 임시로 사용할 vector 정의
	std::vector<int>	left_array, right_array;
	for (int idx = left; idx < right + 1; ++idx)
	{
		if (idx < mid + 1)
			left_array.push_back(unsorted_array[idx]);
		else
			right_array.push_back(unsorted_array[idx]);
	}
	int	i = 0, j = 0, k = left;
	while (i < left_array.size() && j < right_array.size())
	{
		// 대소비교를 통해 원래 vector에 삽입
		if (left_array[i] < right_array[j])
			unsorted_array[k++] = left_array[i++];
		else
			unsorted_array[k++] = right_array[j++];
	}
	// 남은것들 삽입
	while (i < left_array.size())
		unsorted_array[k++] = left_array[i++];
	while (j < right_array.size())
		unsorted_array[k++] = right_array[j++];
}

void	merge_sort(std::vector<int> &unsorted_array, int left, int right)
{
	if (left < right)
	{
		// 증긴깂 결정
		int	mid = (right + left) / 2;
        // 분할
		merge_sort(unsorted_array, left, mid);
		merge_sort(unsorted_array, mid + 1, right);
		// 정복, 결합
		merge(unsorted_array, left, mid, right);
	}
}

시간 복잡도

• 평균, 최선, 최악 모두 $O(nlogn)$를 갖는다.

공간 복잡도

• $O(n)$

장단점

• 효율적이며 안정적인 정렬 방식이다.
• 연결 리스트로 저장 시 유리하다.
• 정복, 결합과정에서 임시 배열이 필요하다.