개발뚱땅

미래에 대해서 고려하지 않음.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시한다.

예제 - 거스름돈

카운터에는 거스름돈으로 사용할 500, 100, 50, 10원이 무한히 존재한다고 가정. 손님에게 거슬러줘야할 돈이 N원인 경우 거슬러 줘야할 동전의 최소 개수를 구하라. (단, N은 항상 10의 배수이다.)

거스름돈 문제는 그리디 알고리즘으로 풀 수 있는 대표적 문제로, 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다.

기준 : 가장 큰 화폐 단위부터 돈을 거슬러 주는 것.

n=1260
count=0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n//coin # '//'은 몫을 구하는 연산자
    n %=coin

print(count)

그리디 알고리즘의 정당성

그리디 알고리즘으로 해법을 찾았을 때에는 그 해법이 정당한지 검토해야한다. ( 최적의 해가 아닐 수 있음)

위의 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 단위가 더 큰 동전은 항상 작은 단위 동전의 배수이기 때문이다. 그렇지 않으면 작은 단위의 동전을 종합해 다른 해가 나올 수 있다.

800원을 거슬러줘여하는 경우, 동전의 단위가 500 400 100이라고 하면 그리디 알고리즘으로 나오는 해는 500 + 100*3으로 4개이다. 그러나 최적 해는 400*2로 2개이다.

그러므로 그리디 알고리즘을 사용할 때, 해당 문제에 대해 사용하는 것이 정당한지 검토할 수 있어야한다.

괄호문제처럼 스택을 사용한다.

여는 괄호 ' ( '가 나오면 스택에 넣고

닫는 괄호 ' ) '가 나오면 두가지 케이스로 구분해 처리한다.

1. 레이저인 경우
   ()인 경우 레이저인데, 레이저로 잘리는 경우 스택에 넣었던 여는 괄호 하나를 제거해줘야한다.
   그리고 스택에 들어있는 쇠막대기의 수를 확인하여 답에 더해준다. 레이저로 자르는 순간 그만큼 갯수가 추가되기 때문이다.
2. 쇠막대기의 끝부분인 경우
   ))인 경우 쇠막대기의 끝이다. 왜냐하면 문제에 쇠막대기에는 하나 이상의 레이저가 포함된다고 했기 때문이다.
   그래서 그 경우 스택에서 pop해주고 답에 1을 더해주면 된다.

스택 자료구조를 쓰지 않고, 괄호를 세주는 변수를 사용해도 된다.

#include <string>
#include <vector>
#include <stack>
using namespace std;

int solution(string arrangement) {
    int answer = 0;
    stack<char> s;
        
    for(auto iter = arrangement.begin(); iter != arrangement.end(); ++iter){
        if(*iter == '('){
            s.push(*iter);
        }else{
            s.pop();
            if(*(iter-1) == '('){//laser
                answer += s.size();
            }else{
                answer++;
            }
        }
    }
    
    return answer;
}

괄호로 이루어진 문자열이 들어온다.

스택을 이용해서 괄호를 확인해주면 된다.

'('이 나온경우 스택에 넣고 ')'이 나오면 스택에 있던 '('을 빼주면 된다.

스택에 뺄'('가 없는데 ')'이 먼저 들어오는 경우도 잘못된 경우이며,

이제 문자열 확인이 끝났는데 스택에 '('이 남아있는 경우도 잘못된 경우이다.

여기서 스택을 직접 사용할 필요는 없고 괄호 카운팅용 정수 변수를 사용해서 구현한다.

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

bool solution(string s)
{
    bool answer = true;
    int cnt = 0;
    
    for(auto el : s){
        if(el == '('){
            cnt++;
        }else{
            cnt--;
        }
        if(cnt<0){
            return false;
        }
    }
    
    if(cnt==0){
        answer=true;
    }else{
        answer=false;
    }

    return answer;
}

카운터를 0으로 초기화하고,

'('인 경우 +1

')'인 경우 -1

그리고 카운터가 음수로 변하면 ')'가 먼저 나온게 되므로 false를 반환한다.

