힙 정렬(Heap Sort)


정렬 시리즈 중 고급 정렬 알고리즘에 속하는 힙정렬은 힙이라는 자료구조를 토대로 정렬합니다. 그러니까 힙에 대해서 알고 와야겠죠??


힙에 대해서 모르는 분들은 아래 url를 참고하시기 바랄게요.

https://reakwon.tistory.com/42


힙에 대해서 아셨다면 이제 어떻게 정렬을 하는지 알아보도록 하지요.


정렬


위의 url의 코드를 통해서 힙정렬을 한다고 하면 의외로 쉽습니다. 메인 함수를 이렇게 바꾸어서 실행해보세요. 정렬이 아주아주 잘됩니다.


int main() {
	heap hp;
	initHeap(&hp);
	int i;
	int arr[] = { 5,3,4,1,6,10 };
	int size = sizeof(arr) / sizeof(int);
	for (i = 0; i < size; i++)
		insert(&hp, arr[i]);

	for (i = 0; i < size; i++)
		arr[i] = deleteData(&hp);

	for (i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}


근데 문제점이 있죠. arr이라는 배열 공간과 heap이라는 배열 공간 두개를 쓰니까 메모리의 낭비가 있습니다.


그리고 insert함수를 부르는 시간 nlog(n), deleteData함수를 부르는 시간 nlog(n)입니다.


우리는 더 잘할 수 있다

이것도 훌륭하지만 우리는 더 나아갈 수 있습니다. 더 잘할 수 있습니다.


아래의 그림은 방금 위의 배열을 단지 트리 형태로 표현한 것입니다.




최대힙을 구현할 것인데, 힙의 조건을 만족하지 않지요. 왜냐면 5가 가장 큰 원소가 아니거든요. 


아차, heap을 구현할때는 1부터 인덱스가 시작되는데 힙정렬할땐 0부터 시작한답니다. 왜냐면 공간을 아끼기 위해 그 배열 자체를 정렬할 것이기 때문이에요. 배열의 인덱스는 0부터 시작하는 것이니까요.


heapify

우리는 이것을 힙의 모양으로 고치는 것, 그 함수를 heapify라고 정의해보겠습니다.


heapify(int arr[], int here, int size) = 크기가 size인 배열 arr을 here부터 힙의 모양대로 만드는 함수


코드와 함께 heapify가 어떻게 동작하는 지 보도록 합시다.



void heapify(int arr[], int here, int size) {
	int left = here * 2 + 1;
	int right = here * 2 + 2;
	int max=here;
	if (left<size&&arr[left]>arr[max])
		max = left;
	if (right < size&&arr[right]>arr[max])
		max = right;

	if (max != here) {
		swap(&arr[here], &arr[max]);
		heapify(arr, max, size);
	}
}


이 함수 하나로 힙의 모양을 만들수는 없습니다. 

아래 왼쪽의 트리에서 우리가 heapify(arr, 0, size)를 호출한다고 치면 오른쪽의 트리로 만들어지게 됩니다.




가장 작은 1이 맨 끝에 이동함을 알 수 있죠. 하지만 최대힙은 아닙니다. 4가 가장 큰 값이 아니잖아요. 


우리는 이렇게 생각해볼 수 있습니다. 만약 자식을 갖고 있는 노드가 있다면 그 위치에서부터 heapify를  역순으로 호출하는 방식이죠. 그러니까 자식노드를 갖고 있는 노드는 0, 1, 2의 인덱스인데, heapify(arr, 2, size), heapify(arr, 1, size), heapify(arr, 0, size) 이렇게 호출하면 되지 않을까요?




그런 함수가 buildHeap이라는 함수입니다.


buildHeap


우선 우리는 자식을 갖고 있는 노드가 어떤 인덱스를 갖고 있어야하는지 알아야합니다. 어떻게 알 수 있을까요??


가장 마지막 노드는 size-1의 노드인것을 알 수 있습니다. 하지만 우리는 그 부모님 성함을 알 수 있죠. 바로 size/2 -1이 그 부모노드의 인덱스라는 것을 알 수 있습니다.

그러니까 맨 마지막의 인덱스는 5, 그 부모노드는 5/2 -1로 2가 됩니다. 


이제부터 우리는 

{ 5,3,4,1,6,10 }

이 배열을 heap으로 만드는 과정을 살펴봅니다.


초기는 아래와 같죠.




자식을 갖고 있는 노드를 알았으니 heapify(arr, 2, size)를 호출해봅시다. 그러면 위의 트리는 이렇게 바뀝니다.





10이 더 크니까 4와 자리를 바꾸죠.


이제 heapify(arr, 1, size)를 호출하면 다음과 같이 바뀝니다.




6이 더 크니까 3과 자리를 바꿉니다.


이제 heapify(arr,  0, size)를 호출합시다.



5의 자식 중 10이 5보다 크네요. 자리 바꿔줍니다.


루트까지 호출이 되었으니까 heapify는 종료됩니다.


어때요? 최대힙 모양이 완성되었죠? 

이것을 for루프로 돌리면 아래와 같은 코드가 됩니다.


void buildHeap(int arr[], int size) {
	int i,j;
	for (i = size / 2 - 1; i >= 0; i--) {
		heapify(arr, i, size);
		for (j = 0; j < size; j++)
			printf("%d ", arr[j]);
		printf("\n\n");
	}
}




이제 정렬 좀 하자..

여기까지 됐으면 거의 끝났습니다. 루트원소를 맨끝에 옮기고 다시 heapify를 호출하면 됩니다. 단, 트리의 사이즈는 하나씩 줄어듭니다.


이제 정렬과정만 보이면 되겠군요.


void heapSort(int arr[],int size) {
	int treeSize;
	buildHeap(arr, size);
	for (treeSize = size - 1; treeSize >= 0; treeSize--) {
		swap(&arr[0], &arr[treeSize]);
		heapify(arr, 0,treeSize);
	}
}

트리의 크기가 처음에는 6입니다. 크기를 점점 줄여나가는 것을 보세요. 

아래의 그림들이 위의 코드가 어떻게 동작하는지 보여줍니다.




우선 0번 노드와 5번 노드의 값을 바꾸어줍니다. 똥색 표시는 이미 정렬된 부분을 의

미합니다. 그 후 heapify를 호출하면 다시 힙의 모양을 유지하게 됩니다. 




이제는 0번 노드와 4번 노드를 교환합니다. 그리고 똥색으로 표시해주고, 이제는 트리 사이즈가 4가 됩니다. 그 후 heapify를 호출해서 사이즈 4까지 힙의 모양으로 만들어 줍니다. 5가 제일 큰 노드가 되겠네요.



이제 0번 노드와 3번 노드를 바꿉니다. 5, 6, 10까지 정렬된 것이 보이죠?? 그 후 heapify를 호출해서 최대힙의 모양으로 유지합니다.




이제 거의 다 왔습니다. 0번 노드가 가장 크므로 마지막 노드와 교체합니다. 4까지 정렬된 것을 확인할 수 있습니다. 그 후 heapify 호출해서 heap으로 유지합니다.



이제 가장 큰 노드 0번과 1번을 바꿉니다. 3까지 정렬됐습니다. 그 후 heapify호출하여 heap의 모양으로 만들어 줍니다.





이제 하나남았네요. 가장 큰 노드가 자기 자신이니까 바꾸나 마나고 heapify를 호출해도 그 모양 그대로 유지합니다.

트리를 보세요! 정렬이 된것을 확인할 수 있지요??




여기 그 전체코드가 있습니다.



#include <stdio.h>

void swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
void heapify(int arr[], int here, int size) {
	int left = here * 2 + 1;
	int right = here * 2 + 2;
	int max=here;
	if (left < size&&arr[left]>arr[max])
		max = left;
	if (right < size&&arr[right]>arr[max])
		max = right;

	if (max != here) {
		swap(&arr[here], &arr[max]);
		heapify(arr, max, size);
	}
}

void buildHeap(int arr[], int size) {
	int i,j;
	for (i = size / 2 - 1; i >= 0; i--) {
		heapify(arr, i, size);
		for (j = 0; j < size; j++)
			printf("%d ", arr[j]);
		printf("\n\n");
	}
}

void heapSort(int arr[],int size) {
	int treeSize;
	buildHeap(arr, size);
	for (treeSize = size - 1; treeSize >= 0; treeSize--) {
		swap(&arr[0], &arr[treeSize]);
		heapify(arr, 0,treeSize);
	}
}
void printArray(int arr[], int size) {
	int i;
	for (i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
int main() {
	int arr[] = { 5,3,4,1,6,10 };
	int size = sizeof(arr) / sizeof(int);
	
	heapSort(arr, size);
	printArray(arr, size);
}


시간복잡도

힙 정렬에서 시간 복잡도는 O(nlogn)입니다. 완전 이진 트리이기때문에 높이가 균등합니다. 그래서 heapify는 logn으로 보장할 수 있습니다. 그리고 heapify를 n번 호출하기 때문에 nlogn이라는 것을 알 수 있지요. 


도움이 되셨나요??

반응형
블로그 이미지

REAKWON

와나진짜

,

동전 교환 알고리즘


개념


편의점 아르바이트생인 A는 야간에 편의점 알바를 하고 있어요. 막상 편의점에 도착해서 보니까 동전이 없습니다. 그래서 사장님께 전화를 걸었으나, 이미 술취해서 뻗어버린 상태입니다. 할 수 없이 일단 가지고 있는 동전으로 거스름돈을 주며 내일 아침 사장님이 올때까지 뻐겨야하는 상황이 발생했습니다.

그러기 위해서는 거스름돈에 사용되는 동전의 갯수를 최소로 사용하여 주어야하는데 어떻게 최소 동전 갯수를 구할 수 있을까요?


현실에서는 10원, 50원, 100원, 500원의 동전이 있지만 여기서는 1, 4, 5, 6원의 동전이 있다고 가정하도록 하겠습니다. 만약 23원의 거스름돈을 위의 동전을 최소로 사용해 거슬러준다면 어떻게 거슬러주면 될까요? 여러가지가 있지만, 우선 가장 큰 값인 6을 먼저주고 남은것은 그 다음 큰 동전으로 사용한다면 6원 3개, 5원 1개로 23원을 만들 수 있습니다. 동전을 최소로 사용해서 준 것 맞습니까?




네, 가장 최소의 동전을 사용해서 준 것이 맞습니다.

항상 최대값의 동전을 우선적으로 사용해서 얻은 결과가 바로 답일까요? 일리있어 보이지만 항상 그렇지 않습니다.


14원을 예로 한번 들어보도록 합시다.

위의 방식대로 한다면 6원 2개, 1원 2개, 4개의 동전을 사용해서 14원을 만들 수 있습니다.

하지만 5원부터 주게되면 5원 2개, 4원 1개로 3개의 동전을 사용해서 14원을 만들 수 있습니다.


이제부터 어떻게 구할지 생각해보도록 하겠습니다.

우선 동전 하나를 가지고 얼마를 만들 수 있을지 생각합시다. 우선 1원입니다. 1원은 모든 수를 전부 만들 수 있습니다. 그렇다면 아래의 표와 같겠네요.


1원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수) 

 1

 1(1,0,0,0)

 2

 2(2,0,0,0)

 3

 3(3,0,0,0)

 4

 4(4,0,0,0)

 5

 5(5,0,0,0)

 6

 6(6,0,0,0)

 7

 7(7,0,0,0)

 8

 8(8,0,0,0)

 9

 9(9,0,0,0)

 10

 10(10,0,0,0)

 11

 11(11,0,0,0)

 12

 12(12,0,0,0)

 13

 13(13,0,0,0)

 14

 14(14,0,0,0)



4원을 사용한다면 4원은 당연히 한개로 만들 수 있고, 5원은 그 전의 1원과 합쳐서 만들 수 있습니다. 그렇다면 5원은 2개로 만들 수 있겠군요. 8원은 그전의 4원 2개로 만들 수 있습니다.

9원은 어떻겠습니까? 그전에 5원을 2개의 동전으로 구했었습니다. 1원과 4원을 합쳐서 말입니다. 여기에 4원을 더 얹으면 9원 아닌가요? 그래서 1원 1개, 4원 2개로 9원을 만들 수 있습니다. 그렇다면 표가 다음과 같이 바뀝니다.


4원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수) 

 1

 1(1,0,0,0)

 2

 2(2,0,0,0)

 3

 3(3,0,0,0)

 4

 1(0,1,0,0)

 5

 2(1,1,0,0)

 6

 3(2,1,0,0)

 7

 4(3,1,0,0)

 8

 2(0,2,0,0)

 9

 3(1,2,0,0)

 10

 4(2,2,0,0)

 11

 5(3,2,0,0)

 12

 3(0,3,0,0)

 13

 4(1,3,0,0)

 14

 5(2,3,0,0)



이제 5원을 사용하도록 합시다. 5원을 사용하게 되면 5원은 동전 한개로 만들 수 있고, 6원은 1원의 동전화 합쳐서 만들 수 있겠습니다. 10원은 5원 두개로 만들 수 있고 11원이 그 전의 6원을 만들었던 것에서 5원을 추가하여 만들 수 있답니다. 




5원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수)  

 1

 1(1,0,0,0)

 2

 2(1,0,0,0)

 3

 3(1,0,0,0)

 4

 1(0,1,0,0)

 5

 1(0,0,1,0)

 6

 2(1,0,1,0)

 7

 3(2,0,1,0)

 8

 2(0,2,0,0)

 9

 2(0,1,1,0)

 10

 2(0,0,2,0)

 11

 3(1,0,2,0)

 12

 3(0,3,0,0)

 13

 3(0,2,1,0)

 14

 3(0,1,2,0)


