'알고리즘'에 해당되는 글 34건

14499번 주사위 굴리기

https://www.acmicpc.net/problem/14499

문제 해석

어떤 판 위에 주사위가 있습니다. 이 판에는 임의의 숫자가 적혀있습니다. 주사위를 입력받은 방향으로 굴리면서 주사위 윗면의 숫자를 조건에 따라 출력해주는 문제입니다. 규칙을 따져보자면 이렇습니다.

1. 처음 주사위의 모든 면에는 0이 쓰여있습니다. 그러니까 처음 6면에는 모두 0인 수가 적혀있는 것이죠.

2. 주사위가 굴러가면서 주사위 아랫면에 판의 숫자가 쓰여집니다. 단, 판의 숫자가 0일때는 주사위 윗면의 숫자를 출력해줍니다.

3. 만약 주사위가 판의 범위에서 나가는 입력이 들어왔을때는 깔끔하게 무시해주면 됩니다.

제약 조건

판의 가로(N), 세로(M) 크기는 1이상 20이하, 그리고 주사위를 어느 방향으로 굴릴지에 대한 입력은 1이상 1000이하로 들어옵니다. 주사위의 처음 위치는 판의 범위에 있어야하므로 좌표의 위치(x,y)는 0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1 입니다.

풀이

문제의 조건이 약간 이상하긴 합니다. 보통 x는 가로, y는 세로를 문제로 주고 역시 n도 세로의 길이, m도 가로의 길이로 주는게 조금 일반적이거든요.

그래서 저는 y를 세로 좌표, x를 가로 좌표로 두고 문제를 풀겠습니다.

우선 주사위를 어떻게 굴릴지 머리부터 굴려봅시다. 우선 전개도로 어떻게 주사위를 굴려볼까 봅시다. 

그림에서 가장 가운데 주사위의 전개도가 초기의 주사위입니다. 분홍색이 아랫면, 주황색이 윗면이라고 가정하지요. 주사위의 왼쪽면은 왼쪽 날개, 오른쪽 면은 오른쪽 날개라고 가정한다면 가운데의 주사위 전개도의 모든 면은 이렇게 되겠네요.

0번: 뒷면, 1번: 아랫면, 2번: 앞면, 3번: 윗면, 4번: 왼쪽면, 5번: 오른쪽면

그렇죠?

우리는 이것을 배열 인덱스로 생각해야합니다. 그러니 전개도의 숫자는 적혀져있는 숫자가 아니고 자리를 나타냅니다.

만약 이 상태에서 오른쪽으로 주사위를 굴린다면 0번 자리에 있던 수는 그대로 0번 자리에 있던 수가, 기존 1의 위치에는 5번의 자리에 있는 수가, 기존 2의 자리에는 그대로 2의 자리에 있던 수가, 기존 3의 자리에는 4의 자리에 있던 수가, 기존 4의 자리에는 1의 자리에 있던 수가, 기존 5의 자리에는 3의 자리에 있던 수가 됩니다. 숫자들이 자리를 찾아 이동하게 된것이죠.

정리하자면 이렇습니다.

이처럼 오른쪽으로 이동할때 5번째 자리에 있던 숫자는 1번째 자리로 이동하며, 4번째 자리에 있던 숫자는 3번째 자리로 이동합니다.

그렇게 위로 굴렸을때, 아래로 굴렸을때, 왼쪽으로 굴렸을때, 오른쪽으로 굴렸을때는 위의 그림의 전개도와 같습니다.

자, 이것을 이제 배열로 표현해보지요.

int dice[6];
int perm[5][6] = {
	{},
	{ 0,5,2,4,1,3 },{ 0,4,2,5,3,1 },
	{ 3,0,1,2,4,5 },{ 1,2,3,0,4,5 }
};

주어지는 입력에서 주사위를 굴릴때 동쪽은 1(오른쪽으로 굴릴 때), 서쪽은 2(왼쪽으로 굴릴 때), 북쪽은 3(위쪽으로 굴릴때), 남쪽은 4(아래쪽으로 굴릴 때) 이니까 그 순서대로 배열에 초기화했습니다. 0번은 동서남북으로 쓰여지 않으니 비어두었습니다.

그리고 dice라는 배열은 실제 주사위를 의미합니다. 여기에 주사위에 실제 적혀있는 숫자가 저장이 되죠.

이제 perm이라는 2차원 배열과 dice가 어떻게 동작하게 될까요? 우선 주사위 dice에는 다음과 같이 {5, 4, 3, 6, 8, 9}라는 수가 적혀져있다고 가정해보겠습니다. 이것을 오른쪽으로 굴리면 dice의 숫자는 어떻게 변할까요?

dice는 perm의 값의 따라 위치를 찾아 이동합니다. 오른쪽으로 이동할때 0번의 숫자는 0번으로, 5번의 숫자는 1번으로, 2번의 수는 2번으로, 4번의 수는 3번으로, 1번의 수는 4번으로, 3번의 수는 5번으로 이동하게 됩니다.

코드로 구현하면 이렇습니다.

void roll(int d) {
	int temp[6];
	for (int i = 0; i < 6; i++)
		temp[i] = dice[perm[d][i]];
	for (int i = 0; i < 6; i++)
		dice[i] = temp[i];
}

roll이라는 함수는 방향 d를 인자로 받습니다. 이렇게 d(1은 오른쪽, 2는 왼쪽, 3은 위쪽, 4는 아래쪽)에 따라서 perm을 결정하고 어떻게 dice를 배열할지를 정하게 됩니다. 

이를 토대로 이제 전체 문제를 풀면 됩니다.

int map[21][21], command[1001], n, m, k;
int perm[5][6] = {
	{},
	{ 0,5,2,4,1,3 },{ 0,4,2,5,3,1 },
	{ 3,0,1,2,4,5 },{ 1,2,3,0,4,5 }
};

int inc[5][2]{ {},{ 0,1 },{ 0,-1 },{ -1,0 },{ 1,0 } };
int dice[6];

void roll(int d) {
	int temp[6];
	for (int i = 0; i < 6; i++)
		temp[i] = dice[perm[d][i]];
	for (int i = 0; i < 6; i++)
		dice[i] = temp[i];
}


void solve(int next, int y, int x) {
	if (next == k) return;
	int dir = command[next];
	int Y = y + inc[dir][0], X = x + inc[dir][1];
	if (Y < 0 || Y >= n || X < 0 || X >= m) {
		solve(next + 1, y, x);
		return;
	}

	roll(dir);
	if (map[Y][X] == 0) map[Y][X] = dice[1];
	else {
		dice[1] = map[Y][X];
		map[Y][X] = 0;
	}
	printf("%d\n", dice[3]);
	solve(next + 1, Y, X);
}

solve라는 함수가 이제 문제를 푸는 재귀함수입니다. 인자 next는 다음 방향으로 이동하라는 인덱스입니다. 이것을 comand가 사용합니다.

command라는 배열은 어떻게 이동할지를 담고 있는 변수입니다. 동서남북 이동이 그것이죠. 동서남북 이동 입력이 1000개가 주어지니 command의 배열을 1000+1개로 잡아놓았습니다.

inc는 어떻게 주사위 위치를 증가할지를 담고 있는 변수입니다. inc는 방향에 따라서 (1,2,3,4) 1이이면 x축으로 1증가, 2이면 x축으로 1감소,.. 이런 식입니다.