문자열 전체 순회가 끝나고

카운터가 0이 아니라면 '('이 더 많은 것이므로 false

카운터가 0인 경우 true를 반환한다.

힙정렬은 이진 힙 자료구조 기반의 정렬 기술입니다.

이것은 최대값 원소를 찾아 맨 끝에 위치시키는 점에서 선택정렬과 닮았습니다.

이진 힙이란? Binary Heap

먼저 완전 이진 트리를 정의해봅시다.

완전 이진 트리는 모든 레벨에서 마지막 리프를 제외하고 꽉차있고 마지막 노드는 왼쪽부터 채워집니다.

이진 힙은 아이템이 특정한 순서에 따라 저장되어있는 완전 이진트리입니다. 부모노드는 자식노드 보다 큰 값(작은값)을 갖습니다. 큰값을 갖는 경우 최대 힙이라고 하며, 작은 값을 갖는 경우 최소힙이라고 합니다.

힙은 이진트리나 배열로 구현할 수 있습니다.

이진 힙은 완전 이진 트리기 때문에 배열로 표현하더라도 공간이 낭비되지 않습니다. 배열로 쉽게 구현이ㅣ 가능합니다.

부모 노드의 인덱스를 i라 하면 왼쪽 자식 노드는 2*i+1 오른쪽 자식 노드는 2*i +2로 표현할 수 있습니다. (시작 인덱스가 0부터 시작하는 경우)

오름차순으로 정렬하기 위한 힙 정렬 알고리즘

1. 주어진 값으로 최대힙을 구성합니다.
2. 가장 큰 원소는 힙의 루트에 저장되어 있습니다. 루트값을 제일 뒤로 보내고 힙 사이즈를 1 줄입니다.
   제일 뒤로 보내 힙에서 제외한다는 의미입니다.
3. 힙의 크기가 1이 될때까지 반복하면 큰 순서대로 뒤에서부터 쌓이게 되어 오름차순으로 정렬됩니다.

힙을 만들 때 노드의 자식은 모두 힙구조여야 하므로 상향식으로 만들어져야 합니다.

#include <iostream> 

using namespace std; 

//arr의 인덱스인 i를 루트로 하는 서브 트리를 힙화 합니다.
//n은 힙의 크기입니다.  
void heapify(int arr[], int n, int i) 
{ 
	int largest = i; // 가장 큰 값 인덱스 
	int left = 2*i + 1; // left = 2*i + 1 왼쪽 자식 인덱스 
	int right = 2*i + 2; // right = 2*i + 2 오른쪽 자식 인덱스 

	//만약 왼쪽 자식이 루트보다 크다면 
	if (left < n && arr[left] > arr[largest]) 
		largest = left; 

	//오른쪽 자식이 largest보다 더 큰경우 
	if (right < n && arr[right] > arr[largest]) 
		largest = right; 

	//가장 큰 값이 루트가 아니라면 
	if (largest != i) 
	{ 
		//값을 바꾼다. 
		swap(arr[i], arr[largest]); 

		//그 아래 서브 트리도 똑같이 힙화 한다.
		//하향식 
		heapify(arr, n, largest); 
	} 
} 

void heapSort(int arr[], int n) 
{ 
	//힙 구조 만들기 (배열 재배치) 
	for (int i = n / 2 - 1; i >= 0; i--) 
		heapify(arr, n, i); 

	//힙으로 부터 원소 하나씩 추출 
	for (int i=n-1; i>=0; i--) 
	{ 
		//루트 값을 끝으로 이동 
		swap(arr[0], arr[i]); 

		//최대 힙구조로 설정 
		heapify(arr, i, 0); 
	} 
} 

void printArray(int arr[], int n) 
{ 
	for (int i=0; i<n; ++i) 
		cout << arr[i] << " "; 
	cout << "\n"; 
} 

int main() 
{ 
	int arr[] = {12, 11, 13, 5, 6, 7}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	heapSort(arr, n); 

	cout << "Sorted array is \n"; 
	printArray(arr, n); 
} 

힙정렬은 제자리 정렬이다.

