안녕하세요. 제프입니다.
한동안 강좌를 쉰 것 같아, 커뮤니티에 올리던 강좌 하나를 옮겨담기로 했습니다. 우리는 알고리즘의 기초부터 시작해 점차 알고리즘이 어떤 것이고, 우리에게 무슨 이득을 줄 수 있는지 낱낱이 파헤쳐보도록 할 것입니다.
그중에서도 오늘은 알고리즘을 사용해보고 그 효과를 직접 체험해보는 시간으로 우리가 배우게될 알고리즘에 대해 첫 대면을 갖는 시간이 되겠습니다.
오늘 알고리즘을 적용해볼 상황은 바로 정렬입니다.
정렬은 우리가 쉽게 탐색♡에서도 사용할 수 있으며, 인터넷 게시판 또는 가격비교 사이트 등에서 쉽게 사용해볼 수 있습니다.
- 정렬 그림자료 -
이 정도로 우리가 쉽게 접할 수 있는 기능인 정렬에 대해 모르시는 부분은 없으실 것입니다. 다수의 데이터들을 오름차순, 또는 내림차순 등의 특정한 기준으로 순서대로 다시 나열하는 것입니다.
정렬은 오늘날의 최신형 컴퓨터를 가지고도, 그것을 수행하는 알고리즘에 따라 작업에 걸리는 시간이 극과 극으로 차이가 나는 사례중의 하나입니다. 대부분의 상용 프로그램들은 수만건의 자료도 0.01초 내에 정렬을 해내고 있지만, 알고리즘에 따라서는 정렬만 몇시간이 걸리는 경우도 생길 수가 있습니다.
- 알고리즘의 차이, 그것이 바로 경쟁력 -
이것은 컴퓨터의 성능으로 커버할 범위을 벗어난 알고리즘 자체의 문제인 것입니다. 따라서 우리가 이렇게 알고리즘에 대해 알아보는 것은, 최대한 빠른시간내에 같은 작업을 효율적으로 수행할 방법을 찾기 위해서입니다. 다시말해, 얼마나 빠른 알고리즘을 만들어내느냐가 프로그래머의 영원히 풀리지 않는 과제입니다.
정렬의 기본, 오름차순 정렬을 구현해보자.
가장 기본적인 숫자 정렬을 예로 간단히 오름차순 정렬을 하는 방법을 찾아보도록 하겠습니다. 이 경우 여러개의 숫자들을 접근해야 하므로, 배열에 넣어두고 반복문을 통해 배열의 모든 값을 읽어낼 수 있습니다.
우선 우리에게 주어진 문제인 오름차순 정렬을 하기 위해서는 기존의 배열에서 최소값부터 차례대로 찾아내야 할 필요가 있습니다.
만약 그것이 가능하다면, 찾아낸 결과를 한가지 배열에 차곡차곡 쌓는다면 정렬이 마무리 될 것입니다.
3, 5, 2, 1 // 1이 최소값
1
// 그다음 2가 최소값
1, 2 // 2가 추가
그다음 3이 최소값...
...
마지막까지 남은 숫자를 추가
// 정렬된 결과
- 정렬 알고리즘의 기본 아이디어 -
만약 이렇게 됀다면, 전체 데이터에서 최소값을 얼마나 빠르게 찾느냐가 문제가 됩니다.
하지만, 지금 우리가 찾을 수 있는 가장 쉬운 방법으로는 반복문으로 모든 값들을 비교해서 가장 작은 값을 찾아내는 방법이 있습니다.
소스코드 :
int array[4] = { 3, 5, 2, 1 };
int min_Idx = 0; // 배열 array 의 최소값을 나타내는 인덱스
for (int i=0; i < sizeof(array); i++)
{
if (array[min_Idx] > array[i]) { // 최소값보다 더 작은 값이 나타난다면,
min_Idx = i; // 새로운 값의 인덱스를 최소값으로 기억
}
}
이렇게 된다면 현재 배열의 최소값을 구할 수 있습니다. 그렇다면, 최소값으로 선택된 값을 새로운 배열에 채워넣고, 다음 값을 구하도록 합니다. 이때에는 기존에 선택되었던 값은 제외하고 구해야, 그 다음 최소값을 구할 수 있을 것입니다.
소스코드 :
int size = 0;
int result_Idx[4] = { 0, }
...
// 구한 최소값의 인덱스를 배열에 저장
result_Idx[size++] = min_Idx;
이렇게 배열의 최소값의 인덱스를 저장하는 배열을 만들어두겠습니다. 이 배열은 데이터와 같은 크기인 4개짜리 배열이기 때문에, 정렬할 데이터의 인덱스를 모두 저장할 수 있습니다.
대입을 할 때에는 size 변수의 후증가 연산을 이용해 대입을 수행한 이후 size가 증가하도록 되어있습니다. 즉 인덱스가 한번 저장되면, size 변수는 초기값에서 증가된 1을 나타내게 됩니다. 따라서 그 다음에 저장하기 위해 size 변수를 참조하면, result_Idx[1]에 저장을 하게 될 것입니다.
되짚어보기 - 후증가연산
후증가연산을 이용하면 해당 명령어줄을 실행하는 동안에는 기존의 값을 유지하지만, 명령줄 실행이 모두 끝나면 해당 변수의 값을 1 증가시키는 연산을 수행하게 됩니다.
그렇다면 위의 최소값을 구하는 부분에 기존 결과와 비교하는 부분을 추가해야 겠습니다. 만약 비교문을 추가하지 않는다면, 항상 전체 최소값을 구해내기 때문에 최소값부터 순서대로 값을 얻을 수 없습니다.
소스코드 :
for (int i=0; i < sizeof(array); i++)
{
// 추가된 부분
for (int j = 0; j < size; j++)
if (result_Idx[j] == i) continue; // 기존 결과에 포함되었다면 스킵
// 추가된 부분 끝
if (array[min_Idx] > array[i]) { // 최소값보다 더 작은 값이 나타난다면,
min_Idx = i; // 새로운 값의 인덱스를 최소값으로 기억
}
}
지금까지 정렬의 기본적인 아이디어를 정립하고 소스코드로 만들었습니다.
정렬을 하기위해서는 첫째, 최소값을 구해내고 그것을 결과 배열의 첫번째에 넣습니다. 둘째, 이미 계산된 결과를 제외한 나머지중의 최소값을 다시 구하여 배열에 넣습니다. 이 과정을 모든 데이터가 모두 정렬이 끝날때까지 반복합니다.
이렇게 컴퓨터가 숫자정렬을 할 수 있는 방법을 바로 알고리즘이라고 합니다. 이처럼 알고리즘은 단순 계산만 할 수 있는 컴퓨터에게 정렬이라는 복합적인 일을 처리하도록 만들어 줍니다.
꼭, 정렬만이 아니라 우리가 게임에서 접하는 여러 NPC와 몬스터들의 인공지능도 이런 알고리즘이라고 할 수 있으며, 단순히 성적의 평균을 구하는 계산공식도 알고리즘이라고 할 수 있습니다.
즉, 컴퓨터를 이용해 우리가 원하는 일을 시키는 기본적인 생각, 아이디어가 바로 알고리즘인 것입니다.
알고리즘은 단순히 문제를 해결하는 방법이기 때문에, 다양한 알고리즘이 존재할 수 있습니다. 사람마다 문제를 해결하기위해 생각할 수 있는 방법이 다양하기 때문입니다.
위에서 사용한 정렬 알고리즘도 정답은 없습니다. 단지 저것은 설명을 드리기위해 예제로 문제 해결상황을 제시해 드린 것에 지나지 않습니다. 이것을 더욱 개선할 방법도 무궁무진 할 것입니다.
기초정렬 알고리즘 개선하기
현재 만들어본 정렬 알고리즘은 최소값의 인덱스만을 순서대로 저장해 간접적으로 정렬을 하여 실제 값을 읽으려면 본래의 배열에 해당 인덱스를 넣어 값을 가져와야 합니다.
만약 직접 값을 읽어올 수 있다면, 정렬 결과를 더욱 쉽게 사용할 수 있을 것입니다. 만약 가능하다면 한번 구현해보시는 것도 좋을 것 같습니다.
정렬을 위해 여러분이 생각한 방법이 다를 수도 있습니다. 그렇게 생각한 다른 방법을 이렇게 소스코드로 구현해보는 것도 좋은 경험이 될 수 있습니다.
문제 해결에 대한 아이디어를 실제 소스코드로 표현할 수 있다면, 여러분은 이미 알고리즘에 대해 훌륭히 배우신 것이라고 할 수 있습니다.
알고리즘은 상황에따라 그것을 만든 사람에 따라 그 기본아이디어가 모두 다를 수 있습니다. 우리는 알고리즘에 대해 익숙해지기 위하여, 몇몇 상황에대한 유명한 알고리즘들을 배워볼 것이며, 알고리즘의 성능을 가늠하는 기준에 대해 알아볼 것입니다.
이것을 통해 여러분은 알고리즘을 해석하고 최적화 할 수 있는 능력을 가지게 될 것입니다.
참고자료 - 숫자배열 정렬, 전체 소스코드
소스코드 :
// 정렬 결과를 담을 배열 및 크기변수 선언
int size = 0;
int result_Idx[4] = { 0, }
// 정렬할 대상을 담은 배열
int -nput[4] = { 3, 5, 2, 1 };
int getMin(int[] array)
{
int min_Idx = 0; // 배열 array 의 최소값을 나타내는 인덱스
for (int i=0; i < sizeof(array); i++)
{
// 추가된 부분
for (int j = 0; j < size; j++)
if (result_Idx[j] == i) continue; // 기존 결과에 포함되었다면 스킵
// 추가된 부분 끝
if (array[min_Idx] > array[i]) {
// 최소값보다 더 작은 값이 나타난다면,
min_Idx = i; // 새로운 값의 인덱스를 최소값으로 기억
}
}
}
void main()
{
// 구한 최소값의 인덱스를 배열에 저장
for (int i = 0; i < sizeof(-nput); i++)
result_Idx[size++] = getMin(-nput);
// 정렬된 인덱스를 확인한다.
cout << "result_Idx :" << endl;
for (int i = 0; i < sizeof(-nput); i++)
cout << -nput[result_Idx[i]] << ", ";
cout << endl;
cout << "정렬결과 :" << endl;
// 정렬된 인덱스를 통해 값을 읽어서 보여준다.
for (int i = 0; i < sizeof(-nput); i++)
cout << -nput[result_Idx[i]] << ", ";
cout << endl;
}
출력결과 :
result_Idx :
3, 2, 0, 1
정렬결과 :
1, 2, 3, 5
계속하려면 아무 키나 누르십시오...