이제 감이 오시나요?


결국 현재의 동전만큼을 뺀 거스름돈에서 현재 동전하나를 추가하여 만드니까 그 전의 거스름돈에 1을 더하면 됩니다. 

하지만 이미 구해진 거스름돈이 더 적은값을 가지고 있다면 현재의 값을 유지하면 되는 것입니다. 그래서 이런 식이 나오게 됩니다.


dp[j] = MIN(dp[j], dp[j - coin[i]] + 1); 


dp[j]는 현재 구할 거스름돈의 값입니다. 그래서 현재 거스름돈에서 현재 동전을 뺀 값이 dp[j-coin[i]]를 의미합니다. 그래서 현재 거스름돈 dp[j]와dp[j-coin[i]]+1을 비교하여 작은 값이 답이 됩니다.


이제 5도 했으니 6도 해봅시다. 위의 식대로 구한다면 다음의 표가 완성되겠습니다.


6원 사용시


 거스름 돈

동전 갯수(1원 갯수, 4원 갯수, 5원 갯수, 6원 갯수)   

 1

 1(1,0,0,0)

 2

 2(2,0,0,0)

 3

 3(3,0,0,0)

 4

 1(0,1,0,0)

 5

 1(0,0,1,0)

 6

 1(0,0,0,1)

 7

 2(1,0,0,1)

 8

 2(0,2,0,0)

 9

 2(0,1,1,0)

 10

 2(0,0,2,0)

 11

 2(0,0,1,1)

 12

 2(0,0,0,2)

 13

 3(1,0,0,2)

 14

 3(0,1,2,0)