solve함수에서 만일 범위 밖이면 다음 명령어를 실행하죠. 그것이 조건문에 걸려있군요. 조건에 걸리지 않았다면 주사위를 방향에 따라 굴리고, 이동했던 판의 숫자가 0이면 주사위의 아랫면의 숫자를 판에 복사하며 그것이 아니라면 판의 숫자를 주사위의 아랫면에 복사하고 그 판의 숫자를 0으로 바꾸어줍니다. 그 후 이제 윗면의 수 dice[3]을 출력하면 되지요.

전체 코드는 아래와 같습니다.

#include <cstdio>

using namespace std;
int map[21][21], command[1001], n, m, k;
int perm[5][6] = {
	{},
	{ 0,5,2,4,1,3 },{ 0,4,2,5,3,1 },
	{ 3,0,1,2,4,5 },{ 1,2,3,0,4,5 }
};

int inc[5][2]{ {},{ 0,1 },{ 0,-1 },{ -1,0 },{ 1,0 } };
int dice[6];

void roll(int d) {
	int temp[6];
	for (int i = 0; i < 6; i++)
		temp[i] = dice[perm[d][i]];
	for (int i = 0; i < 6; i++)
		dice[i] = temp[i];
}


void solve(int next, int y, int x) {
	if (next == k) return;
	int dir = command[next];
	int Y = y + inc[dir][0], X = x + inc[dir][1];
	if (Y < 0 || Y >= n || X < 0 || X >= m) {
		solve(next + 1, y, x);
		return;
	}

	roll(dir);
	if (map[Y][X] == 0) map[Y][X] = dice[1];
	else {
		dice[1] = map[Y][X];
		map[Y][X] = 0;
	}
	printf("%d\n", dice[3]);
	solve(next + 1, Y, X);
}

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

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

	for (int i = 0; i < k; i++) scanf("%d", &command[i]);
	solve(0, y, x);
}

2667 단지번호붙이기

문제 해석

가로 세로 크기가 5에서 25사이의 정사작형 배열에서 1이 뭉쳐져있는 구역을 구하고, 각 구역에서 1이 몇개나 있는지 오름차순으로 출력하라는 문제입니다.

1이 상하좌우에 있다면 그것은 같은 그룹에 속합니다. 아래 사진을 보세요.

<그림 1>에서 1의 그룹은 새 개의 구역으로 <그림 2>로 표현될 수 있습니다. 1번 그룹, 2번 그룹, 3번 그룹이 있고, 각각의 그룹은 7, 8, 9개의 1이 뭉쳐져있는 것이죠. 

입력은 가로, 세로의 길이가 주어지고, 위의 그림처럼 띄어지지 않은 문자열형태로 넘어옵니다. 이렇게 말이죠.

출력은 그룹의 갯수와 각 그룹이 포함하고 있는 1의 개수를 오름차순으로 출력합니다. 

풀이

DFS(Depth First Search)를 이용하면 쉽게 풀 수 있습니다. 우선 입력이 불친절하게 들어오니까 이를 정수형 배열로 바꾸어줍니다. 제가 문자 배열은 왠만하면 사용하기 싫거든요.

scanf("%d", &n);
for (int i = 0; i < n; i++) {
	char line[MAX_N];
	scanf("%s", line);
	for (int j = 0; j < n; j++) 
		map[i][j] = line[j] - '0';
}

배열의 길이 n을 입력받은 후에 for루프를 n번 돌면서 문자 배열 line으로 배열의 한줄을 입력받습니다. 그 for문의 내부 for문에서는 map배열에 실제 입력을 시킵니다. 그래서 map에는 입력들을 정수형 배열로 입력됩니다.

int cnt = 0;
for (int i = 0; i < n; i++) 
	for (int j = 0; j < n; j++) 
		if (map[i][j] == 1) {
			groups[cnt]=dfs(i, j);
			cnt = cnt + 1;
		}

입력을 받았으면 map을 전부 이중for문으로 돌며 1이 있는 부분에서 멈춥니다. 1이 있는 부분에서 멈추게 되면 그 지점에서 dfs를 호출하는 것이죠. dfs가 몇번 호출이 되느냐에 따라서 cnt가 커지게 됩니다. 바로 cnt가 그룹의 전체 갯수를 나타냅니다.

groups에는 cnt라는 그룹에 몇개의 1이 포함이 되어있는지 저장됩니다.

dfs에서 무슨 동작을 할까요? 이 문제를 풀기위한 핵심인 dfs를 보도록합시다.

int dfs(int y, int x) {
	if (y < 0 || x < 0 || y >= n || x >= n || map[y][x] == 0) return 0;
	map[y][x] = 0;
	return 1 + dfs(y + 1, x) + dfs(y - 1, x)
		+dfs(y, x + 1) + dfs(y, x - 1);
}

dfs함수는 바로 위와 같이 정의되어 있습니다. y는 행, x는 열만을 인자로 받아들이고 있습니다. y나 x가 배열 범위 밖에 있다면 더이상 dfs를 호출하지 않습니다. 또는 map[y][x]가 0인 부분도 기저사례에 포함이 됩니다. 지금까지 말했던 것들이 첫번째 if문의 조건이 되겠네요.

배열 범위에 포함이 되어있으며 map[y][x]=1이라면 바로 그 지점을 0으로 바꿔줍니다. 왜 바꿔주냐면 더 이상 이 점을 방문할 필요가 없으니까요. 만약 map[y][x]=0이 없다면 이 프로그램은 영원히 끝나지 않을겁니다.

그 후에는 상(y-1)하(y+1)좌(x-1)우(x+1)에 dfs를 호출합니다. return에 1을 더해야만 최종 dfs에는 그룹의 1의 개수가 return됩니다.

printf("%d\n", cnt);
sort(groups, groups + cnt);
for (int i = 0; i < cnt; i++) 
	printf("%d\n",groups[i]);

이제 답은 전부 구했네요. cnt를 출력하고 오름차순으로 1의 개수를 출력하라 하였으니 정렬 후에 groups를 출력하면 됩니다.

아래는 전체코드입니다.

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

#define MAX_N 26

int n;
int map[MAX_N][MAX_N];
int groups[MAX_N*MAX_N];
int dfs(int y, int x) {
	if (y < 0 || x < 0 || y >= n || x >= n || map[y][x] == 0) return 0;
	map[y][x] = 0;
	return 1 + dfs(y + 1, x) + dfs(y - 1, x)
		+dfs(y, x + 1) + dfs(y, x - 1);
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		char line[MAX_N];
		scanf("%s", line);
		for (int j = 0; j < n; j++) 
			map[i][j] = line[j] - '0';
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (map[i][j] == 1) {
				groups[cnt]=dfs(i, j);
				cnt = cnt + 1;
			}
		
	
	printf("%d\n", cnt);
	sort(groups, groups + cnt);
	for (int i = 0; i < cnt; i++) 
		printf("%d\n",groups[i]);
	
	return 0;
}

dfs만 알면 그리 어렵지 않게 풀수 있는 문제였습니다.

1697 숨바꼭질

문제 해석

수빈이가 동생을 찾아가는데 몇초만에 찾는지 알아내는 문제입니다. 수빈이와 동생은 점 0~100000사이에 있습니다. 근데 왜 수빈이만 동생을 찾는 건지는 이해가 가지 않는군요. 

수빈이는 다음과 같은 이상한 능력이 있습니다.

1. 수빈이가 위치 X에 있을때 1초에 X+1, X-1의 위치로 걸을 수 있습니다. 물론 범위 0~100000의 범위 안에서만 말이죠.

