알고리즘(코딩테스트)

정렬 및 탐색 알고리즘 정리

gbleem 2025. 3. 21. 17:20

1. 정렬 알고리즘

1 - 1. 버블정렬

  • 배열에서 두개의 원소 선택하고 비교 후, 왼쪽 원소가 오른쪽 원소보다 큰 경우 swap 한다.
  • 시간 복잡도는 O(N^2), 공간 복잡도는 O(1)
  • 만약 아래 코드에서 swap이 발생하지 않는 경우 break하는 코드를 넣으면, 정렬된 경우 시간 복잡도를 O(N)으로 줄일 수 있다.
더보기 
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec = { 4,6,2,9,1 };

	for (int i = 0; i < vec.size(); ++i)
	{
		for (int j = 0; j < vec.size() - i - 1; ++j)
		{
			if (vec[j] > vec[j + 1])
				swap(vec[j], vec[j + 1]);
		}
	}
	for (const auto v : vec)
		cout << v << " ";
}

 

1 - 2. 선택 정렬

  • 배열의 한가지 값을 선택하고, 자신을 제외한 나머지 값들과 비교하여 가장 작은 값을 자신과 swap하여 정렬하는 방식
  • 시간 복잡도는 O(N^2), 공간 복잡도 O(1)
더보기 
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec = { 4,6,2,9,1 };

	for (int i = 0; i < vec.size() - 1; ++i)
	{
		int idx = i;
		for (int j = i + 1; j < vec.size(); ++j)
		{
			if (vec[j] < vec[idx])
				idx = j;
		}
		
		swap(vec[i], vec[idx]);			
	}
	for (auto v : vec)
		cout << v << " ";	
}

 

1 - 3. 삽입 정렬

  • 현재 선택한 값(i)을 다음 값(i+1)과 비교해서
    • 다음 값이 작은 경우, 다음값(i+1)보다 인덱스가 작은 값(0 ~ i)들 중에서 자신 보다 작은 값 뒤로 삽입하고,
    • 다음 값이 큰 경우, 그대로 두고 다음 인덱스로 이동
  • 시간 복잡도는 평균 O(N^2) 이지만, 만약 모두 정렬된 경우 O(N), 공간 복잡도 O(1)
  • 예시) 4 6 2 9 1에서 i가 1인 경우
    • i가 가리키는 값은 6, i+1 이 가리키는 값은 2 이다. 
    • 2가 6보다 작으므로, 0 ~ i 까지 값과 비교
    • 6은 2보다 크기 때문에 swap
    • 4도 2보다 크기 때문에 swap
    • 결론적으로 2보다 작은 값은 없었으므로, 맨 앞으로 2가 이동한 것
더보기 
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec = { 4,6,2,9,1 };

	int value, j;
	for (int i = 1; i < vec.size(); i++) 
	{ 
		value = vec[i];
		for (j = i - 1; j >= 0; j--) 
		{
			if (vec[j] > value)
				swap(vec[j + 1], vec[j]);
			else
				break;
		}
	}
	for (auto v : vec)
		cout << v << " ";
}

 

1 - 4. 퀵 정렬

  • 피벗을 기준으로 피벗보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 나눠서 정렬하는 방식
  • 평균적으로 O(NlogN)의 시간 복잡도, 최악의 경우(이미 정렬된 경우) O(N^2)이 된다. 공간 복잡도는 재귀 호출 스택으로 인해 O(logN)
더보기 
#include <iostream>
#include <vector>
using namespace std;

int Partition(vector<int>& vec, int low, int high)
{
	//중간값 찾기
	int mid = (low + high) / 2;

	//중간값을 맨 값이랑 swap
	swap(vec[mid], vec[high]);

	//중간값을 pivot으로 설정
	int pivot = vec[high];

	//시작 인덱스 설정
	int idx = low - 1;

	for (int i = low; i < high; ++i)
	{
		//피벗보다 작은 값을 왼쪽으로 몰아버리기
		if (vec[i] < pivot)
		{
			idx++;
			swap(vec[i], vec[idx]);
		}
	}
	//피벗을 정렬한 값 중앙으로 옮겨주기
	swap(vec[idx + 1], vec[high]);

	//정렬한 vec의 피벗 위치 return
	return idx + 1;
}