이제 모든 동전을 사용해서 14원이 3개의 동전으로 교환될 수 있다는 것을 알았습니다.




구현

구현은 뭐 위에서 설명한 것을 그대로 코드로 옮기면 되는데 몇몇 설명할게 아직은 남아있습니다. 전체 소스코드를 보면서 이야기 해보도록 하겠습니다.

#include <stdio.h>
#define MIN(a,b) a<b ? a:b
#define N 4
#define M 14
#define INF 987654321;
int dp[M+1];
int coin[N] = { 1,4,5,6 };
int main() {
	int i, j;

	for (i = 1; i <= M; i++)
		dp[i] = INF;

	for (i = 0; i < N; i++) {
		printf("동전 %d 사용시\n",coin[i]);
		for (j = coin[i]; j <= M; j++) {
			dp[j] = MIN(dp[j], dp[j - coin[i]] + 1);
			printf("%d %d\n", j, dp[j]);
		}
		printf("\n\n");
	}
	printf("%d\n", dp[M]);
}




우선 dp를 아주 큰 값으로 초기에 설정합니다. 그렇지 않으면 0이 되니까요. MIN 매크로 함수를 통해서 작은 값을 구해야하는데 dp가 0이 되버리면 MIN은 항상 0을 반환하게 됩니다.
위에서 이야기한대로 코드로 옮겼습니다.


반응형
블로그 이미지

REAKWON

와나진짜

,

병합정렬 (Merge Sort)


기본 개념

병합 정렬을 알기 전에 우선 Devide and Conquer에 관한 개념을 알고 있어야 합니다. 아니, 몰라도 됩니다. 이제부터 배울꺼거든요. 간단히 말해 어떤 문제를 우선 작은 문제로 쪼개고 난 후 다시 조합하여 원래의 문제를 푼다는 것인데요.

병합정렬을 통해서 어떤 개념인지 알아보도록 하겠습니다.


우선 배열이 있습니다. 정렬이 되지 않은 정수형 배열이지요.

일단 묻지도 따지지도 않고 쪼갭니다. 아주 산산조각을 냅니다.







이 후에 쪼갠 역순으로 정렬을 하는 것입니다. 아래의 그림처럼요. 쪼갠것을 다시 차근차근 조립하면서 정렬하는 것을 볼 수 있지요.





그래서 우리는 이 그림을 이해하는 것이 목적입니다.


구현

구현은 2가지의 큰 틀로 구성이 됩니다.


1. 분할

가장 먼저 해야될 작업입니다. 이 작업은 쉽습니다. 배열을 그냥 2로 계속 나누다보면 언젠가는 하나의 원소를 갖게되니까 그때 멈추면 됩니다. 

 

mergeSort라는 함수를  보세요. 정렬할 배열과 왼쪽끝을 나타내는 left, 오른쪽 끝을 나타내는 right를 인자로 받고 있습니다.

void mergeSort(int arr[], int left, int right) {

	if(left==right) return;  
	int mid;
	
	mid = (left + right) / 2;
	mergeSort(arr, left, mid); 
	mergeSort(arr, mid + 1, right); 
	
}


아래의 그림처럼 left와 right를 이용해서 mid를 기준으로 쪼개는 겁니다. mid는 left와 right의 중간 부분을 가리키고 있죠. 



그러다가 하나의 원소만 남게되면 바로 return이 됩니다. 어떻게 알 수 있을까요? 하나의 원소만 남았다는 것은 left와 right가 서로 같은 값을 가졌다는 것을 의미하니까 left==right라면 바로 return 하면 됩니다.




2. 병합

병합은 조금 어려울 수도 있지만 이해하면 별거 없습니다. 

우선 코드부터 보면서 이해하자구요.

void merge(int arr[], int left, int right) { int L, R, k, a; int mid = ( left + right ) / 2; L = left; R = mid + 1; k = left; while (L <= mid && R <= right) tmp[k++] = arr[L] <= arr[R] ? arr[L++] : arr[R++]; if (L>mid) for (a = R; a <= right; a++) tmp[k++] = arr[a]; else for (a = L; a <= mid; a++) tmp[k++] = arr[a]; for (a = left; a <= right; a++) arr[a] = tmp[a]; }




뭐지 이 변태같은 코드는? 이러지 마시구요. 하나하나 보도록 합시다. 차근차근히


인자로 배열 arr과 left, right를 받고 있습니다. 나누어진 배열의 한쪽은 L, 그리고 다른 한쪽은 R을 인덱스로 하기로 합시다. 쪼개진 배열 하나를 왼쪽에 있다 생각하고 L, 다른 하나는 오른쪽에 있다고 생각하고 R로 한거에요. R은 mid+1부터 시작해야겠죠? 

tmp라는 임시배열은 k를 인덱스로 합니다.


그리고 나누어 쪼개져서 정렬된 일부분의 배열을 부분 배열이라고 하겠습니다. 


자, 됐으면 이제 while문을 돕니다. while루프는 왼쪽 부분 배열을 전부 다 돌았거나 오른쪽 부분 배열을 전부다 돌때까지 반복합니다. 그러니 L은 mid 이하까지 R은 right 이하까지 반복하는데 왼쪽 배열, 오른쪽 배열 하나라도 전부 반복이 되었다면 탈출합니다. 


여기서부터는 그림이 좀 필요하겠네요.


왼쪽 부분 배열과 오른쪽 부분 배열의 원소를 비교해서 더 작은 값이 tmp로 값이 복사됩니다. 같을 때는 아무거나 넣어도 상관없겠죠. 그러니 현재 1과 2 중 1이 더 작으므로 tmp에 1이 저장됩니다. 그리고 L과 k를 하나씩 증가시키죠. 사실 k는 계속 증가하는 상태입니다. 항상 값이 들어가니까요.



그 후 arr[L]과 arr[R] 중 값이 작은 것을 또 선택합니다. 3과 2 중 2가 더 작으니 2를 tmp에 넣습니다. 이후 R과 k는 증가합니다. 


마찬가지입니다. arr[L]과 arr[R] 중 가장 작은 값은 3이므로 3을 넣습니다. 그 후 k와 L의 값이 하나 증가합니다.


4까지 넣고 나면 한쪽 부분 배열(왼쪽)이 전부 tmp에 저장됐으므로 이제 while루프는 종료됩니다. 


이제 남은 것을 옮겨야하는데요. 5가 남았죠? 

만약 L이 mid보다 크다면 왼쪽 부분 배열이 tmp에 전부 복사된 것이므로 오른쪽에 있는 부분 배열의 값을 모조리 tmp에 집어넣습니다. 


반대도 역시 똑같습니다. 오른쪽 부분 배열이 전부 tmp에 복사되었다면 R은 right보다 크게 될테니까 왼쪽 부분 배열의 남은 값을 전부 tmp에 집어넣으면 되는 것이죠.


이제 원본 배열에 값을 다시 돌려주어야합니다. tmp는 잠시 저장하는 용도로 쓰기 때문이죠.





어때요. 아름답게 정렬이 된것을 확인할 수 있죠??


merge라는 함수를 구현했으니, 이제 mergeSort에서도 이 함수를 이용해서 병합! 하면 됩니다. 아래처럼 merge 함수를 추가하세요. 

void mergeSort(int arr[], int left, int right) { if (left == right) return; int mid; mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, right); }



