굳건하게

안녕하세요, 여행벌입니다.

오늘은 버블 정렬(bubble sort)에 대해서 포스팅해보겠습니다.

버블 정렬이란

'서로 인접한 두 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환 해나가는 정렬 방식'

EX)

바로 예시를 통해서 익혀보겠습니다.

[ 2 3 5 1 4 ] 5개의 숫자가 담긴 배열을 버블 정렬을 통해서 정렬해보도록 하겠습니다.

STEP 1]

앞에서부터 차례대로 인접한 두 원소를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환해나가겠습니다.

2 와 3은 정렬이 잘 되어있으므로 교환을 하지 않고 3과 5도 마찬가지이므로 넘어갑니다.

5와 1은 크기가 순서대로 되어 있지 않으므로 둘이 교환해주고 5와 4도 마찬가지로 교환해줍니다.

그 결과 가장 큰 값인 5가 제일 뒤로 가게 되고 5는 정렬이 완료됩니다.

STEP 2]

마찬가지로 동일한 작업을 반복합니다.

2와 3은 PASS , 3과 1은 정렬이 되어있지 않으므로 SWAP을 진행해주고 3과 4는 PASS 합니다.

Unsorted에서 가장 큰 값인 4가 제일 뒷부분으로 가면서 정렬이 완료됩니다.

STEP 3]

STEP 4]

최종적으로 4개의 값들이 정렬이 되면서 마지막 값도 자동으로 정렬이 됩니다.

선택 정렬과 반대로 가장 큰 값이 제일 뒤로 정렬되는 것을 확인할 수 있습니다.

코드 구현

코드는 다음과 같습니다.

void bubble_sort(int list[], int n) {
	int temp;
	for (int i = n - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			// 정렬되어있지않다면 SWAP 한다.
			if (list[j] > list[j + 1]) {
				temp = list[j];
				list[j] = list[j + 1];
				list[j + 1] = temp;
			}
		}
	}
}

복잡도 분석

N 개의 원소가 있다고 가정하고 버블 정렬의 복잡도를 분석해보겠습니다.

버블 정렬은 처음에 ( N - 1 ) 번의 비교 연산이 발생하고, 선택 정렬과 마찬가지로 정렬이 완성된 부분이 하나씩 늘어가며 비교 연산이 1회씩 감소합니다.

따라서, 총 ( N - 1 ) + ( N - 2 ) +  ⋯ + 1 번 비교 연산이 발생합니다.

등차수열의 합으로 O ( N ^ 2 ) 의 시간 복잡도를 가지는 것을 확인할 수 있습니다.

배열이 이미 정렬이 되어있더라도 항상 똑같은 비교 과정을 거치므로 최선, 평균, 최악의 경우에 대해서 시간 복잡도가 동일합니다.

안정 정렬

버블 정렬은 '안정 정렬' 입니다. 즉, 동일한 원소 간의 순서가 정렬 후 바뀌지 않습니다.

[ 5-1  2  1  5-2 ] 를 버블 정렬을 통해서 정렬해보겠습니다.

동일한 두 원소 5를 구분하기 위해 5-1 / 5-2 로 표현했습니다.

정렬 전 [ 5-1  2  1  5-2 ] →  정렬 후 [ 1  2  5-1  5-2 ] 

다음과 같이 버블 정렬은 안정 정렬인 것을 확인할 수 있습니다.

이상으로 버블 정렬 포스팅을 마치겠습니다.

안녕하세요, 여행벌입니다.

오늘은 선택 정렬(selection sort)에 대해서 포스팅해보겠습니다.

선택 정렬이란

'정렬되지 않은 데이터에서 가장 작은 값을 뽑아 가장 앞의 데이터와 교환 해나가는 정렬 방식' 입니다.

EX)

바로 예시를 통해서 익혀보겠습니다.

[ 2 8 6 1 5 3 4 7 ] 8개의 숫자가 담긴 배열을 선택 정렬을 이용해서 정렬해보겠습니다.

STEP 1]

아직까지는 정렬된 부분이 하나도 없기 때문에 전체 범위에서 가장 작은 값인 1을 찾을 수 있습니다.

정렬되지 않은 가장 앞부분은 '2' 이므로 '2' 와 '1'을 SWAP 하게 됩니다.

STEP 2]

이제 정렬된 부분은 [ 1 ] 정렬되지 않은 부분은 [ 8 6 2 5 3 4 7 ] 이 되고, 정렬되지 않은 부분에서 가장 작은 값인 2를 가장 앞 '8'과 SWAP 합니다.

STEP 3]

이 과정을 반복하면 다음과 같이 됩니다.

STEP 4]

STEP 5]

STEP 6]

STEP 7]

정렬되지 않은 배열에 원소가 하나만 남아있다면, 그 원소가 가장 큰 원소이므로 STEP 8 까지 진행하지 않고 정렬을 종료할 수 있습니다.

