알고리즘

 1  알고리즘 개념과 자료구조의 관계

알고리즘(Algorithm)이란 '어떤 문제를 해결해 가는 논리적인 과정' 이다.

자료구조와 알고리즘은 상당히 밀접하고 상호의존적이라고 볼 수 있다.

학술적인 의미에서 자료구조와 알고리즘을 정의하면

자료구조란 컴퓨터 분야에서 효율적으로 접근하고 수정할 수 있도록 자려를 구성, 관리, 저장하는 것이다.

알고리즘이란 컴퓨터 분야나 수학 등 관련 분야에서 어떤 문제를 해결하기 위해 정해진 일련의 단계적 절차나 방법을 공식화한 형태로 표현하는 것을 의미한다.

 

 2  알고리즘 표현법

알고리즘을 표한하는 방법을 알아본다.

• 일반 언어 표현
  • 자연어를 사용해서 설명하듯이 알고리즘을 표현하는 방법이다.
  • 일반 사람이 이해하기 쉬우나, 코드로 변경하는 것에 한계가 존재한다.
  • 생각 법위를 넓히는 단계 정도에서 사용하자.
• 순서도를 이용한 표현
  • 순서도(Flowchart)는 여러 종류의 상자와 상자를 이어주는 화살표를 이용해서 명령 순서를 표현하는 방식이다.
  • 간단한 알고리즘은 쉽게 표현 가능하지만 복잡한 알고리즘은 순서도로 표현하기 어려운 경우가 많다.
• 의사코드를 이용한 표현
  • 의사코드(Pseudo Code)는 프로그래밍 언어보다는 좀 더 인간의 언어에 가까운 형태다.
  • 알고리즘을 좀 더 명확하게 정립하는 데 도움이 된다.
• 혼합 형태
  • 간단한 알고리즘은 직접 코드로 작성한다.
  • 복잡한 알고리즘은 일반언어, 의사코드, 순서도, 그림등을 종합적으로 활용해서 표현한다.

 

 2  알고리즘의 성능

한가지 문제도 주어진 상황에 따라 수십 가지의 알고리즘으로 해결할 수 있다. 

하지만 어떤 알고리즘은 1000초가 걸리기도 하고, 어떤 알고리즘은 몇 초만에 해결 해주기도 한다.

그렇기에 시간이 훨씬 적게 걸리는 알고리즘을 좋은 알고리즘이라고 평가할 수 있다.

이런 알고리즘 성능 분석 방법을 시간 복잡도(Time Complexity)라고 한다.

 

알고리즘 성능은 다양한 표기법으로 비교할 수 있는데 가장 많이 사용하는 것은 빅 - 오 표기법(Big - Oh Notation)으로 O(f(n) 형태로 표기한다.

빅 - 오 표기법에서는 가장 높은 항만 표기하고 계수는 생략한다.  ex) (5n² + n + 100)  -> O(n²)

그래프를 보면 O(2^N)의 시간 복잡도 알고리즘은 데이터가 개수가 몇개 되지 않더라도 시간이 기하급수적으로 중가하는 것을 확인할 수 있다.

버블 정렬의 경우 O(n^2)의 시간 복잡도를 가지고 퀵 정렬은 O(n log n)의 시간 복잡도를 가진다면 퀵정렬이 더 효율성이 좋은 알고리즘이라고 할 수 있다.

성능이 좋지 않은 알고리즘일수록 데이터 개수의 따라 연산 수가 가파르게 증가한다.