힙정렬은 안정정렬이 아니다.

힙정렬의 시간 복잡도는 O(n log(n))이다.

"힙 구조를 이용해 정렬을 한다. Max heap을 만든 뒤 가장 위의 값을 맨 뒤로 보낸뒤 힙 크기를 1 줄이고, 다시 가장 위의 루트를 힙의 끝으로 보내고 1을 줄이고 반복한다. 힙의 크기가 1이 되면 주어진 배열이 모두 정렬되어 있다."

합병정렬처럼 분할 정복 알고리즘이다.

피벗으로 사용할 원소를 선택하고 주어진 배열을 피벗을 기준으로 분할한다.

피벗을 선택하는 방법에 따른 여러가지 버전의 퀵정렬이 있다.

1. 첫번째 원소를 피벗으로 하는 경우
2. 마지막 원소를 피벗으로 하는 경우
3. 랜덤으로 피벗을 선택하는 경우
4. 중앙값을 피벗으로 하는 경우

주요 프로세스는 partition()이다.

주어진 배열과 피벗x 로 분할한다.

x를 정렬되었을 때의 올바른 위치에 두고, 피벗보다 작은 값의 원소들을 피벗보다 앞에 위치시키고 피벗보다 큰 원소들은 뒤에 위치시킨다.

퀵정렬(arr[], low, high)

{

    if(low< high){

        partition_index = 분할(arr, low, high);

        퀵정렬(arr, low, partition_index - 1);

        //partition_index 는 피벗 원소가 정렬이 된 위치기 때문에 건드리지 않는다.

        퀵정렬(arr, partition_index , high);

    }

}

분할(arr[], low, high)

{

    pivot = arr[high];

    i = low;

   for(j = low; j < high; j++)

   {

       if(arr[j] < pivot )

       {

             swap arr[i] and arr[j];

             i++;

       }

    }

    swap arr[i] and arr[high];

    return i;

}

#include <bits/stdc++.h> 
using namespace std; 

void swap(int* a, int* b) 
{ 
	int t = *a; 
	*a = *b; 
	*b = t; 
} 


int partition (int arr[], int low, int high) 
{ 
	int pivot = arr[high];
	int i = low;

	for (int j = low; j <= high - 1; j++) 
	{ 
		if (arr[j] < pivot) 
		{ 
			swap(&arr[i], &arr[j]); 
			i++;
		} 
	} 
	swap(&arr[i], &arr[high]); 
	return i; 
} 

void quickSort(int arr[], int low, int high) 
{ 
	if (low < high) 
	{ 

		int pi = partition(arr, low, high); 

		quickSort(arr, low, pi - 1); 
		quickSort(arr, pi + 1, high); 
	} 
} 