2. 수빈이는 순간이동을 할 수 있는데, 현재 위치 X에서 1초만에 X*2의 위치로 이동할 수 있습니다.

두개의 입력이 주어지는데, 가장 첫번째 입력은 수빈이의 위치, 두번째 입력은 동생의 위치입니다.

5와 17이라는 입력이 주어진다면 답은 4가 됩니다. 5->10->9->18->17로 찾을 수 있습니다.

이런 조건 속에서 몇 초만에 동생을 찾을 수 있을까요?

풀이

BFS(Breadth First Search)를 이용하면 이 문제를 풀 수 있습니다. 그 때문에 큐(Queue)를 이용해야합니다. 수빈이가 있는 점을 start라고 하고 동생이 있는 위치를 end라고 합시다. 결국 우리가 구현해야하는 것은 start에서부터 BFS를 통해 end까지 도달을 몇번에 할 수 있는가입니다.

아래의 전체적인 코드를 우선 보고 설명하도록 하겠습니다.

#include <cstdio>
#include <queue>

using namespace std;
#define MAX_N 100001
#define LIMIT 100000
int bfs(int start, int end) {
	if (start==end) return 0;
	queue<int> q;
	q.push(start);
	int length[MAX_N] = { 0, };

	while (!q.empty()) {
		int here = q.front();
		q.pop();
		if (here + 1 <= LIMIT) {
			if (here + 1 == end)
				return length[here] + 1;
			if (!length[here + 1]) {
				length[here + 1] = length[here] + 1;
				q.push(here + 1);
			}
		}
		if (here - 1 >= 0) {
			if (here - 1 == end) return length[here] + 1;
			if (!length[here - 1]) {
				length[here - 1] = length[here] + 1;
				q.push(here - 1);
			}
		}
		if (here * 2 <= LIMIT) {
			if (here * 2 == end) return length[here] + 1;
			if (!length[here * 2]) {
				length[here * 2] = length[here] + 1;
				q.push(here * 2);
			}
		}

	}
	return -1;
}
int main() {
	int start, end;
	scanf("%d %d", &start, &end);
	printf("%d\n", bfs(start, end));
	return 0;
}

LCS(Longest Common Subsequence)

백준 9251번입니다. 문제는 이렇습니다.

임의의 두 수열에서 공통적으로 갖고 있는 가장 긴 부분 수열의 길이를 구하는 것이 문제입니다.

예를 들어 다음과 같은 두 수열이 있다고 합시다.

첫번째 수열과 두번째 수열의 공통수열은 다음과 같습니다.

이 외에도 여러가지 공통 수열이 있지만 가장 긴 수열은 4의 길이를 갖고 있는 ACAK입니다. 두 수열에서 LCS는 여러가지가 있지만 그 길이는 같지요.

제약조건

두 수열을 항상 대문자 알파벳으로 주어지고 각 수열의 길이는 1이상 10000이하입니다.

풀이

이 문제는 생각보다 단순합니다. 두 수열의 문자를 비교해 일치하면 동시에 한칸을 옮겨서 그 다음부터 비교하면 되고, 만약 일치하지 않는다면 두 수열중 아무것이나 한칸 옮겨서 그 다음부터 비교하면 됩니다.

위 두 수열의 LCS길이는 AKEPPA 또는 OKEPPA입니다. 그렇기때문에 답은 6이 나오지요. 이 답이 나오는 과정을 살펴보도록 하겠습니다.

빨간색 글자는 현재 비교할 두 문자입니다. 우선 초기상태이므로 A와 O가 비교됩니다. 두 문자가 일치하지 않으므로 A의 다음 문자를 비교하거나 O의 다음 문자를 비교합니다. 저는 일부러 답을 찾기 위해서 최적의 방법을 사용할 것이니 여러분들은 두 수열 중 어떤 수열을 먼저 한칸 더 옮기든지 상관없다는 것만 아시면 됩니다.

첫번째 수열의 비교 문자를 한칸 옮기니까 두 수열의 문자가 일치하는 군요. 그렇다면 두 수열의 비교문자를 다음으로 옮겨줍니다.

L과 C는 일치하지 않으므로 두 수열중 비교할 문자를 한칸 뒤로 옮깁니다.

이런식으로 이제 계속 비교하다가 보면 언젠가는 다음과 같은 상황이 발생합니다.

이제 K와 K를 비교할 때가 된거죠. K는 두 수열이 두 수열의 비교문자를 모두 다음 위치로 이동합니다.

E 역시 두 문자가 같으므로 다시 또 한칸 동시에 비교문자를 옮깁니다. 옮기고 난 후 보니까 P와 M은 일치하지를 않지요. 그러니까 둘 중 아무 수열이나 비교할 문자를 한칸 옮겨줍니다. 저는 답을 찾기위해 일부터 아래 수열의 비교문자를 한칸 더 옮기겠습니다.

이제 P는 두 수열 모두 같으니 다음 칸으로 옮겨줍니다. 계속 이런식으로 답을 찾으면 결국 다음과 같은 LCS가 나오게 되는 것이죠.

이 LCS는 OKEPPA이고 길이가 6인 것을 알 수 있습니다. 따라서 답은 6이 되는 겁니다.

DP적용

이렇게 답은 찾았는데요. 길이가 10000인 두 수열을 이런식으로 계속 비교하다가는 시간안에 답을 찾기가 힘듭니다. 우리가 자세히 살펴본다면 DP를 적용할 수 있다는 사실을 알 수 있는데요. 만일 수열에서 순서가 A와 O를 비교했는데 아래 배열의 비교 문자를 옮긴다면 A와 C를 비교하게되어 O를 빠뜨리고 가지요. 분명 O는 일치하는 문자임에도요. 

[1][2][3][4][5][6][7][8][9][10]

A O L D M K E P P A

[1][2][3][4][5][6][7][8][9][10]

O C A C K E M P P A

그래서 결국 KEPPA까지만 일치하게 된 상황에서 각 인덱스는 [6][5]입니다. 

따라서 [6][5]에서 가장 긴 수열은 5라고 기억하지요. 그리고 다시 이전으로 돌아가서 비교해야합니다. 그때는 순서를 바꿔 O가 일치하는 상황이 되죠.

[1][2][3][4][5][6][7][8][9][10]

A O L D M K E P P A

[1][2][3][4][5][6][7][8][9][10]

O C A C K E M P P A

이렇게 [6][5]까지 비교한다면 이미 기억해두었으니 제차 끝까지 비교하지 않고 [6][5]까지의 값 5를 반환하기면 하면 됩니다. 그리고 O는 일치했으므로 1을 더하는것이죠. 그래서 답이 6이 됩니다. 이렇게 DP를 적용해서 시간을 줄일 수 있습니다.

구현

다음의 코드는 LCS의 길이를 구하는 코드입니다. 위의 설명을 잘 이해했다면 코드 역시 이해하기가 훨씬 쉬울거에요.

#include <stdio.h>
#include <string.h>

#define MAX(a,b) a>b ? a:b
#define _CRT_SECURE_NO_WARNINGS
char a[1001], b[1001];
int n, m;
int dp[1001][1001];
int solve(int pos1, int pos2) {
	if (pos1 == n || pos2 == m) return 0;
	if (a[pos1] == b[pos2])
		return 1 + solve(pos1 + 1, pos2 + 1);

	int ret = 0;
	if (dp[pos1][pos2] != -1) return dp[pos1][pos2];
	ret = MAX(solve(pos1 + 1, pos2), solve(pos1, pos2 + 1));
	return dp[pos1][pos2] = ret;
}
int main() {

	scanf("%s %s", a, b);
	n = strlen(a); m = strlen(b);
	memset(dp, -1, sizeof(int) * 1001 * 1001);
	int ret = solve(0, 0);
	printf("%d\n", ret);
}

