알고리즘 (Algorithm) 기초 개념과 조건, 복잡도

알고리즘은 무엇인지 소개해 드리고 알고리즘 표현 방법과 조건 그리고 공간복잡도, 시간복잡도에 대해 쉽게 설명드리겠습니다. 

 

 

목차

 

 

알고리즘 소개

 

알고리즘 개요

알고리즘은 문제를 해결하기 위한 절차나 방법으로 어떠한 행동을 하기 위해 만들어진 명령어들의 유한집합(finite set)입니다. 유한 집합의 각 단계는 하나 또는 그 이상의 연산을 필요로 합니다.

 

예를 들어 볼게요 강남에서 분당까지 가야해요. 가는 방법은 광역버스, 지하철, 택시, 도보? 등 여러가지 방법이 있어요. 알고리즘은 문제를 해결하는 절차나 방법이라고 말씀드렸죠? 여기서 문제는 강남에서 분당을 가는 것이고 절차는 방법은 이동하는 모든 수단이 될 수 있습니다. 

 

그럼 왜 알고리즘이 필요할까요? 강남에서 분당까지 잘 가기 위해서입니다. 최단시간에 가던지, 최소비용으로 가던지 우리는 원하는 방법이 있기 때문입니다.

 

알고리즘 표현

그렇다면 알고리즘은 어떻게 표현할까요?

 

1. 자연어 - 일상생활에서 사용하는 언어를 이용해 표현합니다.

2. 의사코드 (pseudocode) - 인간이 이해하기 쉬운 말로 코드를 흉내 내어 설명되어 있어요,

3. 순서도 - 기호와 도형을 사용하여 표현하는 방식이예요.

4. 프로그래밍 언어 - C언어, 파이썬 등

 

알고리즘 조건

알고리즘에는 다음과 같은 조건이 필요해요.

 

1. 입력 - 0 또는 그 이상의 외부에서 제공된 자료가 존재해야 합니다.

2. 출력 - 최소 1개 이상의 결과를 가져야합니다.

3. 명확성 - 알고리즘의 단계는 명확하여 애매함이 없어야 합니다.

4. 유한성 - 유한한 횟수를 거친 후 문제를 해결하고 종료해야합니다.

5. 효과성 - 모든 연산들은 사람이 종이와 펜으로 유한한 시간 안에 풀 수 있을 정도로 단순해야 합니다.

 

튜링 머신이란 1936년 앨런 튜링이 제안한 수학적 모델로 계산 가능한 문제의 개념을 정의하기 위한 이론적 장치입니다.

알고리즘이란 모든 입력값에 대해 이 튜링 머신이 정지하게 하는 명령입니다. 꼭 정답이 아니더라도 어떠한 입력에도 제한된 시간내에 답을 내고 정지하면 알고리즘인 것이죠.

 

 

 

 

알고리즘 복잡도

그렇다면 어떤 알고리즘이 좋은 알고리즘 일까요? 다음과 같은 복잡도가 알고리즘의 평가기준이 됩니다.

 

공간 복잡도 (Space Complexity)

알고리즘 문제를 해결하는 필요한 공간은 바로 '메모리' 입니다. 컴퓨터의 성능이 좋아지면서 공간 복잡도에 대한 중요성이 낮아지고 있습니다. 

 

시간 복잡도 (Time Complexity)

문제를 해결하는데 걸리는 시간에 대한 평가 방법입니다. 문제를 해결하는데 10년이 걸린다면 활용도가 매우 낮겠죠. 

 

복잡도 표기 방식 (Big-O)

알고리즘이 문제를 해결하는데 걸리는 시간을 표시하는 방식으로  Big-O 표기법  을 사용합니다. 입력 크기 (n)가 커질수로 알고리즘이 소요되는 시간이 어떻게 변화하는 지를 분석하는데 사용됩니다.

 

 

1.  O(1) - 상수 시간 알고리즘  은 입력 크기와 관계없이 일정한 시간이 소요되는 알고리즘을 말합니다.

2.  O(log n) - 로그 시간 알고리즘  은 입력 크기가 2배로 증가할 때 반복 횟수가 일정 비율로 증가하는 알고리즘입니다.

3.  O(n) - 선형 시간 알고리즘  은 입력 크기와 실행 시간이 비례합니다. 입력 크기가 2배로 늘어나면 실행 시간도 2배로 늘어납니다.

4.  O(n log n) - 선형 로그 시간 알고리즘  은 로그 시간 알고리즘을 반복할 때 발생하며 정렬 알고리즘에서 많이 나타납니다.

5.  O(n^2) - 이차 시간 알고리즘  은 반복문이 중첩되어 있을 때 발생하는 시간 복잡도입니다.

 

O(n) 선형 시간 알고리즘의 복잡도를 가지면 좋은 알고리즘이라고 볼 수 있습니다. O(2^n) 이나 O(n!) 같은 복잡도를 가지는 알고리즘은 굉장히 비효율적일 수 있지만 이 복잡도의 알고리즘밖에 방법이 없는 어려운 문제들도 있기 때문에 사용할 수 밖에 없죠.

 

---

 

지금까지 알고리즘란 무엇인지 어떤 알고리즘이 좋은 알고리즘인지 간단하게 설명드렸습니다. 알고리즘이 무엇인지에 대해 감을 잡는 정도면 충분할 것 같습니다. 다음 포스팅은 알고리즘의 종류에 대해서 말씀드리겠습니다.

 

관련포스트

알고리즘 | 종류 (탐색, 정렬, 그리드)

게임 알고리즘 (레벨업, 데미지, 피해량)

딥러닝과 머신 러닝 개요