void printArray(int arr[], int size) 
{ 
	int i; 
	for (i = 0; i < size; i++) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

int main() 
{ 
	int arr[] = {10, 7, 8, 9, 1, 5}; 
	int n = sizeof(arr) / sizeof(int); 
	quickSort(arr, 0, n - 1); 
	cout << "Sorted array: \n"; 
	printArray(arr, n); 
	return 0; 
} 

 시간복잡도

최악 - O(n^2)

최고,평균 - O(n log(n))

안정정렬이 아니며 제자리 정렬입니다.

"피벗값을 정한뒤 그보다 작은 값은 그앞에 배치, 그보다 큰 값은 뒤에 배치한 후 배치된 서브 배열에서 또다시 피벗을 정하고 반복한다."

퀵정렬 처럼, 합병정렬은 분할 정복 알고리즘입니다.

주어진 배열을 두개로 나누고, 두개의 배열을 인자로 합병정렬 함수 호출을 합니다. 그리고 정렬된 두 배열을 병합합니다.

merge() 함수는 두개의 배열을 합병하는데 사용됩니다.

merge(arr, left, middle, right)은 arr[left ... middle]과 arr[middle+1 ... right]이 정렬되었다는 가정하에 두개의 서브배열을 합병합니다.

#include<stdlib.h> 
#include<stdio.h> 
#include<cstring>
#include<iostream>
using namespace std;

void printArray(int A[], int size);

//두개의 배열을 합병합니다.
//left~middle, middle+1~right 까지
void merge(int arr[], int left, int middle, int right) 
{ 
	int left_size = middle - left + 1; 
	int right_size = right - middle; 

	/* 임시 배열을 만듭니다. */
	int Left[left_size], Right[right_size]; 

	/* 왼쪽 오른쪽 배열에 값을 복사합니다. */
	memcpy(Left, &arr[left], left_size*sizeof(int));
	memcpy(Right, &arr[middle+1], right_size*sizeof(int));

	/* Merge the temp arrays back into arr[l..r]*/
	int i=0;
	int j=0;
	int k = left; // Initial index of merged subarray 
//	둘다 합병이 끝나지 않은경우 
	while (i < left_size && j < right_size) 
	{ 
		//작은 값을 먼저 넣는다. 
		if (Left[i] <= Right[j]) 
		{ 
			arr[k] = Left[i]; 
			i++;
		} 
		else
		{ 
			arr[k] = Right[j]; 
			j++; 
		} 
		k++; 
	} 

	/* 왼쪽에 값이 남은경우 */
	if(i < left_size) 
	{ 
		memcpy(&arr[k], &Left[i], (left_size - i)*sizeof(Left[0]));
	} 

	/* 오른쪽 배열에 값이 남은경우 */
	if (j < right_size) 
	{ //인덱스 - 인덱스가 아닌 갯수에서 j를 빼는 거라 +1할 필요가 없다 
		memcpy(&arr[k], &Right[j], (right_size - j)*sizeof(Right[0]));
	} 
} 

//정렬하려는 배열의 왼쪽, 오른쪽 인덱스를 넣어준다. 
void mergeSort(int arr[], int left, int right) 
{ 
	if (left < right) //오른쪽 인덱스가 더 큰경우만 시행 
	{ 
		//(left+right)/2랑 같으나 오버플로우를 막기 
		int middle = left+(right-left)/2; 

		//배열을 나누어 재귀함수 호출한다. 
		mergeSort(arr, left, middle); 
		mergeSort(arr, middle+1, right); 
		
		//나눈 배열들을 합병한다. 
		merge(arr, left, middle, right);
		
	} 
} 

void printArray(int A[], int size) 
{ 
	int i; 
	for (i=0; i < size; i++) 
		cout<<A[i]<<" "; 
	cout<<endl;
} 

int main() 
{ 
	int arr[] = {12, 11, 13, 5, 6, 7}; 
	int arr_size = sizeof(arr)/sizeof(int); 

	cout<<"Given array is"<<endl; 
	printArray(arr, arr_size); 

	mergeSort(arr, 0, arr_size - 1); 

	cout<<endl<<"Sorted array is"<<endl; 
	printArray(arr, arr_size); 
	return 0; 
} 

시간복잡도

O(n log(n))

제자리 정렬이 아니며, 안정정렬이다

"주어진 배열을 최대한으로 나눈 뒤 합병하면서 정렬시키는 방식이다."

삽입정렬은 우리가 카드를 정렬하듯 작동하는 간단한 정렬 알고리즘입니다.

8 7 1 2 9 6,   시작

7 8 1 2 9 6,   7은 8보다 앞에 오므로 그 앞에 삽입

1 7 8 2 9 6,   1은 8보다, 7보다 앞에 오므로 그 앞에 삽입

1 2 7 8 9 6,   2는 8보다, 7보다 앞에 오므로 그 앞에 삽입

1 2 7 8 9 6,   9는 8보다 크므로 그대로

1 2 7 6 8 9,   6은 9보다 8보다 작으므로 그 앞에 삽입

#include <bits/stdc++.h> 
using namespace std; 

void insertionSort(int arr[], int n) 
{ 
	for(int i=1; i<n; i++){
		int key = arr[i];
		
		int j=i-1;
		//key가 들어갈 자리를 찾는다 
		while(j>=0 && arr[j] > key){
			arr[j+1] = arr[j];
			j--;			
		}
		//그 자리에 삽입한다. 
		arr[j+1]=key;
	}
} 

void printArray(int arr[], int n) 
{ 
	int i; 
	for (i = 0; i < n; i++) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

int main() 
{ 
	int arr[] = { 12, 11, 13, 5, 6 }; 
	int n = sizeof(arr) / sizeof(int); 

	insertionSort(arr, n); 
	printArray(arr, n); 

	return 0; 
}

시간복잡도: O(n^2)

제자리정렬이며 안정정렬이다.

"정렬할 원소가 들어갈 자리를 찾아 삽입한다. 1번 인덱스 원소부터 마지막 인덱스 원소까지 실시한다."

버블정렬은 가장 간단한 알고리즘입니다.

인접한 원소를 비교하고 반복적으로 재배열 하면서 작동합니다.

예:

(5 1 4 2 8)->(1 5 4 2 8), 처음 두 원소를 비교하고 5와 1을 바꿉니다.

(1 5 4 2 8)->(1 4 5 2 8), 5와 4를 바꿉니다.

(1 4 5 2 8)->(1 4 2 5 8), 5와 2를 바꿉니다.

(1 4 2 5 8)->(1 4 2 5 8), 순서가 올바르기에 5와 8은 바꾸지 않습니다. pass

(1 4 2 5 8)->(1 4 2 5 8)pass

(1 4 2 5 8)->(1 2 4 5 8), 4와 2 교환

(1 2 4 5 8)->(1 2 4 5 8)pass

(1 2 4 5 8)->(1 2 4 5 8)pass

이제 정렬이 되었지만 알고리즘 내에서는 완료 되었는지 알 수 없기에, 전부 pass될 때 까지 반복합니다.

(1 2 4 5 8)->(1 2 4 5 8)pass

(1 2 4 5 8)->(1 2 4 5 8)pass

(1 2 4 5 8)->(1 2 4 5 8)pass

(1 2 4 5 8)->(1 2 4 5 8)pass

#include <bits/stdc++.h> 
using namespace std; 

void swap(int *xp, int *yp) 
{ 
	int temp = *xp; 
	*xp = *yp; 
	*yp = temp; 
} 

void printArray(int arr[], int size) 
{ 
	int i; 
	for (i = 0; i < size; i++) 
		cout << arr[i] << " "; 
	cout << endl; 
} 

void reculsiveBubbleSort(int arr[], int n) 
{ 
    // Base case 
    if (n == 1) 
        return; 
  
    bool all_pass = true;
    for (int i=0; i<n-1; i++) 
        if (arr[i] > arr[i+1]){
        	swap(arr[i], arr[i+1]);
        	all_pass = false;
		}
    printArray(arr, n); 
  	if(all_pass == true){
  		return;
	  }

    reculsiveBubbleSort(arr, n-1); 

void bubbleSort(int arr[], int n) 
{ 
	
	for(int i=0; i<n-1;i++){//원소와 원소 사이마다 한번씩만 반복하면 된다. 그러므로 1회 제거 
		bool all_pass = true;
		for(int j=0; j < n-1-i; j++){//1회 반복 시 제일 뒤의 원소는 정렬이 된 상태가 된다 그러므로 i만큼 빼준다. 
			if (arr[j] > arr[j+1])
			{
				swap(&arr[j], &arr[j+1]);
				all_pass=false;
			}
		}
		printArray(arr, n); 
		if(all_pass == true){
			break;
		}
	}
} 

int main() 
{ 
	int arr[] = {5, 4, 3, 2, 1};
	int n = sizeof(arr)/sizeof(int); 
	bubbleSort(arr, n); 
	cout<<"Sorted array: \n"; 
	printArray(arr, n); 
	return 0; 
} 

제자리 정렬이며 안정정렬이다.

최악의 경우 시간복잡도 O(n^2)이다.

"인접한 원소를 정렬해나가기 때문에 버블처럼 보인다. 1회 반복때마다 가장 큰 원소는 맨 뒤에 자리하게 된다."