코드 구현

코드는 다음과 같습니다.

void SelectionSort(int arr[], int N) {
    int min, temp;
    for(int i = 0; i < N - 1; i++) {
        min = i; // min 에 unsorted 중 가장 작은 값을 저장한다.
        for(int j = i+1; j < N; j++) 
            if(arr[j] < arr[min]) min = j;
        
        // 가장 앞과 SWAP 해준다.
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

첫 번째 for 문의 i 는 정렬되지 않은 배열의 가장 앞을 가리킵니다.

두 번째 for 문은 이제 정렬되지 않은 배열에서 가장 작은 값을 찾는 역할을 합니다.

복잡도 분석

이제 N 개의 원소가 있다고 가정하고 선택 정렬의 복잡도를 분석해보겠습니다.

첫 번째 원소를 정렬하기 위해 N개의 모든 원소를 순회하며 가장 작은 값을 찾아야 합니다.

즉, N - 1 번의 비교 연산이 발생합니다.

두 번째 원소를 정렬하기 위해서는 ( N - 1 )개의 모든 원소를 순회하며 가장 작은 값을 찾아야 합니다.

즉, N - 2 번의 비교 연산이 발생합니다.

그다음은 ( N - 2 ) 개의 모든 원소를 순회하며 가장 작은 값을 찾아야 하고

이 과정을 반복하면 총 (N - 1) + ( N - 2 ) + ⋯ + 1 번 비교 연산이 발생합니다.

등차수열의 합으로 O ( N ^ 2 ) 의 시간 복잡도를 가지는 것을 확인할 수 있습니다.

배열이 이미 정렬이 되어있더라도 가장 작은 값을 찾기 위해 항상 똑같은 순회, 비교 과정을 거치므로

최선, 평균, 최악의 경우에 대해서 시간 복잡도가 동일하게 O ( N ^ 2 )이 됩니다.

불안정 정렬

선택 정렬은 다음과 같은 상황에서 동일한 원소의 위치가 뒤바뀌므로 불안정 정렬에 속합니다.

[ 5 5 1 ] 배열을 선택 정렬을 통해서 정렬해보겠습니다.

이때 동일한 원소 5가 존재하므로 5-1 / 5-2 로 구분해주겠습니다.

결과는 다음과 같습니다.

정렬 전 [ 5-1 5-2 1 ]  → 정렬 후 [ 1 5-2 5-1 ]

동일한 원소가 존재할 때, 동일한 원소 간의 순서가 선택 정렬을 진행한 후 바뀐 것을 확인할 수 있습니다.

따라서, 선택 정렬은 '불안정 정렬' 입니다.

이상으로 선택 정렬 포스팅을 마치겠습니다.

안녕하세요, 여행벌입니다.

오늘은 문자배열을 이용해 덧셈 연산을 구현하는 방법에 대해 포스팅하겠습니다.

int 형 , long long 형 범위 안에 있는 수들은 '+' 를 이용해 덧셈 연산을 진행해도 문제가 발생하지 않습니다.

하지만, 굉장히 큰 수(ex 212342351384273198237832984 ) 처럼 long long 형의 범위를 벗어난 수들을

평소처럼 '+'를 이용해 덧셈 연산을 진행한다면 오버플로우가 발생하게 됩니다.

따라서, 굉장히 큰 수에 대해서는 문자배열을 이용해서 덧셈을 진행해야 합니다.

문자배열을 이용하는 덧셈을 진행하기 위해 다음과 같은 STL 을 이용하겠습니다.

C++에서는 문자배열 string을 STL 에서 지원해주기 때문에 조금 더 간편하게 구현할 수 있습니다.

#include<iostream>
#include<string>
#include<algorithm>

[ 핵심알고리즘 ]

1) 문자배열(A,B) 2개를 뒤에서부터 더해가며 새로운 문자배열(result)에 저장한다.

2) 1)을 진행하면서 올림수(sum)를 계속 저장해 간다.

3) 문자배열 A,B를 모두 순회하고 올림수에 저장된 수가 없다면 result를 뒤집어주고 종료한다.

문자배열 A, B를 뒤에서부터(일의자리부터) 더해가며 새로운 문자배열 result에 결과를 저장해나가면

문자배열을 이용해 큰 수의 덧셈을 구현할 수 있습니다.

[ 예시 ]

A = "12345" 와 B = "666"을 더해보겠습니다.

STEP 1]

5와 6을 더하면 11이므로 올림수는 1, result에는 1을 추가한다. → sum = 1 result = "1" 을 저장한다.

STEP 2]

4와 6과 sum을 더하면 11이므로 올림수는 1, result에는 1을 추가한다. → sum = 1 result = "11"을 저장한다.

