Algorithm (1)

지금까지 취업 준비를 위해 코딩 테스트를 위해 수많은 알고리즘 문제를 풀어보았다.

그렇다면 나는 알고리즘 그 자체에 대하여 얼마나 알고 푸는 것일까? 라는 궁금증으로 이와같은 카테고리를 생성하여 그저 테스트만을 위한 알고리즘 공부가 아닌 순수히 알고리즘 자체를 이해하는 시간을 가져보고자 한다.

1.  그리하여 알고리즘이란?

간단히 설명하자면, 알고리즘은 결국 문제를 해결하는 단계적 절차 또는 방법, 명령어들의 집합이라고 할 수 있다.

알고리즘은 컴퓨터에만 적용되는것은 아니다. 예를 들어, 컴퓨터가 이해하지 못하는 의사코드를 통한 알고리즘 혹은 수학적인 이론에서 발생한 알고리즘이 있을 수 있다.

1.1  알고리즘의 일반적인 특성은?

- 정확성 : 주어진 입력에 대하여 올바른 해를 출력해야한다.

- 수행성 : 알고리즘의 각 단계는 컴퓨터에서 수행이 가능해야 한다. 애매모호한 표현은 프로그래밍 언어로 바꿀 수 없다.

- 유한성 : 일정한 시간 내에 종료되어야한다.

- 효율성 : 효율적일수록 알고리즘의 가치가 높아진다. 그러나 효율적인 알고리즘만이 알고리즘은 아니다. 

2.  최초의 알고리즘?

그렇다면, 최초의 알고리즘은 무엇일까? 

유클리드(Euclid)의 최대공약수를 찾기

유클리드는 수학문제를 풀어본 사람들이라면 꼭 한번쯤 들어보았을 것이다.

유클리드는 2개의 자연수의 최대공약수는 큰수에서 작은수를 뺀 수와 작은 수와의 최대공약수와 같다는 성질을 이용하여 최대공약수를 찾았다.

예시를 통해 함께 확인해보자

최대 공약수 (24, 14) = 최대 공약수 (24-14 , 14)         = 최대 공약수(10, 14) = 최대 공약수 (14-10, 10)           = 최대 공약수(4, 10) = 최대 공약수 (10-4, 4)              = 최대 공약수(6, 4) = 최대 공약수 (6-4, 4)                = 최대 공약수 (2, 4) = 최대 공약수 (4-2, 2 )               = 최대 공약수 (2, 2) = 최대 공약수 (2-2, 2)                = 최대 공약수(2, 0) = 2

아래는 위의 최소공약수를 구하는 방법을 Java 코드로 작성한 것이다.

참고로 빼기도 가능하지만, 나눗셈을 사용하면 더욱 빠르게 문제를 해결 할 수 있다.

public class Euclid {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(leastCommonFactor(24,14));
		System.out.println(leastCommonFactor(16,4));
		System.out.println(leastCommonFactor(5,2));
		
	}
	
	public static int leastCommonFactor(int a, int b) {
//		a >= b >= 0
		if(b==0) return a;
		return leastCommonFactor(b, a%b);
	}

}

코드로 작성한 알고리즘은 알고리즘을 표현하는 하나의 방법일 뿐이다.

그외에도 알고리즘 표현 방법이 있다.

1) 말로 표현된 알고리즘

2) 의사 코드로 표현된 알고리즘 

 

간단하게 알고리즘에 대하여 생각하는 시간을 가져보았다.

다음에는 어떤 알고리즘이 있는지에 대하여 공부해보도록 하겠다.