void QuickSort(vector<int>& vec, int low, int high)
{
	if (low < high)
	{
		//피벗보다 작은 값을 왼쪽 큰 값을 오른쪽으로 바꿔주기
		int pos = Partition(vec, low, high);

		//피벗을 기준으로 재귀함수 시작
		QuickSort(vec, low, pos - 1);
		QuickSort(vec, pos + 1, high);
	}
}


int main()
{
	vector<int> vec = { 4, 6, 2, 9, 1 };

	int low = 0;
	int high = vec.size() - 1;

	QuickSort(vec, low, high);

	for (auto v : vec)
		cout << v << " ";
}

 

1 - 5. 병합 정렬

  • 배열을 반으로 나눠, 각각을 정렬한 후 다시 합치는 방식으로 동작
  • O(NlogN)의 시간 복잡도를 보장한다. 추가적인 배열이 필요하므로 공간 복잡도는 O(N)
더보기 
#include <iostream>
#include <vector>
using namespace std;

int answer[10]; //정렬된 배열 (size N)

//정렬되어 온 배열을 다시 합치는 과정
void Merge(vector<int>& vec, int left, int mid, int right)
{
	int i = left; //정렬된 왼쪽 배열 인덱스
	int j = mid + 1; // 정렬된 오른쪽 배열 인덱스
	int k = left; // 정렬된 전체 리스트 인덱스
	int l = 0;

	while (i <= mid && j <= right)
	{
		if (vec[i] <= vec[j])
			answer[k++] = vec[i++];
		else
			answer[k++] = vec[j++];
	}

	//남은 값 처리
	if (i > mid)
	{
		for (l = j; l <= right; ++l)
			answer[k++] = vec[l];
	}
	else
	{
		for (l = i; l <= mid; ++l)
			answer[k++] = vec[l];
	}

	//다시 기존 배열로 복사하기
	for (l = left; l <= right; ++l)
		vec[l] = answer[l];
}

void MergeSort(vector<int>& vec, int left, int right)
{
	int mid;

	if (left < right)
	{
		mid = (left + right) / 2;
		MergeSort(vec, left, mid);
		MergeSort(vec, mid + 1, right);
		Merge(vec, left, mid, right);
	}
}

int main()
{
	vector<int> vec = { 4,6,2,9,1 };
	MergeSort(vec, 0, vec.size() - 1);
	for (const auto& v : vec)
		cout << v << " ";
}

 

 

2. 탐색 알고리즘

2 - 1. 선형 탐색

  • 단순히 정렬되지 않은 배열을 앞에서부터 하나씩 순차적으로 체크하며 찾는 방법
  • 시간 복잡도는 O(N)

 

2 - 2. 이분 탐색

  •  정렬된 배열에서 절반씩 나눠 찾는 방식
  • 시간 복잡도 O(logN)
더보기 
#include <iostream>
#include <vector>
using namespace std;

int BinarySearch(const vector<int>& vec, int target)
{
	int left = 0;
	int right = vec.size() - 1;

	while (left <= right)
	{
		int mid = (left + right) / 2;

		//찾은 경우
		if (vec[mid] == target)
			return mid;
		else if (vec[mid] < target)
			left = mid + 1;
		else
			right = mid - 1;
	}
	return -1;
}

int main()
{
	vector<int> vec = { 1,3,5,7,9,10,14 };
	int target = 10;

	int targetIdx = BinarySearch(vec, target);

	cout << targetIdx;
}
  • 참고)
    • STL에 존재하는 binary_search 함수나 upper_bound, lower_bound를 사용할 수도 있다.
    • algorithm 헤더가 필요하다.
    • binary_search 함수를 통해 target 존재 여부를 파악할 수 있다.
    • upper_bound, lower_bound 함수를 통해 target의 위치를 파악할 수 있다.
//STL
cout << binary_search(vec.begin(), vec.end(), target) << "\n";     //true (1)
cout << lower_bound(vec.begin(), vec.end(), target) - vec.begin(); //5