보다 이해가 잘 되기 위해 전체코드를 보세요.

#include <stdio.h> #define SIZE 5 int tmp[SIZE]; void merge(int arr[], int left, int right) { int L, R, k, a; int mid = (left + right) / 2; L = left; R = mid + 1; k = left; while (L <= mid && R <= right) tmp[k++] = arr[L] <= arr[R] ? arr[L++] : arr[R++]; if (L>mid) for (a = R; a <= right; a++) tmp[k++] = arr[a]; else for (a = L; a <= mid; a++) tmp[k++] = arr[a]; for (a = left; a <= right; a++) arr[a] = tmp[a]; } void mergeSort(int arr[], int left, int right) { if (left == right) return; int mid; mid = (left + right) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, right); } void printArr(int arr[], int size) { int i; for (i = 0; i<size; i++) printf("%d ", arr[i]); printf("\n"); } void main() { int i; int arr[SIZE] = { 3,4,1,5,2 }; mergeSort(arr, 0, SIZE - 1); printArr(arr, SIZE); }



시간복잡도

버블 정렬이나 선택정렬 이런 정렬과는 어떤 차이가 있을까요?? 시간복잡도에서 차이가 있습니다. 병합정렬은 nlogn의 시간복잡도를 갖고 있습니다. 계속 둘로 쪼갠 횟수 만큼 n번의 루프를 돌기 때문입니다. 더 빠르다는 것을 알 수 있습니다.



반응형
블로그 이미지

REAKWON

와나진짜

,

정렬 알고리즘

정렬 알고리즘은 알고리즘 과목 중에서 기초적으로 반드시 알고 지나가야되는 파트입니다. 단순히 작은 순, 또는 큰 순으로 순서를 정렬하는 데에도 여러가지 알고리즘이 존재하는데요. 우리가 바로바로 이해할 수 있는 알고리즘이 있는 가 하면 좀 복잡하게 정렬하는 알고리즘도 있지요. 우리는 그나마 쉬운 편에 속하는 정렬 알고리즘 3개를 같이 보겠습니다.

 

1. 선택정렬(Selection Sort)

선택 정렬은 일단 자리는 정해져있습니다. 첫번째 자리에 가장 작은 녀석을 집어넣으면 되죠. 그리고 난 후에 두번째 자리에 그 다음 가장 작은 녀석을 선택해 집어 넣습니다. 이 짓을 배열이 끝날때까지 합니다.

 

다음 배열 arr에는 9, 8, 1, 2, 3이 있습니다. 이것을 선택정렬로 정렬하도록 해봅시다.

 

 

우선 제일 첫번째 자리 , 즉 9가 있는 자리를 i라고 놓고 j는 i 다음부터 배열의 가장 작은 index를 뽑아 옵니다. 그것을 minIndex라고 하지요.

j는 8부터 배열을 검색하면서 가장 작은 index를 찾아보니 1이 있는 자리가 제일 작군요. 그러니 minIndex는 2(1이 있는 배열 원소의 위치!)가 됩니다. 그래서 가장 첫번째 자리는 1이 되겠습니다.

 

 

 

그 후 두번째 자리(8이 있는 자리)가 i가 되고, j는 그다음 가장 작은 원소의 index를 구하게 되니까 minIndex는 2가 있는 자리, 즉 4가 됩니다.

minIndex와 i를 바꿉니다.

 

 

 

다음은 9가 있는 자리입니다. i는 2가 되겠네요. 가장 작은 인덱스는 3이 있는 자리이므로 i와 바꾸어 줍니다.

 

 

다음 i가 하나 증가되어 9를 가리킵니다. 8이 더 작으니까 바꾸어 주어야겠죠??

 

 

이제 모든 비교와 교환은 끝났습니다. 오름차순으로 정렬이 된것을 볼 수 있습니다.

 

 

 

아래는 선택정렬을 구현한 코드입니다.

void selectionSort(int arr[], int size) {
    int minIndex;
    int i, j;
    for (i = 0; i < size - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < size; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;

        swap(&arr[i], &arr[minIndex]);
    }
}
 
2. 버블 정렬
버블 정렬은 현재 배열 요소와 그 다음 배열 요소를 비교한다음 조건에 걸리면 교환하는 식의 정렬입니다. 그러니까 배열의 0번 인덱스의 요소와 1번 인덱스의 요소를 비교하고, 그 다음 1번 인덱스의 요소와 2번 인덱스의 요소를 비교합니다. 이 짓을 계속하면 정렬이 됩니다. 아래의 배열을 가지고 버블 정렬로 정렬해보도록 하지요.
 

 

 

인덱스를 j라고 표시하겠습니다. 우선 가장 앞 자리부터 그 다음 원소를 비교합니다. 9와 8을 우선 비교하는 것이죠. 9가 더 크니 8과 9를 바꿉시다. 

 

 

 

그 다음 j가 하나 증가하여 다음 자리를 가리키고 9와 1을 비교합니다. 9가 더 크니 1과 9를 바꿉시다.

 

느낌 오시나요? 가장 큰 요소를 끝으로 보내려고 하는 겁니다. 다음 j를 하나 증가시키고 9와 3을 비교합니다. 9가 더크네요. 3과 9를 바꾸어줍니다.

 

 

다시 j가 하나 증가하게 되고 9과 2를 비교해보니 9가 더 크니까 자리를 바꾸어줍니다.

 

이렇게 보니까 9(제일 큰 수)가 제일 뒤로 갔군요. 

 

 

 

그 다음은 4번째(인덱스 3)까지 이런 방식을 반복합니다. 하나씩 줄여가면서 이런 방식을 반복하여 가장 큰수를 오른쪽으로 보내면 정렬이 되는 것이죠. 버블 정렬을 코드로 구현한 것이 아래에 있습니다.

void bubbleSort(int arr[], int size) {
    int i, j;
    for (i = size - 1; i > 0; i--)
        for (j = 0; j < i; j++)
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
}

 

 

3. 삽입 정렬

 

삽입 정렬을 우선 배열의 한 원소인 key라는 값을 우선 가지고 있고, 이 key를 알맞은 자리에 삽입하면 됩니다. key보다 큰 값은 하나하니씩 밀어버리고 key보다 작은 값을 만났으때 그 뒷자리에 삽입하는 것입니다.

 

그림을 통해봅시다.

우선 배열이 이렇게 있구요. 사실 계속 이 배열을 썼었죠.

 

 

우선 key값은 배열 인덱스 1번부터 시작입니다. i 이전의 원소를 비교해야하는데, 인덱스가 0이면 비교할게 없으니까요. key는 8로 8보다 큰 값은 오른쪽으로 밀어버립니다. 8보다 작은 원소가 발견되면 그 원소 뒤에 8을 삽입해야하는 데 없으므로 제일 앞에 삽입합니다.

 

 

 

8이 맨앞에 삽입 되고 난 후 i가 하나 증가하여 계속 비교합니다. key는 1이 됩니다. 1보다 작은 원소가 없으므로 제일 앞에 위치하게 됩니다.

 

 

 

 

 

이후 i가 하나 증가하고 키는 3입니다. 3보다 작은 원소를 만날때 그 뒤에 삽입하는 과정을 아래 그림이 보여줍니다.

 

 

 

 

 

 

 

이제 i가 하나 증가하게 되고 마지막 원소인 2가 키가 됩니다. 2보다 작은 원소는 1이므로 1뒤에 2를 삽입하는 것이 되지요. 아래 그림이 그 과정을 보여줍니다.

 

 

 

 

 

 

 

 

 

 

 

최종적으로 정렬된 상태는 바로 이와 같습니다.

 

 

