알고리즘이란?

“알고리즘”은 다음과 같이 정의할 수 있습니다.

문제를 해결하기 위한 것으로, 명확하게 정의되고 순서가 있는 유한 개의 규칙으로 이루어진 집합

간단하게는 문제 풀이에 필요한 계산 절차, 처리 과정의 순서를 뜻합니다. 알고리즘은 언제나 명확하게 정의되어야 하기 때문에 대입되는 변수들에 따라 항상 옳은 값이 도출되지 않고 결과가 달라진다면 알고리즘이라 할 수 없습니다. 간단한 예시를 통해 프로그래밍에서의 알고리즘을 알아보겠습니다.

세 값의 최댓값 구하기

import java.util.Scanner;

public class getMaxValue {
    public static void main(String[] args) {
        Scanner numScan = new Scanner(System.in);
        int[] numArr = new int[3];
        int maxValue = 0;

        //3개의 값을 받아옵니다.
        for(int i = 0; i < 3; i++) {
            numArr[i] = numScan.nextInt();
        }

        //제일 첫 번째 값을 임시 최댓값으로 지정합니다.
        maxValue = numArr[0];

        //순회 알고리즘을 사용합니다.
        //두 번째 값부터 임시 최댓값과 비교하며 최댓값을 찾습니다.
        for(int j = 1; j < 3; j++) {
            if(numArr[i] > maxValue) {
                maxValue = numArr[i];
            }
        }

        System.out.println("최댓값은 : " + maxValue);
        numScan.close();
    }
}

위 프로그램은 Java로 작성되었습니다. 반복문을 통해 사용자로부터 받아온 3개의 변수를 배열 자료구조에 저장했고, 조건문을 반복문으로 여러번 수행해 원하는 결과를 도출하기 위한 프로그램을 작성했습니다. 입력된 3개의 변수의 순서와 상관 없이 항상 최댓값을 출력하므로 이 프로그램은 알고리즘이라 할 수 있습니다. 이 짧은 프로그램에서 우리는 알고리즘을 작성할 때 자주 사용하게 되는 여러 요소들을 확인해볼 수 있습니다. 이 알고리즘은 데이터의 처음부터 끝까지 모두 탐색하는 “순회”(Traverse) 알고리즘입니다.

알고리즘은 “명확히 정의된, 문제 해결을 위한 순서가 있는 계산 절차 혹은 처리 과정”입니다. 우리에게 주어진 문제는 무척 간단할 수도 있고 매우 복잡할 수도 있습니다. 우린 이런 다양한 문제들을 해결하기 위해 알고리즘을 설계할 때, 여러 조건 판단에 따른 분기점을 만들기도 하고 같은 동작을 여러번 반복해야할 때도 있습니다.

이때 사용하게 되는 것이 바로 “조건문”과 “반복문”입니다. 또, 이 과정에서 많은 양의 데이터를 다뤄야하기도 하는데, 이때 사용하는 것이 자료구조입니다. 자료구조는 데이터를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법을 말합니다. 알고리즘 설계자는 문제를 최대한 빠르게, 자원을 절약하며 해결할 수 있도록 설계해야하고 이를 도와주는 자료구조는 알고리즘과 떼어놓기 힘든 사이입니다.

알고리즘 개선하기

지금까지 알고리즘이 무엇인지 대략적으로 알아봤습니다. 알고리즘은 명확히 정의되어 있어야하며, 빠르고 효율적으로 작성되면 더욱 좋습니다. 시간과 자원이 낭비되면 예기치 못한 일이 발생할 수 있기 때문입니다. 나중에 알아볼 “시간 복잡도”(Time Complexity)와 “공간 복잡도”(Space Complexity)를 통해 내가 작성한 알고리즘의 성능을 확인할 수 있습니다.

알고리즘을 개선하는데 있어 가장 먼저 생각해볼 수 있는 것은 “불필요한 연산을 줄이자.”입니다. 알고리즘이 수행되는데 들어가는 모든 연산 과정은 결국 복잡도를 높이게 됩니다. 적은 양의 데이터만 다룰 때는 오히려 복잡도가 높은 알고리즘이 더 빠르게 결과를 도출하는 상황도 있지만 데이터의 양이 무한히 커질 수록 복잡도가 높으면 그만큼 소모되는 시간과 공간도 기하급수적으로 커집니다.

우리가 알고리즘의 성능을 판단할 때는 주로 “최악의 상황”을 기준으로 판단하기 때문에 알고리즘을 개선할 수 있다면 최대한 개선해주는 것이 좋습니다.

소수 찾기 소수(Prime Number)는 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는, 1보다 큰 자연수입니다. 소수를 찾는 알고리즘은 정말 다양한 방법으로 작성할 수 있습니다. 소수 찾기 알고리즘을 개선해 나가봅시다.

//알고리즘으로 소수를 찾아봅시다
import java.util.Scanner;

