C로 다시보는 알고리즘 01 – 알고리즘이란

어떤 문제를 해결하기 위한 논리나 절차를 알고리즘이라고 한다. 하나의 문제를 해결하기 위한 알고리즘의 형식은 다양하지만, 일반적으로는 사람이 생각하는 알고리즘을 그대로 적용하는 데에는 한계가 있다.

예를 들어서 최대 공약수를 구하는 방법에 대해서 생각하게 되면, 두 수의 약수를 찾는 것은 사람의 경험적 직감에 의존하게 된다. 경험에 따라 문제를 해결하기 위해 접근하는 숫자에 대해서 도중식이 다를 수 있다. 이를 컴퓨터에서 실행한다면 논리가 엄청나게 복잡해지게 된다. 그래서 이를 기계석인 방법(=정형화된 수식화)을 통해서 해결하는데 유클리드 호제법을 이용한다.

그리고 하나의 문제를 해결하기 위해서는 여러 방법이 존재할 수 있다. 이 중에서 가장 적합한 방법의 알고리즘을 찾는 것 또한 중요하다. 그러한 것을 찾기 위해서는 여러 요건들이 존재한다.

  1. 신뢰성이 높을 것
    정밀도가 높고 올바른 결과를 얻을 수 있어야 함.
  2. 처리 효율이 높을 것
    계산 횟수가 적고 처리 속도가 빨라야 한다. 알고리즘의 효율성은 O 표기법(Big-O Notation) 단위를 사용하여 처리하는데, 이에 대해서는 뒤에서 추가로 설명한다.
  3. 일반적일 것
    특정 상황에서만 사용되는 알고리즘이 아닌, 다양한 상황에서 통용될 수 있어야 한다.
  4. 확장성이 있을 것
    변경 사항을 간단하게 수정할 수 있어야 한다.
  5. 알기 쉬울 것
    누가 봐도 알기 쉬워야 한다. 이해하기 힘든 알고리즘은 프로그램의 유지, 보수에 엄청난 걸림돌이 된다.
  6. 이식성이 높을 것
    유용한 프로그램은 다른 곳에서도 사용할 가능성이 높다. 따라서 프로그램의 이식성을 높일 수 있도록 해야 한다. 그 프로그램에서 이용된 알고리즘 또한 마찬가지이다.

이 알고리즘이 학문적일 경우에는 사실 1,2번에만 신경을 써도 된다. 그러나 실제로 사용할 경우에는 어느 정도 나머지 것들에 대해서도 고려를 해야 한다.

또한 컴퓨터에서는 다양한 형테의 데이터를 다루게 되는데, 데이터를 처리하는 데에는 특정한 데이터 구조(자료 구조)를 사용하느냐에 따라서도 문제 해결에 필요한 알고리즘이 생기게 된다. 이 이야기는 “Algorithms + Data Structure = Program” (Prentice-Hall, 1976)이라는 책에서도 언급되었던 내용이다. 데이터 구조와 알고리즘은 밀접한 관련이 있으므로 좋은 데이터 구조를 선택하는 것은 좋은 프로그램을 만드는 기초로 이어지게 된다. (그래서 자료구조도 중요하다)

그래서 이 블로그에서는 알고리즘에 대한 이야기를 주로 작성하지만 일반적인 자료구조에 대해서도 다루게 될 것이다.