삽입 정렬에 대한 코드는 아래와 같습니다.

void insertionSort(int arr[], int size) {
    int i, j, key;

    for (i = 1; i < size; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

 

시간복잡도

선택 정렬과 버블 정렬은 항상 n^2의 시간복잡도를 갖지만 삽입정렬은 조금 다릅니다. 삽입 정렬은 평균적으로 n^2이지만 만약 정렬된 원소들로 구성된 배열이 입력으로 들어오면 n^2의 시간 복잡도를 갖습니다. for 루프안의 반복문이 1회만 실시하고 말거든요. 바로 현재 키보다 작은 원소를 만나기 때문입니다. 아래의 표로 쉽게 확인해보세요.

 

정렬 알고리즘   최적의 경우 평균적인 경우  최악의 경우 
 Selection Sort  n^2  n^2  n^2
 Bubble Sort  n^2  n^2  n^2
 Insertion Sort  n  n^2  n^2

 

 

전체코드

확인하기 쉽도록 전체코드를 올립니다.

#include <stdio.h>

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void selectionSort(int arr[], int size) {
    int minIndex;
    int i, j;
    for (i = 0; i < size - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < size; j++)
            if (arr[j] < arr[minIndex])
                minIndex = j;

        swap(&arr[i], &arr[minIndex]);
    }
}
void bubbleSort(int arr[], int size) {
    int i, j;
    for (i = size - 1; i > 0; i--)
        for (j = 0; j < i; j++)
            if (arr[j] > arr[j + 1])
                swap(&arr[j], &arr[j + 1]);
}

void insertionSort(int arr[], int size) {
    int i, j, key;

    for (i = 1; i < size; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}


void printArr(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr1[] = { 9,8,1,3,2 };
    int arr2[] = { 9,8,1,3,2 };
    int arr3[] = { 9,8,1,3,2 };
    int size = 5;
    printArr(arr1, size);
    selectionSort(arr1, size);
    printArr(arr1, size);
    printf("\n");

    printArr(arr2, size);
    bubbleSort(arr2, size);
    printArr(arr2, size);
    printf("\n");

    printArr(arr3, size);
    insertionSort(arr3, size);
    printArr(arr3, size);

    return 0;
}

 

정렬 알고리즘에는 이 밖에도 병합정렬, 퀵정렬, 힙정렬 등이 있습니다. 일단 이것부터숙지하도록 합시다.

 

반응형
블로그 이미지

REAKWON

와나진짜

,

배낭 알고리즘(Knapsack algorithm)

 

알고리즘에서 DP를 배울때 등장하는 유명한 문제가 있습니다. 제목과 같이 바로 배낭알고리즘이지요. 배낭알고리즘도 여러가지가 있지만, 우리는 조건이 가장 간단한 0/1 배낭 알고리즘 문제를 알아보도록 하겠습니다.

 

상황은 이렇습니다.

어떤 REAKWON이라는 이름의 도둑놈이 있습니다. 이 도둑은 새벽 늦은 시간 도둑질을 하기 위해서 남의 집에 들어가는데 까지는 성공했습니다. 그리고 훔쳐갈 물건들을 담기 위해 배낭도 챙겼지요. 데헷

하지만 이 도둑은 안타깝게도 아이큐가 70입니다. 배낭의 용량은 한정되어 있고 무거우면 들고갈 수도 없으므로 가장 값어치가 비싸고, 무게가 적은 물건들을 최대한 많이 담아가야합니다.

하지만 조건이 있습니다.

1) 물건을 부분적으로 담을 수는 없습니다.

2) 물건들은 모두 한개씩만 있습니다. 예를 들어 똑같은 반지가 2개일 수 없다는 이야기입니다.

 

도둑은 현재 15의 무게를 담을 수 있는 배낭을 가지고 있습니다. 그리고 아래와 같이 그 집의 물건이 있지요. 

 

items 

 weight

 value

 [0]

 5

 8

 [1]

 8

 11

 [2]

 3

 3

 [3]

 4

 6

 [4]

 2

 4

 

 

이 상황에서 도둑이 훔쳐갈 수 있는 최대의 값을 구하는 것입니다.

 

어떻게 도둑을 도와줄것인가?

아 그냥 무게가 가장 적은거 순서대로 훔쳐가면 되지 않을까요?

라고 생각하신다면 다시 한번 생각해봅시다.

위의 물건들을 가장 작은 무게가 나가는 것을 훔쳐가게 된다면 items[4], items[2], items[3], items[0]만 가져갈 수 있고, 총 가치는 21이 되고 총 용량은 14가 됩니다.

하지만 items[0], items[1], items[4]를 선택한다면 총 가치는 23이 되고, 용량은 15로 더 비싼물건을 훔칠 수 있습니다.

 

그렇기 때문에 무게가 덜 나가는 순으로 정렬해서 문제를 해결할 수가 없는것이죠.

그래서 단순 무식하게 한번 접근해봅시다.

도둑은 그 물건을 훔쳐갈 수 있느냐, 훔쳐갈 수 없느냐 이 둘만 고려합니다. 

 

1) 훔쳐갈때 

만약 어떤 물건을 훔쳐갈 수 있다고 한다면 현재 무게가 그 물건의 무게만큼 무거워지요. 하지만 배낭 용량을 초과할 수는 없습니다. 그럴땐 그 물건을 배낭에 담을 수가 없습니다.

현재 그 물건들을 배열로 표현(items)하고, 어떤 물건을 고려 할때 그 아이템의 인덱스를 pos라고 합시다. 그리고 현재 용량을 capacity라고 해봅시다. V는 그 물건의 가치, W는 그 물건의 용량이라고 친다면 우리는 이런 식을 쓸 수 있습니다.

 knapsack(pos + 1, capacity - items[pos][W]) + items[pos][V]

 

knapsack이라는 함수는 현재 물건 이후 가장 큰 값을 반환합니다. 그러니까 당연히 용량(capacity)는 그 물건의 무게(items[pos][W])만큼 줄어들 것이고, 그 반환된 가장 큰 값에서 현재 물건의 가치를 더함으로써 지금 이 물건을 훔쳤을때 얻을 수 있는 값을 얻을 수 있습니다.

 

 

2) 훔쳐가지 않을 때

그리고 또 그냥 그 물건을 안가져갈 수도 있습니다. 그럴때는 현재 무게가 그대로 유지되면서 다음 물건을 고려하는 겁니다.

 

그러니 아래의 식이 가능합니다.

 

knapsack(pos + 1, capacity )

 

 

1)훔쳐갈 경우2)훔쳐가지 않을 경우 중에서 가장 큰 값이 우리가 원하는 답이 되는 것이죠.

 

코드

이런 프로그램을 구현한 것이 바로 아래 소스 코드입니다.

 

#include <stdio.h>
#define W 0
#define V 1
#define N 5
#define MAX(a,b) a>b ? a:b;

int items[N][2] = {
	,
	,
	,
	,
	
};

int knapsack(int pos,int capacity) {
	if (pos == N) return 0;
	
	int ret = 0;
	if (items[pos][W] <= capacity) //지금 pos의 물건을 훔칠 수 있을때
		ret = knapsack(pos + 1, capacity - items[pos][W])
		+ items[pos][V];
        //지금 pos의 물건을 훔치지 않을때와 ret 중에 큰 값
	ret = MAX(ret, knapsack(pos + 1, capacity)); 
	return ret;
}
int main() {
	int capacity = 15;
	printf("knapsack(%d,%d)=%d\n",0,capacity, knapsack(0, capacity));
	return 0;
}

답은 원하는 결과대로 나옵니다.

 