public class searchPrimeNumber {
    public static void main(String[] args){
        Scanner numScan = new Scanner(System.in);
        int counter = 0; //연산 횟수 확인 변수
        boolean isPN = true; //소수 여부 판단

        int endRange = numScan.nextInt();
        //소수는 1보다 큰 자연수
        for(int i = 2; i <= endRange; i++) {
            //소수 판단 후 변수 초기화
            isPN = true;
            //판단할 수 전까지 전부 하나 씩 나눠봄
            for(int j = 2; j < i; j++) {
                counter++;
                //나누어 떨어지면 소수 아님
                if(i % j == 0) {
                    isPN = false;
                    break;
                }
            }
            //반복문이 종료 되면...
            //1과 자기 자신을 제외하고 나누어떨어지지 않으므로 소수
            if(isPN == true) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
        System.out.print("연산 횟수는 : " + counter);
        numScan.close();
    }
}

이 알고리즘으로 어떤 범위가 주어지든 항상 범위 안의 모든 소수를 찾아낼 수 있습니다. 그러나 최선의 알고리즘은 아닙니다. 일단 범위가 매우 커지면 연산 횟수가 너무 많아집니다. 매번 1부터 소수인지 판단하려는 수까지 나눗셈을 수행해야합니다. 만약 판단하려는 범위가 매우 커지면 그만큼 나눗셈도 많이 수행됩니다. 이는 단순히 생각해봐도 비효율적입니다.

이 알고리즘을 개선하기 위해 소수의 또다른 성질을 알아내야 합니다. 소수를 판단할 수 있는 더 세부적인 성질을 우리가 미리 판단해준다면 컴퓨터의 연산 수행 시간을 획기적으로 줄일 수 있습니다.

자연수는 소수인 2나 3으로 나누어 떨어지지 않을 때, 4(2 × 2)나 6(2 × 3) 같은 합성수로도 나누어 떨어지지 않습니다. 합성수는 소인수분해를 통해 여러 소수들의 곱으로 나타낼 수 있고, 다시 말해서 소수들의 곱인 합성수로 나누는 것은 소수로 나누는 것과 같은 결과가 나온다는 것입니다. 즉, 소수는 소수로 나누었을 때 나누어 떨어지지 않습니다.라는 특징을 얻을 수 있습니다. 또한 2라는 소수로 모두 나누어 떨어지는 짝수는 계산할 필요 없이 모두 합성수입니다.

이렇게 알아본 소수의 특징을 통해 다시 알고리즘을 작성해보겠습니다.

//개선된 알고리즘으로 소수를 찾아봅시다
import java.util.Scanner;

public class searchPrimeNumber {
    public static void main(String[] args){
        Scanner numScan = new Scanner(System.in);
        int counter = 0; //연산 횟수 확인 변수
        int index = 0; //소수 배열 인덱스
        int end = numScan.nextInt(); //소수 찾을 범위
        int[] primeNumbers = new int[end]; //소수 배열

        //2와 3은 명백히 소수다
        primeNumbers[index++] = 2;
        primeNumbers[index++] = 3;

        //홀수들만 소수인지 확인하기
        for(int i = 3 ; i <= end; i+=2) {
            int j;
            for(j = 1; j < index; j++) {
                counter++;
                //소수 배열의 수들과 나누어 떨어지면 소수가 아님
                if(i % primeNumbers[j] == 0) {
                   break;
                }
            }
            if(index == j) {
                primeNumbers[index++] = i;
            }
        }

        for(int k = 0; k < index; k++) {
            System.out.print(primeNumbers[k] + " ");
        }
        System.out.println();
        System.out.print("연산 횟수는 : " + counter);
        numScan.close();
    }
}

첫 번째 알고리즘은 1,000까지의 자연수 중 소수를 찾을 때, 무려 78,022회의 연산 끝에 모든 소수를 찾아냈습니다. 그에 반해 두 번째 알고리즘은 14,623회만에 모든 소수를 찾아냈습니다. 굳이 하지 않아도 될 연산을 배제한 결과 약 1/5로 연산 횟수를 줄일 수 있었습니다. 두 알고리즘 모두 “주어진 범위에서 모든 소수를 구하라.”라는 문제를 해결하는데는 적당한 알고리즘입니다. 소수를 빠짐없이 구하는데는 아무런 문제가 없습니다. 그러나 두 번째 알고리즘이 훨씬 좋은 알고리즘인 것은 틀림 없습니다.

알고리즘은 사람마다 각각 생각하는 방식이 다른 것처럼 정말 다양한 알고리즘이 있습니다. 어떤 문제에 대한 정답을 정확히 도출해낸다면 모두 알고리즘입니다. 그러나 “좋은 알고리즘”에 대해서는 대다수의 사람들이 비슷하게 생각할 것입니다. 저는 더 빠르고 효율적이고 절약적인 알고리즘이 좋은 알고리즘이라고 생각합니다.

알고리즘이란?

목차

알고리즘이란?

알고리즘 개선하기

Table of contents