pos1은 첫번째 수열의 비교할 문자 위치, pos2는 두번째 수열의 비교할 문자위치를 말합니다. 만약 pos1과 pos2이 하나라도 수열 끝까지 갔다면 종료되는 것이죠. 이것이 기저 사례입니다.

앞서 말한것과 같이 첫번째 수열의 pos1위치의 문자와 두번째 수열의 pos2위치 문자와 비교해서 같다면 LCS의 길이 1을 더해주고 비교할 문자의 위치 pos1,pos2를 한 칸 증가시켜줍니다.

만약 일치하지 않는다면 둘 중 하나의 수열 비교문자(pos1 또는 pos2)만 한칸 증가시키고 둘 중 가장 큰 값을 반환하면 되죠.

나중에 return할때 메모이제이션으로 값을 업데이트 시키는 것은 잊지 말고 말이죠.

퀵정렬(Quick Sort)

오늘 다루어볼 정렬 주제는 바로 퀵정렬입니다. 이름만에서도 알 수 있듯이 빠른 속도를 자랑합니다.

하지만 다른 정렬 알고리즘에 비해서 병합정렬과 더불어 까다로운 정렬 알고리즘인데요. 사실 이해만 정확히 한다면 그리 어려운 알고리즘은 아니지요.

개념

퀵 정렬에서 우선 pivot이라는 개념부터 알아야합니다. 뭐 어렵지 않습니다. 그냥 비교할 기준이라고 생각하면 되겠네요.

배열의 원소들은 피봇보다 작으면 왼쪽, 피봇보다 크면 오른쪽에 놓이는데요.

바로 아래 그림을 보면서 이해하도록 합시다.

정렬되지 않은 배열 arr= {5,6,7,3,4,2,1,9}가 있다고 하겠습니다. 이 배열에서 피봇은 1번째 원소인 5라고 가장하겠습니다.

퀵 소트를 한번 돌게 된다면 5를 기준으로 작은 원소들은 모두 왼쪽에, 큰 원소들은 모두 오른쪽에 놓이게 됩니다.

이제 이런 짓을 계속하다가 보면 어느 순간 정렬된 형태가 나오는 것이죠. 병합정렬을 배운 분이라면 뭔가 보이지 않나요? 

퀵정렬의 분할정복

퀵 정렬은 병합정렬과 마찬가지로 분할 정복의 아주 대표적인 예입니다. 하지만 정직하게 2로 나누는 병합정렬과는 다르게 퀵정렬은 비대칭으로 두동강을 내버립니다. 내 얼굴

아래 그림에서 일부를 쪼개고 다시 합치는 과정이 보이세요? 이것이 분할-정복의 개념입니다. 

분할 퀵정렬은 우선 피봇을 기준으로 2개로 나누지요. 나누고 쪼개는 것이 바로 분할입니다. 분할을 통해서 큰 문제를 여러개의 문제로 조각을 내서 더 쉽게 문제를 푼다는 개념입니다.

정복 분할 이후에 다시 정렬의 과정을 거치게 됩니다. 

병합 정복 이후 다시 합치는 과정을 병합이라고 합니다. 원래의 커다란 문제를 풀기 위해서는 해결했던 조각난 문제들을 다시 합쳐야하기 때문에 병합이라는 과정이 필요하죠. 

구현

다음의 코드가 바로 퀵소트를 구현한 것입니다.

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

void quickSort(int left, int right, int *arr) {
	int pivot = arr[left];
	int less = left;
	int more = right+1;
	
	if (left < right) {
		do {
			do
				less++;
			while (less <= right && arr[less] < pivot);

			do
				more--;
			while (more >= left && arr[more] > pivot);

			if (less < more)
				swap(&arr[less], &arr[more]);

		} while (less < more);
		swap(&arr[left], &arr[more]);
		
		quickSort(left, more - 1,arr);
		quickSort(more + 1, right, arr);
	}

}

소스코드를 보면 가장 왼쪽의 원소가 피봇이라는 것을 알 수 있네요. 이 피봇값을 기준으로 작다면 배열에 왼쪽으로 놓고 크다면 오른쪽으로 놓는 것이죠. 그 후에 피봇의 위치를 찾고 다시 피봇의 위치 기준으로 배열을 쪼개서 재귀호출을 하게 됩니다.

우리는 do ~ while 문으로 위 코드를 쓰기 때문에 more은 right의 한칸 더 뒤에 있어야합니다. do ~ while문의 특징은 우선 한번은 실행시키기 때문입니다. 

역시 less 그렇습니다. 가장 첫번째 left의 위치부터 시작해야 피봇 다음 원소부터 비교할 수 있는 것입니다.

어려울 수 있으니 다시 그림과 함께 이 코드를 봅시다.

우선 초기 상태는 이렇습니다. 그림에서도 볼 수 있듯이 less는 left의 위치에 있고, more은 right의 다음번째에 있습니다. 이제 do ~ while문을 실행하는 거죠.

less는 5보다 큰 원소가 있으면 멈추고 more은 5보다 작은 원소가 있으면 멈춥니다.

자, 6과 1이 걸리게 되겠죠? 6은 5보다 크니까 오른쪽에 있어야하고 1은 5보다 작으니 왼쪽에 있어야합니다. 그러니까 less와 more의 원소를 교환합시다. 그 후 계속 이 과정을 반복할 겁니다.

이제는 7과 2가 걸리게 되겠네요. 역시 교환합시다.

3과 4는 5보다 작으니까 지나가고 less는 7을 만나게 되면 멈춥니다. 그리고 more은 4를 만날때까지 왼쪽으로 가게 되죠. 하지만 이때 more과 less가 교차하게 됩니다. 이때 우리는 more과 less 사이의 지점, 그 지점이 바로 피봇이 위치하게 되는 지점이 되는 겁니다. 그러니 피봇이 있는 위치 left와 more과 swap하게 되면 5를 기준으로 작은 원소는 왼쪽에, 큰 원소들은 오른쪽에 위치하게 되는 것이죠.

최종상태는 위와 같습니다. 이제 5(pivot)을 기준으로 다시 이러한 과정을 반복하게 됩니다.

이제 이해가 되셨나요?

시간복잡도

위의 분할 정복의 그림에서 봤듯이 계속 두개로 쪼개 n번 비교하게 되므로 시간 복잡도는 평균적으로 O(nlogn)이 됩니다.

하지만 이미 정렬된 배열에서도 O(nlogn)이 나오게 될까요? 이 경우에는 O(n^2)이 됩니다. 피봇의 위치가 항상 왼쪽이라면 항상 2개로 쪼개지는 것이 아니라 pivot을 제외한 배열을 정렬하게 되는 샘이지요.

하지만 퀵소트가 빠른 점은 바로 pivot은 정렬에 포함시키지 않기 때문이죠. 그러므로 병합정렬보다 빠릅니다. 그러니까 이름이 Quick Sort이지요.

그리고 퀵 정렬은 배열의 공간외에는 다른 공간을 쓰지 않기 때문에 공간복잡도는 O(n)입니다.

이상으로 퀵소트에 대한 포스팅을 마치도록 하지요. 바이바이

이진탐색