STEP 3]

3과 6과 sum을 더하면 10이므로 올림수는 1, result에는 0을 추가한다. → sum = 1 result = "110"을 저장한다.

STEP 4]

문자배열 B는 다 순회했으므로, 2와 sum을 더한다. 올림수는 0, result에는 3을 추가한다. → sum = 0 result = "1103"

STEP 5]

마찬가지로 1과 sum을 더한다. 올림수는 0, result에는 1을 추가한다. → sum = 0 result = "11031"

STEP 6]

문자배열 A, B를 모두 순회했고, 올림수도 0이므로 result를 뒤집으며 종료한다. → result = "13011"

[ 코드구현 ]

algorithm에서 지원해주는 reverse 함수를 이용하면 쉽게 문자배열을 뒤집을 수 있습니다.

string string_add(string a, string b) {
	int sum = 0;
	string result;
	while (!a.empty() || !b.empty() || sum) {
		if (!a.empty()) {
			sum += a.back() - '0';
			a.pop_back();
		}
		if (!b.empty()) {
			sum += b.back() - '0';
			b.pop_back();
		}
		result.push_back((sum % 10) + '0');
		sum /= 10;
	}
	reverse(result.begin(), result.end());
	return result;
}

안녕하세요, 트레블비입니다.

오늘은 빠르게 어떤 수의 N 제곱 구하기에 대해서 포스팅하겠습니다.

[O(N) 으로 구하기]

예를 들어, 2의 100 제곱을 구한다고 해봅시다. ( Int 형 범위는 고려하지 않겠습니다. )

2를 계속 100번 곱하면 간단하게 답을 얻을 수 있겠죠? 

int answer = 1;
for(int i = 0; i < 100; i++)
	answer = answer * 2;
//주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다. 

그렇다면, 2의 100,000,000,000(1000억) 제곱을 구한다고 한다면 2를 계속 곱해가는 방법으로 빠르게 풀 수 있을까요??

int answer 1;
for(int i = 0; i < 100000000000; i++)
	answer = answer * 2;
//주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다.

당연히 1000억 번의 연산이 필요하므로 시간이 엄청 오래 걸립니다.

어떤 수 A의 N제곱을 구해야 되는데 N이 굉장히 크다면,  위의 방법은 시간 복잡도가 O(N)으로 사용할 수 없습니다.

[O(logN) 으로 구하기]

똑같이 2의 100 제곱을 구한다고 해봅시다. ( Int 형 범위는 고려하지 않겠습니다. )

100은 64 + 32 + 4 로 표현할 수 있습니다. 즉, 100 = 1100100(2) 입니다.

당연히, 모든 수는 2진수로 표현이 가능합니다!

이 사실을 이용해 훨씬 더 빠르게 2의 100 제곱을 구해보겠습니다.

int answer = 1, A = 2, N = 100;
while(N){
  if (N & 1)
  	answer = answer * A;
  N = N / 2;
  A = A * A;
}
//주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다.

A = 2, N은 100 = 1100100(2) 이고 마찬가지로 2^100인 A^N을 구하는 코드입니다.

먼저, 코드를 살펴보겠습니다.

N = 100 = 1100100(2) 이고, A는 2, Answer = 1로 시작합니다.

N & 1 은 N의 마지막 비트와 1을 And연산을 취하는 것으로, N & 1 은 False입니다.

따라서 answer는 그대로 1이고, N = N / 2 이므로 N = 50 = 110010(2)로 마지막 비트가 사라지고,

A = A * A ; 로 2^2인 4가 됩니다.

이 과정을 반복하면 아래 표와 같이 작동합니다.

#주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다.

100번의 연산이 아니라, 각 단계마다 3번의 연산으로 무려 7단계 만에 답을 구할 수 있습니다.

N이 커지면 커질수록 처음의 알고리즘보다 훨씬 더 빠르게 작동하겠죠?

잘 익혀두시면 정말 유용하게 사용하는 알고리즘입니다!

함수로 표현하면 다음과 같습니다.

long long math_pow(long long x, long long y)
{
	long long tmp = 1;
	while (y)
	{
		if (y & 1)
			tmp = tmp * x;
		y = y / 2;
		x = x * x;
	}
	return tmp;
}

당연히, A^N이 Int 나 long long 형 범위를 넘어가는 문제들은 A^N 을 어떤 수로 나눈 나머지를 구해달라 합니다!

아래와 같이 함수로 표현할 수 있습니다.

long long math_pow(long long x, long long y)
{
	long long tmp = 1;
	while (y)
	{
		if (y & 1)
			tmp = tmp * x % m;
		y = y / 2;
		x = x * x % m;
	}
	return tmp;
}

오늘의 포스팅은 여기서 마치겠습니다.

[추천문제]
https://www.acmicpc.net/problem/1629