허나 이런 무식한 해결방법을 원한 것을 아닙니다.

만약 물건의 수가 많게 된다면 답을 구하기 전에 도둑은 감방으로 직행하게 될 것입니다. knapsack함수는 분명 같은 값을 여러번 중복해서 계산합니다. knapsack(pos,capacity)에서 같은 pos와 같은 capacity가 이전에 계산했었음에도 불구하고 또 다시 한번 더 계산한다는 것이죠.

 

그래서 DP가 사용됩니다. 단지 계산된 결과를 기억하고 있다가, 같은 계산을 수행할때 바로 값을 반환해주면 됩니다.

 

아래의 수정된 코드처럼 말입니다.

 

#include <stdio.h>
#include <stdlib.h>
#define W 0
#define V 1
#define N 5
#define MAX_CAPACITY 1000
#define MAX(a,b) a>b ? a:b;

int dp[N][MAX_CAPACITY];
int items[N][2] = {
	,
	,
	,
	,
	
};

int knapsack(int pos,int capacity) {
	if (pos == N) return 0;
	
	int ret = dp[pos][capacity];
	if (ret != -1) return ret;
	if (items[pos][W] <= capacity)
		ret = knapsack(pos + 1, capacity - items[pos][W])
		+ items[pos][V];
	ret = MAX(ret, knapsack(pos + 1, capacity));
	return dp[pos][capacity]=ret;
}
int main() {
	int capacity = 15;
	memset(dp, -1, sizeof(dp));

	printf("knapsack(%d,%d)=%d\n",0,capacity, knapsack(0, capacity));
	return 0;
}

우선 dp라는 2차원 배열을 -1로 셋팅합니다. 그리고 dp[pos][capacity]가 -1이 아니면 바로 그 값을 반환합니다. 배낭문제에서 음수는 나올 수 없습니다. 만약 계산되지 않은 값이라면 계산 후 dp[pos][capacity]에 값을 넣어주는 것입니다. 기억하고 있습니다.

 

결국 도둑은 가장 비싼 물건들을 훔쳐갈 수 있었지만, CCTV에 걸려 감방에 끌려가게 됩니다. 그걸 도와준 저도 같이 갑니다.

반응형
블로그 이미지

REAKWON

와나진짜

,

1912번 연속합



문제 해석


수열에서 연속된 수들의 합이 가장 큰 것을 구하는 문제입니다.


10, -4, 3, 1, 5, 6, -35, 12, 21, -1 라는 수열에서 가장 큰 연속은 얼마일까요?

12, 21 부분이 가장 큰 연속합입니다.


연속합의 수들은 한개 이상이라는 점입니다.


제약 조건
100,000개의 수들이 주어지고 각각의 수는 -1000~1000의 크기를 갖습니다.




풀이

쉬워보입니다.


처음 시작점을 고정하고 끝점을 하나씩 늘려가면서 시작점과 끝점을 전부 더하는 거죠. 전부 현재의 최대값과 비교해서 크면 그게 최대값이 되는 식으로요.


#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int nums[100001];

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &nums[i]);

	int ans = -1001;
	for (int start = 0; start < n; start++) {
		for (int end = start; end < n; end++) {
			int sum = 0;
			for (int i = start; i <= end; i++)
				sum += nums[i];
			ans = max(sum, ans);
		}
	}
	printf("%d\n", ans);
}
	

네, 이렇게 제출하면 시간초과랍니다. 하하

입력이 자그마치 10만개가 되거든요.


단순히 이렇게 for루프만 돈다면 문제를 해결할 수가 없습니다.


여기서 간단한 이론(?)이 있는데요.

부분합이라는 개념이 여기 사용됩니다.


우리는 전에 계산한 합을 이용할 수 있다는 거죠.



[0] 

[1] 

[2] 

[3] 

[4]

[5] 

 [6]

[7] 

[8] 

[9] 

10

-4 

3 

1 

5 

6 

-35 

12 

21 

-1 

10

6 

9 

10 

15 

21 

-14 

-2 

19 

18 



[0]~[5]까지의 합은 [0]~[4]까지의 합 + 현재의 수를 더하면 된다는 것을 알 수 있습니다.


코드로 본다면 이런 형태이죠.

for (int i = 1; i <= n; i++)
		partialSum[i] = partialSum[i - 1] + numbers[i];

i가 1부터 시작한 이유는 조금 더 보기 편하게 하기 위함입니다. 그러니까 n까지 for루프를 돌아야 됩니다.


그렇다면 [7]~[8]까지의 합만을 구하려면 어떻게 할까요?

partialSum[8]-partialSum[6]을 하게 되면 [7]과 [8]의 부분합만을 구할 수 있습니다.




그럼 1부터 3까지의 합은 partialSum[3]-partialSum[0]이 되겠죠? 인덱스를 왜 1부터 시작하는 지 이유를 알 것 같습니다. 그렇지 않으면 if문을 사용해야합니다.


이제 우리는 위의 코드를 2개의 for문으로 줄일 수 있습니다.



#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int partialSum[100001];

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int number;
		scanf("%d", &number);
		partialSum[i] = partialSum[i - 1] + number;
	}
	int ans = -1001;
	for (int start = 0; start <= n-1; start++) {
		for (int end = start + 1; end <= n; end++) {
			ans = max(ans, partialSum[end] - partialSum[start]);
		}
	}
	printf("%d\n", ans);
}
	



부분합을 이용해서 이중 for문으로 문제에 접근할 수도 있지만, 이 역시 시간초과가 됩니다. 아까 말한것 처럼 입력이 10만개이기 때문에 이중 for문 역시 시간초과죠.


여기서 한 번 더 줄일 수 없을까요?

부분합을 이용해서 말이죠. 


그전까지 계산한 부분합 + 지금 숫자가 지금 숫자보다 작다면 부분합은 다시 계산 되어야 한다는 것을 직관적으로 느낄 수 있을까요??


그러니까...


현재의 수를 numbers[i]라고 하고 그 전까지 계산했던 부분합이 partialSum[i-1]라고 할때 , partialSum[i]=max(partialSum[i-1]+numbers[i], numbers[i]) 라고 하는 것 말이에요.


다시말해,


partialSum[i]=max(partialSum[i-1]+numers[i], numbers[i])

                =max(지금까지의 부분합, 현재 수)

라고 하는 것이 이해가 가시나요?


지금까지 구한 부분합이 현재의 수보다 작다면 현재의 수부터 다시 부분합을 계산하는 것이 더 클 거니까요.


이것만 이해가 간다면, 다음의 코드는 이 과정을 배열없이 구현했다라는 것을 알 것입니다.




#include <cstdio> #include <algorithm> using namespace std; int main() { int n, partialSum = 0, maxPartialSum = -1001; scanf("%d", &n); for (int i = 1; i <= n; i++) { int number; scanf("%d", &number ); partialSum = max(number, number + partialSum); maxPartialSum = max(partialSum, maxPartialSum); } printf("%d\n", maxPartialSum); }

코드가 무척이나 짧아졌습니다.

문제의 답은 maxPartialSum입니다. 


코드에서 이 부분을 보세요.


partialSum = max(number, number + partialSum);


number는 현재의 수를 말하는 것이고, partialSum은 이전까지 계산했던 부분합을 의미합니다.

현재의 수와 이전까지 계산했던 부분합 + 현재의 수가 현재의 수보다 작다면 부분합은 다시 현재의 수부터 시작입니다.


이후 이 부분합(partialSum)과 지금까지 부분합의 최대값(maxPartialSum)을 비교해서 큰 값이 다시