배열에서 어떤 원소를 찾을때 그 원소가 있는지 어떻게 찾을 수 있을까요?b가장 간단한 방법은 아무래도 for루프를 실행하면서 하나하씩 일치하는지 검색하는 방법이겠죠?

너무 쉽습니다.

int arr[10] = { 3,5,6,8,9,11,14,15,18,20 };
int i;
int data = 18;
int found = -1;
for (i = 0; i < sizeof(arr); i++)
	if (arr[i] == data) found = arr[i];

printf("found:%d\n", found);

이보다 빠르게 찾을 수는 없을까요? 이 탐색시간을 O(logn)으로 수행할 수 있는 방법이 바로 이진탐색(Binary Search)입니다.

개념

이진탐색은 우선 정렬된 배열에서만 사용가능합니다. 정렬되지 않았다면 정렬을 해주어야하지요. 

또한 이진탐색은 3개의 변수가 사용이 됩니다. 바로 left, mid, right이지요. 초기상태에서 배열의 가장 첫번째를 가리키고 있는 left, 배열의 가장 끝을 가리키고 있는 right, left와 right의 중간을 가리키고 있는 변수가 mid입니다.

우리가 찾는 원소를 data라고 합시다. 우리는 mid의 값을 중요하게 생각해야 돼요. mid자리에 있는 원소가 data와 같다면 그 원소를 찾게 된 것이죠.

만약 mid자리에 있는 원소보다 data가 크다면 left~mid까지 범위는 탐색할 필요가 없게 되지요. 반대로 mid자리 원소보다 data가 작다면 mid~right까지의 범위는 탐색할 필요가 없습니다.

찾지 못 한다면 범위를 바꾸어줘야합니다. left~mid까지의 범위를 탐색할 필요가 없다면 이제 left=mid+1이 되고 mid 역시 left, right의 중간값인 (left+right)/2가 됩니다. 그 반대도 역시 마찬가지죠. 정리하자면 이렇습니다.

이제 실제로 어떻게 데이터가 검색되는지 보도록하지요.

배열의 원소 arr = { 3, 5, 6, 8, 9, 11, 14, 15, 18, 20}이라고 칩시다.

다음은 여기서 18을 찾는 과정을 보여줍니다.

우선 초기에 left=0, mid=4, right=9입니다. mid의 값은 (left+right)/2로 계산된 값입니다. arr[mid]와 data를 비교해보니 data가 더 크군요. 그러니까 left와 mid까지의 범위는 볼 필요가 없습니다. 정렬된 배열이기 때문에 18보다 작은 것들은 left~mid까지이니까요.

이제 범위를 옮기도록 하지요. left=mid+1이 되고 mid는 그 중간 값인 (left+right)/2가 됩니다. 이제 다시 arr[mid]와 data를 비교해보니 data가 더 크지요? 다시 범위를 바꿉니다

이제 left와 mid는 같은 값이 되고 다시 arr[mid]와 data를 비교해보니 일치합니다. data가 배열에 있다는 것을 알게 됐습니다.

만일 data를 찾지 못한다면 left와 right는 서로 뒤집히게 됩니다. 그러니까 left가 right보다 더 크게 변한다는 의미입니다.

구현

아래코드는 원소가 존재한다면 몇번째에 위치하는지 인덱스를 구해냅니다. 구현을 통해서 위의 결과를 확인해보세요. 

int binarySearch(int *arr,int size,int data) {
	int left = 0;
	int right = size - 1;
	
	while (left<=right) {
		int mid = (left + right) / 2;
		if (arr[mid] == data)
			return mid;
		if (arr[mid] > data)
			right = mid - 1;
		else
			left = mid + 1;
	}

	return -1;
}

초기 left=0, right=size-1입니다. 가장 처음과 끝을 가리키고 있지요. while루프의 탈출조건은 left가 right보다 같거나 작을때까지 입니다. 

while루프에서는 우선 mid의 값을 구하고 이 mid 원소와 data를 비교하여 같은지 확인합니다. 원소를 찾지 못하면 left와 right의 값을 바꿉니다.

간단하죠?

이진탐색은 재귀함수로도 간단하게 구현이 가능합니다.

int binarySearch(int *arr,int left,int right,int data) {
	if (left > right) return -1;

	int mid = (left + right) / 2;
	
	if (arr[mid] == data) return mid;
	if (arr[mid] > data)
		return binarySearch(arr, left, mid - 1, data);
	return binarySearch(arr, mid + 1, right, data);
}

재귀함수도 너무 간단하죠? 기자사례는 위의 while루프와 같다는 것을 알 수 있습니다. 재귀함수의 종료 조건이되지요.

그 후 내부 코드는 while루프의 내부 코드와 유사하다는 것을 알 수 있습니다. 그렇죠?

아참, 주의할것은 호출할때 binarySearch(arr,0, (sizeof(arr)/sizeof(int))-1, data)로 호출해야합니다. 만약 arr의 크기가 10이라면 9를 right의 매개변수로 전달하는 것이죠. 왜냐면 크기가 10인 배열의 마지막 인덱스는 9이기 때문이죠.

시간복잡도

결국 이진탐색은 반으로 계속 줄여가면서 원소를 탐색하기 때문에 시간복잡도는 O(logn)이라는 사실을 알 수 있습니다. O(n)에 비해서는 훨씬 빠른 속도입니다.

하지만 배열이 정렬된 상태여야 된다는 점이 조금 아쉬운 부분이기는 하지만 하나의 배열에서 검색을 자주하는 상황이라면 한번 정렬만 하면 다음부터는 계속 O(logn)의 속도로 원소를 찾을 수 있죠.

