알고리즘(Algorithm)이란?

대수학의 아버지 al - khwarizmi

알고리즘이란?? 문제를 해결하기 위한 절차나 방법을 말한다

 

알고리즘이란 단어의 정의는 대수학의 아버지 알-콰리즈마의 이름에서 유래되었다고 전해지는데,

오늘 날 어떤 문제를 푸는 알고리즘이란 어떤 입력에서 정확한 출력을 유한한 시간에 내는 프로그램을 일컫는다.

 

• 여기서 어떤 입력이란? 주어진 입력의 크기와 관계없이 문제를 풀 수 있음을 뜻하는데 문제에 따라서는 음수도 될 수 있고 매우 크거나 작은 수(double 자료형의 범위 밖)가 될 수도 있다.
• 정확한 출력은 말 그대로 코드를 짠 프로그래머가 원하는 결과값을 나오게함을 의미한다.
• 유한한 시간은 여러 알고리즘 문제 사이트에서 볼 수 있는 시간 제한 내에 풀 수 있는지를 뜻한다. 예를 들어 내가 짠 코드가 무한루프에 빠지게 되거나 정말 터무니없는 반복을 할 때 시간 초과가 나오면서 문제가 틀리게되는 것이다.

 

그렇다면 어떻게 코드를 짜야 이 조건들을 모두 만족시킬 수 있을까??

답은 문제의 요구 사항에 따라 다르다. 하지만 알고리즘을 배우는 목적은 적은 메모리를 사용하고 빠른 시간에 동작하기 위함이다. 이는 데이터의 크기가 커질 수록 중요한 문제이다. 또한 다른 사람들과 협업을 할 때 내가 짠 코드가 간결해야 다른 사람이 봐도 이해하기 쉽고, 코드의 유지 보수에 유리하기 때문이다.

 

여기까지는 말로 설명해 이해가 안될 수 있으니 바로 문제로 넘어가자.

 

문제 1. 100명의 학생들의 시험점수 중 최대값을 구하시오.

 

해결방법 1. 입력으로 주어지는 100명의 학생들의 시험점수를 배열에 저장한 후 정렬하고, 이후 그 배열의 마지막 인덱스 값을 출력한다. 

해결방법 2. 먼저 최대값을 의미하는 변수(max)를 설정해둔다. 이후 위와 같이 시험점수들을 배열에 저장하고, for문을 이용해 저장된값들을 하나씩 비교해가며 지금까지 나온 수들보다 높을 때 최대값을 교체한다.

 

결론부터 말하자면 해결방법 2가 최적성의 증명(모든 알고리즘 중 이보다 더 좋은 시간 복잡도를 얻을 수 없음을 증명)을 만족시킨다.

 

우선 이 문제를 풀기 위해서 반드시 해야하는 일은 100개의 시험점수를 한 번씩 거쳐야하는 일이다. 하나라도 덜 거치게되면 절대 최대값을 구할 수 없다. 해결방법 1에서의 정렬도 모든 정렬이 배열에있는 값들을 최소한 한 번씩은 거쳐서 정렬을 하게된다. 하지만 정렬 중 가장 빠른 퀵정렬도 정렬을 하는데에 O(nlogn) 만큼의 시간이 필요하기때문에 이 문제를 정렬로 풀기엔 너무 아깝다...(시간이)

해결방법 2는 for문을 한 번만 써서 딱 한 번씩 주어진 값들을 거치기 때문에 여기서 시간 복잡도는 O(n)이다.

따라서 이 문제는 해결방법2로 푸는것이 현명하다.

 

 

문제 2. 100명의 학생들의 시험 점수중 가장 자주 나오는 값을 구하시오.

 

100개는 너무 많으니 예시로 몇 개의 수만 뽑아보자.  1 5 6 2 1 3 4 6 7

 

해결방법 1. 왼쪽부터 시작해 자기 오른쪽 숫자들을 모두 비교하면서 나오는 횟수를 비교한다.

값	1	5	6	2	1	3	4	6	7
횟수	2	1	2	1	x	1	1	x	1

 이런식으로 자기 자신을 포함하여 오른쪽에 자신과 같은 값이 나온 횟수를 카운트해서 적어준다.

단, 똑같은 값이 또 나올 때는 무시하고 넘어간다(x표시)

이후 가장 높은 값이 나온 수를 뽑으면 된다.

이 방법의 비교 횟수는 (n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2  -> O(n^2)이다.

 

해결방법 2. 주어진 값들을 정렬한 후, 왼쪽부터 세어나가면서 같은 값이 나온 수를 센다.

값	1	1	2	3	4	5	6	6	7
누적횟수	1	2	1	1	1	1	1	2	1

 max_count를 만들어 이거보다 많이 나오면 max_count를 바꿔주는 형식으로 왼쪽부터 오른쪽까지 비교한다.

정렬 시 nlogn의 시간 + 비교하는데 n = n < nlogn이므로 이 방법에대한 시간복잡도는 O(nlogn)이다.

이를 코드로 구현하면

#include <iostream>
#include <algorithm>
using namespace std;
 
int main()
{
    int stu_score[9] = { 1,5,6,2,1,3,4,6,7 };
    sort(stu_score, stu_score+9);
    int max_cnt = 0; int max_num = 0;
    int cnt = 0;
    int num = stu_score[0];
    for (int i = 0; i < 9; i++) {
        if (num == stu_score[i]) {
            cnt++;
            if (cnt > max_cnt) {
                max_cnt = cnt;
                max_num = num;
            }
        }
        else {
            num = stu_score[i];
            cnt = 1;
        }
    }
    printf("%d", max_num);
}

이런 식으로 표현가능하다.

 

그런데, 이 보다 더 좋은 방법이 있을까?

풀이 3. 값들을 이진 탐색 트리에 넣고, 같은 값이 있으면 빈도수를 늘리는 방법이다. 이는 트리의 특성상 서로 다른 값이 없는 경우 nlog1의 시간에도 풀 수 있다. (보통 nlogk (서로 다른 값이 k가지))

이 방법은 이해하는데에 난이도가 좀 있기때문에 이후에 트리를 배울때 차근차근 알아가도록 하자.