maxPartialSum이 되는 것입니다.

반응형
블로그 이미지

REAKWON

와나진짜

,

2178번 미로탐색



문제 해석



추석인데 할게 없으니, 알고리즘 하나 풀어보자구요!

NxM행렬이 있습니다. N은 행의 수, M은 열의 수인데, 1은 통과 가능한 구역, 0은 통과하지 못하는 공간이라고 문제 설명에서 말합니다.

(1,1)부터 시작해 (N,M)까지 오는데, 가장 적게 1을 통과하는 수를 구하는 게 문제의 답입니다.


아래처럼 빨간 색으로 된 1을 통과하는 게 답이 되겠고, 15가 답이 됩니다.

1 

0

 1

 1

 1

 1

1

0

 1

 0

 1

 0

1

0

 1

 0

 1

 1

1

1

 1

 0

 1

 1



물론 답은 여러가지가 있을 수도 있겠죠?

위에 빨간점대로 이동하지 않고도 녹색점을 거쳐서 오는 경우도 가능한데, 어차피 답은 똑같다라는 점입니다.

한칸 띄어서 정수형으로 주지 귀찮게




제약 조건
N과 M 둘 다 2이상 100이하가 되겠습니다. 


풀이
음...
최소라... 

일단 어떤 지도같은 것을 주고, "최단거리를 구하라" 라는 문제는 BFS로 풀어볼만 합니다. BFS가 최단 거리를 구하는데 안성맞춤이거든요. 어떤 정점이 있을때 그 주위에 있는 정점들만 우선적으로 돌기 때문이지요.

그리고 N과 M, 모든 점을 계산했을 때 10000개 이하가 되니까 Queue에 담기도 충분합니다.


우선 어떤 점 (y,x)가 있을때, 사방에 1인 녀석들을 일단 찾습니다. 그놈들이 그래프의 정점 중 다음에 방문해야할 후보들에 속하거든요.
그렇다면 상하좌우이니까 (y, x-1), (y, x+1), (y+1, x), (y-1, x)로 주변 정점들을 찾고 이미 방문된 정점이라면 그냥 skip하면 되겠네요.




#include <cstdio>
#include <queue>
#include <string>
#include <string.h>

using namespace std;

int n, m;
bool visited[101][101];
char map[101][101];

struct Point {
	int x, y;
	Point(int _y, int _x) {
		x = _x; y = _y;
	}
};

queue<Point> q;

void pushQ(int y, int x) {

	if (y >= n || x >= m || y<0 || x<0 || visited[y][x] || map[y][x] == '0') return;
	q.push(Point(y, x));

	visited[y][x] = true;
}

int bfs() {

	pushQ(0, 0);
	int count = 1;
	while (!q.empty()) {

		int size = q.size();

		for (int i = 0; i<size; i++) {
			Point here = q.front();
			q.pop();

			if (here.y == n - 1 && here.x == m - 1) return count;

			pushQ(here.y + 1, here.x);
			pushQ(here.y - 1, here.x);
			pushQ(here.y, here.x + 1);
			pushQ(here.y, here.x - 1);
		}
		count++;
	}
	return count;
}

int main() {
	scanf("%d %d", &n, &m);

	memset(visited, false, sizeof(visited));
	for (int i = 0; i < n; i++)
		scanf("%s", map[i]);

	printf("%d\n", bfs());
	return 0;
}


위 코드는 단순하게 (0,0) (문제에서는 1,1라고 했지만, 배열은 0,0부터 첫번째 요소이기 때문에)부터 시작해서 (n-1, m-1)( 역시 배열의 가장 마지막 요소는 n-1, m-1)까지 문자열로 입력을 받고,  bfs를 돕니다.


bfs에서는 우선 시작 정점(0,0)을 큐에 집어 넣습니다. 그 후에 bfs의 size를 호출해 포문을 돌고 그 상하좌우의 정점을 집어 넣게 되는 겁니다. 주의해야할 점은 for루프 조건문에서 직접적으로 q.size()를 호출하면 안된다는 점입니다. for루프 안에서 q에 push되므로 for문을 한번 돌때마다 q.size()가 유동적으로 바뀌게 됩니다.

                int size = q.size();

		for (int i = 0; i<size; i++) {
			Point here = q.front();
			q.pop();

			if (here.y == n - 1 && here.x == m - 1) return count;

			pushQ(here.y + 1, here.x);
			pushQ(here.y - 1, here.x);
			pushQ(here.y, here.x + 1);
			pushQ(here.y, here.x - 1);
		}
		count++;

그렇게 for문을 한 번 돌면 그 주위에 있는 정점 한번을 탐색한 것이니까 count를 하나 증가시켜 주고요. 만약 n-1, m-1 정점까지 도달했다면 바로 이 count를 return하게 되면 몇 번만에 (n-1, m-1)까지 도달했는지 알 수 있습니다.




pushQ함수는 조건에 맞지 않는 정점은 그냥 지나쳐 버립니다.

조건에 맞지 않는 정점이라는 것은 범위밖의 정점( 0보다 작거나 n또는 m보다 큰 정점), 이미 방문된 정점, 또는 0인 정점을 말하는 것이죠.

방문해야 할 정점이라면 큐에 push하고 방문되었다는 표시만 해주는 아주 단순한 함수입니다. visited[y][x] = true가 바로 방문되었다는 표시를 해주는 작업이랍니다.


단순하긴 하지만 이 함수가 없다면 for루프 안에 일일히 if문으로 검사를 해주어야하는 뻘짓을 하게 될겁니다.

void pushQ(int y, int x) {

	if (y >= n || x >= m || y<0 || x<0 || visited[y][x] || map[y][x] == '0') return;
	q.push(Point(y, x));

	visited[y][x] = true;
}

그리고 또 한가지는 pushQ를 총 4번 호출하죠?

for문으로 돌릴 수 있으나, 거기까지 생각하면서 귀찮게 코딩 안하잖아요 우리는...

그냥 짧은거는 복붙합시다... 티도 안나요.


점(point)을 조금 편하게 관리하게 위해서 Point라는 구조체를 사용했습니다.

뭐... 사용하지 않고 그냥 배열로만 해도 상관없구요.


십쥬?

반응형
블로그 이미지

REAKWON

와나진짜

,

1463번 1로 만들기


문제 해석


문제는 너무 간단 합니다. 세가지 규칙이 있는데요.

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.


이렇게 만들어서 1로 만들어라 이겁니다. 12를 최소로 위 규칙을 사용하면 어떤 과정을 거칠 수 있을까요?

12 - 4(1번 규칙 적용) - 2(2번 규칙 적용) - 1(2번 또는 3번 규칙 적용)

이렇게 3번으로 1을 만들 수 있다는 건데요. 


36은 어떻게 구할 수 있을까요?

36 - 12(1번 규칙 적용)

12는 위에서 구했습니다. 감이 오시죠? DP냄새가 나지 않습니까?





제약 조건
n은 1000000이하네요. O(n^2) 이상으로는 풀 수 없습니다.

풀이
 
세가지 조건과 메모이제이션을 이용해서 이 문제를 풀 수 있습니다. 


#include <cstdio>
#include <string.h>

#define min(x,y) x<=y ? x:y
#define INF 987654321
using namespace std;

int dp[1000001];

int solve(int n) {

	if (n == 1) return 0;
	if (dp[n] != -1) return dp[n];

	int ret = INF;
	if (n % 2 == 0) ret = 1 + solve(n / 2);
	if (n % 3 == 0) ret = min(ret, 1 + solve(n / 3));
        //ret = min(ret, 1+solve(n-1));
	if (n % 6 != 0) 
		ret = min(ret, 1 + solve(n - 1));

	return dp[n] = ret;
}