프림 알고리즘(Prim's Alogorithm)

최소 스패닝 트리의 크루스칼 알고리즘과 프림 알고리즘의 동작 방법을 알아보았으니 이제 코드로 구현해 볼 차례입니다.

그때 썼던 그래프를 다시 가져다가 써보도록 하죠.

우리는 이 그래프의 최소 스패닝트리를 프림알고리즘으로 구하는 원리는 알고 있으니 위의 그래프를 코드로 구해보도록 합시다. 여기서는 C++을 사용하여 보다 쉽게 구현할 겁니다.

int prim(vector<pair<int, int> > &selected) {
	selected.clear();

	vector<bool> added(V, false);
	vector<int> minWeight(V, INF), parent(V, -1);

	int ret = 0;
	minWeight[0] = parent[0] = 0;
}

우선 필요한 변수들을 선언했습니다. 

selected 변수에는 우리가 선택한 간선의 정점 정보가 저장될 겁니다. 일단 selected.clear()로 벡터를 비워주도록 합시다.

added변수는 현재 트리에 어떤 정점이 있는지 체크하기 위한 변수입니다. 

만약 정점 3이 트리에 포함되어 있다면 added[3]=true이지요. 처음에는 어떤 정점도 트리에 포함되지 않으므로 added 벡터는 전부 false로 초기화가 됩니다.

minWeight에는 트리에 붙어있는 정점 중 가장 가까운 정점이 들어있습니다. 초기에는 선택된 정점이 아직 없으므로 가장 큰 값을 설정합니다.

parent에는 정점의 부모를 나타냅니다. 만일 어떤 정점 u가 있다면 그 부모 정점은 parent[u]가 되는 것이죠.

ret는 최소 스패닝 트리의 모든 간선의 값을 나타냅니다.

이제 우리는 정점 0을 기준으로 트리를 만들어 나갈건데 0의 부모는 자기 자신이고, 자기 자신까지의 거리는 0입니다.

for (int iter = 0; iter < V; iter++) {
		
}

위의 for 루프는 모든 정점까지 반복하는 루프입니다. 이 안이 우리가 구현해야 할 부분이지요.

이제 이 for루프를 구현해보도록 하죠.

int u = -1;
for (int v = 0; v < V; v++) {
	if (!added[v] && (u == -1 || minWeight[u]>minWeight[v]))
		u = v;
}

if (parent[u] != u)
	selected.push_back(make_pair(parent[u], u));

u라는 변수는 초기에 -1을 지정합니다. 이미 트리에 저장되지도 않았고, 트리의 가장 가까운 정점을 찾는 것이죠.

만약 u의 부모가 u가 아니라면 u의 부모와 u로 구성된 정점 쌍을 selected에 저장합니다. 

u==-1일 경우에는  언제일까요? u가 첫 시작점(첫 스타트를 끊었을때)일 때 -1이라는 것이죠. 가장 처음으로 시작하기 때문에 아직 추가된 정점이 없고, 가장 처음에 시작했기 때문에 u==-1이지요. 

ret += minWeight[u];
added[u] = true;

추가를 했으니 ret에 값을 추가하고 트리에 추가되었다는 표시를 해야되겠죠??

for (int i = 0; i < adj[u].size(); i++) {
	int v = adj[u][i].first, weight = adj[u][i].second;
	if (!added[v] && minWeight[v]>weight) {
		parent[v] = u;
		minWeight[v] = weight;
	}
}

#include <iostream>
#include <vector>

using namespace std;

const int MAX_V = 100;
const int INF = 987654321;

int V=6;

vector<pair<int, int> > adj[MAX_V];

int prim(vector<pair<int, int> > &selected) {
	selected.clear();

	vector<bool> added(V, false);
	vector<int> minWeight(V, INF), parent(V, -1);

	int ret = 0;
	minWeight[0] = parent[0] = 0;
	for (int iter = 0; iter < V; iter++) {
		int u = -1;
		for (int v = 0; v < V; v++) {
			if (!added[v] && (u == -1 || minWeight[u]>minWeight[v]))
				u = v;
		}

		if (parent[u] != u)
			selected.push_back(make_pair(parent[u], u));

		ret += minWeight[u];
		added[u] = true;

		for (int i = 0; i < adj[u].size(); i++) {
			int v = adj[u][i].first, weight = adj[u][i].second;
			if (!added[v] && minWeight[v]>weight) {
				parent[v] = u;
				minWeight[v] = weight;
			}
		}
	}
	return ret;
}

int main() {
	adj[0].push_back(make_pair(1, 5));
	adj[1].push_back(make_pair(0, 5));

	adj[1].push_back(make_pair(2, 3));
	adj[2].push_back(make_pair(1, 3));

	adj[2].push_back(make_pair(3, 4));
	adj[3].push_back(make_pair(2, 4));

	adj[1].push_back(make_pair(4, 3));
	adj[4].push_back(make_pair(1, 3));

	adj[0].push_back(make_pair(3, 7));
	adj[3].push_back(make_pair(0, 7));

	adj[2].push_back(make_pair(4, 2));
	adj[4].push_back(make_pair(2, 2));

	adj[3].push_back(make_pair(5, 1));
	adj[5].push_back(make_pair(3, 1));

	adj[4].push_back(make_pair(5, 4));
	adj[5].push_back(make_pair(4, 4));

	vector<pair<int, int> > selected;
	int mst=prim(selected);
	printf("mst:%d\n", mst);
	for (int i = 0; i < selected.size(); i++) {
		printf("%d-%d\n", selected[i].first, selected[i].second);
	}
	printf("\n");
}

main함수에서는 각 간선을 연결해주고 weight도 부여합니다. 

예를 들어

adj[4].push_back(make_pair(5,4))

adj[5].push_back(make_pair(4,4))

라는 것은 4와 5의 정점을 연결하는데 그 간선의 weigt는 4라는 것입니다. 또한 그래프가 무향 그래프이기 때문에 거꾸로도 연결해야하는 것이죠.

그래서 각각 짝을 맞추어서 간선을 연결해주어야합니다.

mst는 최소스패닝트리의 간선값의 합을 나타냅니다. 따라서 단지 최소스패닝트리의 값만 보고 싶다면 mst를 쓰면 되구요.

경로를 보고 싶다면 selected에서 정점 쌍을 꺼내 출력하면 됩니다.

최소 스패닝 트리(Minimum Spanning Tree)

최소 스패닝 트리를 이야기하기 전에 우선 스패닝 트리란 무엇인지 알아보도록 할게요.

우선 어떤 무향 그래프가 있다고 해보도록 가정하겠습니다. 스패닝 트리는 말 그대로 그래프에서 트리의 상태를 유지해야합니다. 그러니 사이클이 있으면 안되지요. 반드시 부모와 자식 관계로 이루어져 있지 않아도 됩니다.

다음의 그림은 올바른 스패닝 트리와 그렇지 않은 스패닝 트리를 보여줍니다.

왼쪽의 그림의 선택된 간선(굵은 선)은 사이클을 이루지 않지요.

반면 오른쪽 그림은 빨간선 때문에 사이클을 이루게 됩니다.

어때요? 간단하지요?

스패닝 트리는 그래프에서 여러개가 존재할 수도 있지만 우리가 눈여겨 볼 것은 스패닝 트리의 간선들이 가장 최소의 값을 갖는 것으로 바로 최소 스패닝 트리(Minimum Spanning Tree)라고 합니다.

대표적인 알고리즘에는 대표적으로 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 있는데요. 이 두가지 알고리즘을 함께 보도록 하지요.

크루스칼 알고리즘 개념(Kruskal's Algorithm Concept)

우리는 아래의 그래프의 최소 스패닝 트리를 구할 겁니다. 이제 이 그래프를 가지고 크루스칼 알고리즘이 어떻게 동작하는지를 확인해 보도록 할게요.

원리는 이렇습니다.

우리는 위의 조건들을 가지고 최소 스패닝 트리를 찾는 겁니다.

우선 가장작은 간선의 값인 1, 즉 3-5의 간선을 봅니다. 현재 선택된 간선은 없으므로 3-5의 간선을 추가합니다. 그 다음 작은 간선을 보면 2인데, 이 간선은 현재 추가된 간선이 없으므로 2-4의 간선도 추가합니다.

이제 추가된 간선은 3-5, 2-4의 간선(파란색)입니다. 그 후 가장 작은 간선을 보면 1-2인데 이 간선은 추가된적이 없으므로 추가합니다. 그 후 역시 3인 간선이 있는데요. 이 간선을 추가하게 되면 사이클을 이루게 됩니다. 그러니까 다음 간선으로 넘어가게 되지요.

그 다음 작은 간선은 2-3입니다. 값은 4인데, 이 간선은 현재 추가한적이 없지요?(파란색 간선이 추가한 간선입니다.) 그러니 이 간선을 포함시키도록 합니다.

그 후 4-5 간선을 보게 되면 현재 선택되지는 않았지만 추가하게 되면 사이클을 이루게 됩니다. 그러니 넘어가죠.

이후 간선 0-1의 간선을 추가합니다. 다음으로 큰 수가 5이니까요.

이제 모든 정점이 트리에 포함되었으니 종료합니다.

따라서 최종 최소 스패닝 트리는 아래의 그림과 같습니다.

어떻습니까??

가장 최소의 값으로 스패닝 트리를 완성했다는 것을 알 수 있습니다.

프림 알고리즘 개념(Prim's Alogorithm Concept)

이번에는 최소 스패닝 트리의 다른 알고리즘, 프림 알고리즘을 보도록 하지요. 프림 알고리즘은 트리에 연결된 간선 중 가장 작은 것을 차례차례 선택해나갑니다. 크루스칼 알고리즘과 같은 점은 역시 사이클을 이루는 간선을 선택하지 않는다는 것이죠.

어느 정점에서 시작하든 상관없습니다. 우리는 3번의 정점부터 계속 트리에 정점을 추가할 것입니다. 3과 가장 가까운 정점은 5가 되겠네요. 3과 5를 트리에 추가합니다. 3, 5 정점 중 가장 작은 간선은 2-3과 4-5네요. 구현에 따라 다를수 있으므로 둘 중에 아무거나 선택하면 됩니다. 2-3의 간선을 선택하지요. 따라서 트리에는 2가 추가가 됩니다.

이제 2, 3, 5에 붙어 있는 간선 중 가장 작은 간선 2-4를 선택합시다. 

그렇다면 현재 트리에는 2, 3, 4, 5가 됩니다. 이제 이 정점에서 가장 작은 간선을 선택해보도록 하지요. 후보는 1-2 간선과 1-4 간선이 됩니다. 아무거나 선택합시다. 

1-2의 간선을 선택하지요.

그 후 트리에 속해있는 정점과 붙어있는 가장 작은 간선은 1-4의 간선이 되는 군요. 하지만 선택할 수 없습니다. 사이클을 이루니까요. 그러니 버립시다.

다음 가장 작은 간선은 4-5의 간선입니다. 이것 역시 사이클을 이루게 되죠? 그러니 그냥 버리도록 합시다.

다음으로 가장 작은 간선은 0-1의 간선입니다. 이 간선을 포함해도 사이클을 이루지 않으니 선택하도록 하지요.

그렇다면 이제 모든 정점이 트리에 포함되어 있습니다. 여기서 종료합니다.

프림 알고리즘과 크루스칼 알고리즘이 동작하는 방식은 다르나 최소 스패닝 트리를 구할 수 있다는 것을 알 수 있습니다. 두 알고리즘 다 15의 값을 갖는 최소 스패닝 트리를 만들어 낼 수 있었습니다. 최소 스패닝 트리는 여러개 존재할 수는 있지만 그 값은 같다는 것을 잊지마세요.

플로이드(Floyd) 알고리즘

이번에는 조금 더 간단하게 최단거리를 구할 수 있는 알고리즘을 소개합니다.

다익스트라 알고리즘은 한 시작점에서 다른 정점까지의 최단 거리를 구하는데 반해 플로이드 알고리즘은 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구할 수 있습니다!

단, 플로이드 알고리즘은 음수 가중치가 없는 무조건 양수의 그래프에서 동작합니다.

경유점

어떤 정점 a와 b가 연결되어 있다고 할때 이 정점 사이에 c가 있다고 하지요. a와 b로 연결되어 있는 간선의 비용이 5라고 하구요.

하지만 a와 c의 비용은 2, b와 c의 비용은 2라고 한다면 a와 b로 가는데 c를 거쳐가는 것이 더 효율적이라는 것을 알 수 있습니다. a-c-b의 비용은 4이기 때문에 a-b의 비용 5보다 비용이 더 적습니다.

c와 같이 경로가 거쳐가는 정점이 경유점이라고 하지요.

플로이드 알고리즘은 두 정점 사이의 어떤 경유점이 존재한다면 경유점을 거쳐가는 것을 확인하면서 더 짧은 것을 선택하게 됩니다.

구현

아래와 같은 그래프가 있는데 모든 쌍의 최단거리는 어떻게 될까요?

1-4까지의 최단 거리?

0-3까지의 최단 거리?

이제 본격적으로 구현해보도록 합시다.

그래프의 초기화

위의 그래프를 우선 배열로 구현해야합니다. 조건이 있는데, 초기에 직접적으로 연결되어 있지 않은 경로는 아주 큰 값으로 설정해야한다는 것이죠. 그리고 자기 자신까지의 비용은 0으로 만들어 줍니다.

플로이드 알고리즘 적용

이제 플로이드 알고리즘만 적용시켜주면 되지요.

시작점은 i, 끝점을 j, 경유점을 k라고 했을때 구하는 식은 다음과 같습니다.

이 경유점 k를 지나는 모든 i, j에 대해서 확인해주면 됩니다.

adj[i][j]와 adj[i][k]+adj[k][j] 중 항상 작은 값만을 갖게 되므로 직접적으로 연결이 되지 않는 간선은 INF로 처음에 초기화 한 이유를 아시겠어요?

만일 경유점 k가 0이라고 할때 adj[1][2] = MIN(adj[1][2], adj[1][0] + adj[0][2]) = MIN( INF, 5) = 5 가 됩니다. 결국 1-2까지의 경로는 5로 더 작은 값이 됨을 알 수 있죠.

그 후 경유점이 k=2가 되었다고 할때 adj[1][3] = MIN(adj[1][3], adj[1][2] + adj[2][3]) = MIN(INF, 6) = 6이 됩니다. 왜냐면 방금전 adj[1][2]를 구해냈기 때문이지요. 그래서 1-3까지의 비용은 6이 되는 것을 알 수 있습니다.

이렇게 모든 경유점을 확인하면서 비용이 작은 값만을 선택합니다.

이제 전체 코드를 보면서 결과를 확인해보세요.

#include <stdio.h>
#define MAX_V 10
#define MIN(a,b) a<b ? a:b
#define INF 987654321
int V,E;
int adj[MAX_V][MAX_V];
void initAdj() {
	int i, j;
	for (i = 0; i < V; i++)
		for (j = 0; j < V; j++) {
			adj[i][j] = INF;
			if (i == j)adj[i][j] = 0;
		}
}
void floyd() {
	int k,j,i;
	
	for (k = 0; k < V; k++)
		for (i = 0; i < V; i++)
			for (j = 0; j < V; j++)
				adj[i][j] = MIN(adj[i][j], adj[i][k] + adj[k][j]);
}
int main() {
	int i, j;
	printf("정점 개수:");
	scanf("%d", &V);
	printf("간선 개수:");
	scanf("%d", &E);

	initAdj();

	printf("정점 연결( 정점1 정점2 비용) \n");
	for (i = 0; i < E; i++) {
		int v1, v2, cost;
		scanf("%d %d %d", &v1, &v2, &cost);
		adj[v1][v2] = adj[v2][v1] = cost;
	}


	floyd();

	for (i = 0; i < V; i++) {
		for (j = 0; j < V; j++)
			printf("%d~%d까지의 최단거리:%d\n", i, j, adj[i][j]);
		printf("\n\n");
	}
}

경유점 k의 순서가 꼭 0부터 V까지 순차적일 필요는 없습니다. 경유점을 어느 순서로 해도 상관이 없다는 것이죠.

복잡도

위 코드의 시간복잡도는 O(V^3)이 되고 공간복잡도는 O(V^2)가 됩니다. 플로이드 알고리즘은 V가 작고 모든 정점의 최단 거리를 구할때 아주 유용하고 쉽게 구현할 수 있기 때문에 기억해둘만한 가치가 충분히 있습니다.

다익스트라 알고리즘 (Dijkstra Algorithm)

최단거리를 구하는 데에는 꽤 여러가지 알고리즘이 존재합니다. 그 중에서 가장 유명한 알고리즘, 다익스트라 알고리즘에 대해서 알아보도록 하겠습니다.

다익스트라 알고리즘은 무엇일까요?

그래프의 한 정점에서 모든 정점까지의 최단 거리를 구하는 것이 이 알고리즘입니다. 

우선 아래와 같은 그래프가 있다고 가정해볼게요.

정점 0에서 모든 정점까지의 최단거리는 어떻게 될까요?

0번에서부터 5번 정점 중 임의의 i까지 최단 거리를 dist[i]라고 할때

가 됩니다.

이와 같이 어떤 시작점을 정해서 그 정점부터 다른 정점까지의 최단거리를 구하는 알고리즘이 바로 단일 시작점 알고리즘이고, 대표적인 알고리즘이 바로 다익스트라 알고리즘입니다.

BFS 최단거리 기반

이 알고리즘은 최단 거리를 구하는 것이기 때문에 BFS를 기반으로 움직이는데요. BFS는 자료구조에서 큐를 썼었죠? 따라서 다익스트라 알고리즘 역시 큐를 사용하여 구현할 수 있다는 사실을 알아두세요.

주의 사항은 위의 그래프가 나타내는 것처럼 음수간선이 있으면 다익스트라 알고리즘을 쓸 수가 없어요.

다익스트라 구현 (C++)

코드로 다익스트라 알고리즘을 살펴본 후 설명하도록 하겠습니다.

#include <vector>
#include <iostream>
#include <queue>

#define MAX_V 100
#define INF 99999999
using namespace std;


vector<pair<int, int> > adj[100];
vector<int> dijkstra(int start, int V) {
	vector<int> dist(V, INF);
	dist[start] = 0;
	priority_queue<pair<int, int> > q;
	q.push(make_pair(0, start));

	while (!q.empty()) {
		int cost = -q.top().first;
		int from = q.top().second;
		q.pop();

		if (dist[from] < cost) continue;

		for (int i = 0; i < adj[from].size(); i++) {
			int to = adj[from][i].first;
			int distFromTo = cost + adj[from][i].second;
			if (distFromTo < dist[to] ) {
				dist[to] = distFromTo;
				q.push(make_pair(-distFromTo, to));
			}
		}
	}
	return dist;
}

int main(int argc, char **argv)
{
	int E, V;
	printf("[input] vertex edge :");
	scanf("%d %d", &V, &E);

	
	for (int i = 0; i < E; i++) {
		printf("[input] from to cost :");
		int from, to, cost;
		scanf("%d %d %d", &from, &to, &cost);
		adj[from].push_back(make_pair(to, cost));
		adj[to].push_back(make_pair(from, cost));
	}

	printf("===dijkstra===\n");
	vector<int> dist = dijkstra(0, V);
	for (int i = 0; i < V; i++) {
		printf("from 0 to %d : %d\n", i, dist[i]);
	}
	return 0;
}

우선 입력을 받습니다. 위의 그래프 모양 그대로 입력을 받습니다. 위의 그래프를 조금 더 편하게 입력받으려면 아래의 input을 복사해서 붙여넣으세요.

이후 dijkstra가 어떻게 동작하는 지 그림을 보며 살펴보도록 합시다.

우선 우리가 반환한 dist의 벡터 사이즈를 V의 크기(정점의 개수)로 정하고 그 값을 아주 큰 값으로 설정합니다.

자기 자신과의 거리는 0이므로 dist[start]는 0으로 셋팅합니다.

여기서는 priority queue를 사용하는데요. 그 이유는 정점으로부터 가장 작은 값으로 연결되어 있는 정점을 꺼내는 것이 더 효율적이니까 그렇습니다.

또한 priority queue는 pair를 통해서 우선 순위를 정할때 첫번째 요소를 기준으로 가장 큰 값을 먼저 꺼내옵니다. 그래서 첫번째 요소를 거리, 그것도 -를 붙여서 넣어주면 값이 큰 간선으로 연결된 정점이 더 나중에 나오게 되는 것이죠.

그래서 꺼내올때 -를 붙여서 꺼내오고 -를 붙여서 집어 넣습니다.

이제 그림으로 더 쉽게 보도록 합시다.

우선 초기상태는 자기 자신의 정점을 우선순위 큐에 push하며 그 거리는 0이 됩니다. while루프를 돌기 전의 모습입니다. 

그 후 첫 while 루프를 돌면서 큐에 저장된 (0,0)을 가져옵니다. 0은 dist[0]보다 작지 않기 때문에 if문에 걸리지 않고 for루프를 돌게 됩니다. 주변에 가장 작은 값으로 연결된 정점은 2, 1, 3이지요. 그래서 그에 대응되는 거리 2, 3, 5와 함께 우선 순위 큐에 저장합니다. 

하지만 우선순위 큐는 큰 값이 먼저 선정되기 때문에 음수를 붙여서 -2,-3,-5로 바꾸어서 넣어줍니다.

** 아래 그림에서 잘못된 것이 있는데 우선순위 큐에 푸시되는 값은 (-2,2) (-3,1) (-5,3)인것으로 정정해주세요. 죄송해요.

우선순위 큐에서 2를 꺼내올때 이미 dist[2]는 2로, dist[2]보다 2가 더 작지 않으므로 if 조건문에 걸려 continue됩니다.

이 후 (-3, 1)을 꺼내옵니다. 정점 1에서 연결된 정점 중 가장 가까운 정점은 4입니다. 그렇기 때문에 dist[4]를 12로 수정하고 이 정보를 우선순위 큐에 저장합니다.

이제 (-5,3)을 꺼내올 차례이군요. dist[3]은 5이고, 큐에서 꺼내온 값 역시 5이므로 if문에 걸리지 않고 for루프를 돕니다. 이제 3에 연결되어 있는 정점은 4로 연결된 cost가 1인 간선입니다. 그래서 그전에 있던 dist[3]과 4로 연결된 간선의 cost 1을 더한 값(6)과 dist[4]와 연결된 값과 비교해보니 6이 더 작으므로 dist[4]=6으로 갱신하고 (-6,4)를 큐에 집어 넣습니다.

여기서 우선순위 큐를 사용하는 이유가 나옵니다. 만일 순서를 고려하지 않고 (-5, 3)이 큐에 맨 끝에 위치해있다면 이러한 갱신을 맨끝에 하게 되어 for루프를 돌게 되는 시간적인 낭비가 있게 되는 겁니다. 

그렇기 때문에 가장 비용이 낮은 것이 먼저 나오는 것이 유리하다는 것이죠.

다음 (-15,4)는 cost가 15이기 때문에 if조건에 걸려 continue됩니다. 

남은 (-6, 4)를 꺼내오게 되면 if조건문에 걸리지 않고 for루프를 돌아요. 4와 연결된 정점 5까지의 비용은 dist[4]와 3을 더한 9가 됩니다. 왜냐하면 dist[5]는 아주 큰 값이기 때문에 6이 더 작잖아요?

그 후 5와 연결된 간선의 정보를 큐에 저장합니다.

이제 마지막 (-9, 5)를 꺼내오는데, 이미 dist[5]=9이므로 if 조건에 걸려 continue됩니다. 이 후에는 큐가 비었으므로 while문을 탈출하게 되지요.

이제 모든 거리를 구했습니다.

코드에서는 0을 기준으로 구했는데 코드를 바꾸어서 1부터 시작해서 최단거리를 구해보세요. 그리고 비교해보세요.