int main() {

	int n;
	scanf("%d", &n);

	memset(dp, -1, sizeof(dp));
	printf("%d\n", solve(n));
}




n을 규칙대로 3으로 나누어 떨어지면 3으로 나누고, 2로 나누어 떨어지면 2로 나누고, 또는 1을 뺀 규칙을 적용해서 1로 만들어보는 것입니다. 3으로 나누어 떨어지지 않거나, 2로 나누어 떨어지지 않을 땐 1을 빼는 규칙을 적용해줍니다.

왜요?

n을 1로 만들어주는데 있어서 2와 3으로 나누는 것이 유리하다는 것이죠. 어떤 수로 나누는 것이 n을 줄이는 일에 효과적이라는 겁니다. 그래서 1을 최소로 빼주고 될 수 있으면 2와 3으로 나누는 편이 더 좋습니다.  그러니 2와 3의 최소 공배수 6을 이용해서 6으로 나누어 떨어지지 않으면 1을 빼는 것을 시도하는 것입니다.


위 코드의 주석을 해제하고 if문 부분을 주석처리하여 제출해보세요. 결과는 맞지만 효율성에서 차이가 나는게 보일겁니다.

반응형
블로그 이미지

REAKWON

와나진짜

,

BOJ [1260] DFS와 BFS



문제해석


그래프를 DFS와 BFS 순으로 탐색한 결과를 반환하면 되겠습니다.


제약조건


간선 M은 10000개 이하, 정점 N은 1000 이하입니다.

그냥 묻지도 따지지도 않고 DFS, BFS 오지게 코딩하시면 됩니다.


문제풀이



DFS와 BFS에 대한 설명은 아래의 링크를 통해서 확인해주세요.


DFS https://reakwon.tistory.com/4?category=300866

BFS https://reakwon.tistory.com/7?category=300867





코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

vector<int> dfs_order = vector<int>();
vector<int> bfs_order = vector<int>();
vector<bool> visited;
int map[1001][1001];

int V,E;

void dfs(int here) {
	
	visited[here] = true;
	dfs_order.push_back(here);

	for (int to = 1; to<=V; to++) 
		if (!visited[to] && map[here][to] == 1) 
			dfs(to);
}

void bfs(int start) {

	queue<int> q;
	q.push(start);
	bfs_order.push_back(start);
	visited[start] = true;

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		for (int next = 1; next<=V; next++) 
			if (!visited[next] && map[here][next] == 1) {
				q.push(next);
				bfs_order.push_back(next);
				visited[next] = true;
			}
	}
}

void print_order(vector<int> &order) {
	for (int i = 0; i < order.size(); i++)
		printf("%d ", order[i]);
	printf("\n");
}


int main() {
	
	scanf("%d %d", &V, &E);

	int start;
	scanf("%d", &start);
	for (int i = 0; i<E; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		map[a][b] = map[b][a] = 1;
	}

	visited = vector<bool>(V + 1);
	dfs(start);
	visited = vector<bool>(V + 1);
	bfs(start);

	print_order(dfs_order);
	print_order(bfs_order);

}

dfs_order와 bfs_order는 각각 dfs 순으로 방문된 순서를 저장하는 벡터, bfs 순으로 방문된 순서를 저장하는 벡터입니다.



반응형
블로그 이미지

REAKWON

와나진짜

,

1012번 유기농 배추



문제 해석


문제는 여러가지 방법으로 풀 수 있습니다.

문제는 간단히 말해 이렇답니다.



그냥 1이 뭉쳐저 있는 곳을 세는 겁니다. 

단, 1은 상하좌우를 통해서 연결되어 집니다. 대각선으로 1은 서로 다른 지역으로 인식하게 되는 겁니다.


위의 예제에서는 1이 뭉쳐져 있는 곳이 총 5부분입니다. 그래서 답이 5가 되는 것입니다.




이런 문제는 조금 흔한 문제라서 딱 보면 그거네~ 하실 거에요.


제약 조건


테스트케이스 T가 주어지고 N과 M은 1이상 50 이하입니다. 배추가 심어져 있는 점은 Y, X로 주어집니다.


최대 50*50이 주어질 수가 있겠군요. 



풀이


이 유기농배추가 있는 지도를 그래프로 생각을 해보도록 하겠습니다. 탐색 방법은 어떤 방향이든 좋습니다. 하지만 상하좌우 네 방향을 전부 탐색해야합니다. 단, 1인 정점만 탐색합니다.



현재 위치를 y,x라고 치고 상하좌우를 탐색합니다. 위쪽 정점은 현재 정점의 y-1, x 아래 정점은 현재 정점의 y+1,x, 왼쪽 정점은 현재 정점의 y, x-1, 오른쪽 정점은 현재 정점의 y, x+1입니다.


하지만 이미 방문되었다면 그 정점은 탐색하지 않습니다.


따라서 dfs가 몇번 호출되었는가가 이 문제의 답이됩니다. 코드를 통해서 살펴보도록 할까요?





#include <cstdio>
#include <string.h>
#define M 51
#define VISITED 0
using namespace std;

int n, m, k;
int map[M][M];

void dfs(int y, int x) {
	
	if ( y<0 || y >= n || x < 0 || x >= m || map[y][x] == VISITED )
		return;

	map[y][x] = VISITED;
	dfs(y + 1, x);	dfs(y, x + 1);
	dfs(y - 1, x);	dfs(y, x - 1);
}

int main() {
	int T;

	scanf("%d",&T);
	for (int t = 0; t < T; t++) {

		memset(map, 0, sizeof(map));

		scanf("%d %d %d", &m, &n, &k);
		for (int i = 0; i < k; i++) {
			int y, x;
			scanf("%d %d", &y, &x);
			map[x][y] = 1;
		}

		int count = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++)
				if (map[y][x] == 1) {
					dfs(y, x);
					count++;
				}
		}
	
		printf("%d\n", count);
	}
}


이중 for문을 돌며 1이 등장하면 그 정점부터 dfs를 실행합니다.  dfs는 그 정점이 0이거나 y, x가 범위 밖이면 바로 return 됩니다.

그렇다면 우리는 그냥 0을 방문되었다고 표현하면 더 간단하게 문제를 풀 수 있지 않을까요?



아래 사진처럼 0,0에서 1을 만났다고 치겠습니다. 그렇다면 그 지점 0,0에서 dfs를 수행하면 앞뒤 양옆을 dfs로 순차적으로 돌아 전부 방문됩니다. 그러면 0으로 값이 변하게 되지요. 이 부분이 두번째 사진의 빨간색으로 된 0으로 표현을 했네요.




dfs가 끝났으니 for문을 계속 수행합니다. 하지만 이미 dfs가 돌아 0으로 값이 변했으므로 skip됩니다.






이런 식으로 dfs를 한번 돌게 되면 하나의 덩어리를 구할 수 있습니다. 이 덩어리의 수를 세는 것이 답입니다.


답은 위 코드의 count로 표현됩니다.


시간 복잡도는 N*M이 됩니다. 


이외에도 BFS를 통해서도 문제의 해답을 구할 수도 있습니다. 

마찬가지로 for문 속에서 일일이 루프를 돌면서 아직 방문되지 않는 점이 있으면 bfs를 돌고 count에 1을 더해 주기만 하면 되거든요.


BFS나 DFS나 둘 중 하나만 알아도 이 문제는 풀 수 있습니다.


또 어떤 방법으로 풀 수 있을까요??




반응형
블로그 이미지

REAKWON

와나진짜

,