[Python Algorithms] 알고리즘 O 표기법

 

최근 가장 핫한 키워드를 하나만 뽑으라면 단연 알고리즘일 것이다. (아마도..)

 

많은 회사들이 개발자 입사 시험에 알고리즘 테스트를 넣고 있고

개발자의 역량 강화에서도 중요한 부분이라고 알려져 있어

많은 사람들이 관심을 가지고 공부하고 있다.

나도 마찬가지로 입사를 위해서..ㅋㅋ 열심히 공부하고 있는 중이다.

 

 

먼저 알고리즘이 무엇인지 살펴본 뒤, 알고리즘을 어떻게 평가해야하는지,

파이썬으로 알고리즘을 어떻게 표현할 수 있을지를 다뤄보려 한다.

 

 

 

 

---

 

 

 

 

알고리즘 모식도

알고리즘

 

알고리즘은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해

정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것 [출처: 위키백과] 이라 설명되어 있다.

 

나는 특히 컴퓨터 과학에서 알고리즘을

"주어진 환경에서 컴퓨터로 문제를 효율적으로 해결할 수 있게 하는 방법.."

정도로 생각하고 있다.

 

특정한 상황에서 사용될 수 있는 알고리즘은 무수히 많으며

각기 다른 방법으로 구현되고 있다.

 

모든 알고리즘이 같은 형태라고 말하기는 어렵지만

같은 논리구조를 가지고 있는 단위로 나눠 구분할 순 있다.

 

대표적인 여러가지 알고리즘을 살펴보기 전에,

어떤 알고리즘을 선택해야 하는지에 대한 설명을 해보려 한다.

 

 

 

 

---

 

 

O 표기법

 

알고리즘을 잘 만들고 잘 사용하려면

먼저, 문제를 해결할 때 어떤 알고리즘이 잘 맞는지,

어떤 알고리즘이 안 좋은지를 판단하는 것이 중요하다.

 

알고리즘을 판단할 때는 알고리즘의 실행시간이나 메모리의 효율성 등

여러 방면에서 판단해볼 수 있지만,

주로 제어문(특히 반복문)이 그 알고리즘의 성능을 판단하는데 큰 영향을 끼친다.

 

알고리즘은 시스템과 같은 여러 환경에 의해 그 성능이 달라질 수 있기 때문에

항상 최악의 상황을 고려하는 방법을 사용해야 한다.

 

이런 이유로, 알고리즘의 비교에 있어 가장 많이 사용되는 방법은

바로 O(영어 오)표기법이다.

 

 

 

 

O 표기법에는 7가지 정도로 분류할 수 있다.

 

1. O(1) - 데이터의 양과는 상관없이 항상 같은 실행시간을 가지는 알고리즘을 말한다.

 

2. O(log2N, 밑이 2인 로그) - log 그래프의 형태처럼 완만한 상승곡선을 띄고 있는 알고리즘으로

                                     데이터 양이 증가할수록 실행시간도 조금씩 증가하는 알고리즘을 말한다.

 

3. O(N) - 데이터양이 증가할수록 실행시간이 비례적으로 증가하는 알고리즘을 말한다.

 

4. O(NlogN) - 데이터 양이 증가할수록 O(N)의 비례적인 증가보다 더 증가하는 실행시간을

                   가지는 알고리즘을 말한다.

 

5. O(N^2) - 처리해야 할 데이터 양의 제곱 배로 시간이 증가하는 알고리즘이다.

                보통 반복문 두 개가 중첩되어 있는 경우의 알고리즘을 말한다.

 

6. O(N^3) - 처리해야 할 데이터의 양의 세제곱 배로 시간이 증가하는 알고리즘이다.

                보통 반복문 세 개가 중첩되어 있는 경우의 알고리즘을 말한다.

 

7. O(2^n) - 처리해야 할 데이터의 양의 2^n 만큼 시간이 증가하는 알고리즘이다.

               일반적으로 좋지 않은 알고리즘이라고 평가된다.

 

 

 

 

앞서, 알고리즘의 평가에서 제어문이 성능 판단에 많은 영향을 끼친다고 말한 바 있다.

O 표기법으로 제어문을 어떻게 표현할 수 있는지 몇 가지 예를 들어보도록 하겠다.

 

 

1. if(else)문은 알고리즘 성능에 영향을 끼치지 않는다.

 

2. 반복문은 최대 반복 횟수를 고려한다.

   for 문의 range가 101이라면 100번의 반복문이 실행될 것이고, 이에 따라 O 표기법은

   O(100)이라고 표기할 수 있는데 O 표기법에서 상수의 경우 무조건 O(1)로 표시하기 때문에

   100번의 반복문을 실행하는 알고리즘의 경우 O(1)로 표기할 수 있다.

   이는 O(N)의 알고리즘을 갖는다고 볼 수 있다.

 

3. 중첩된 반복문의 경우 각 중첩문의 최대 반복 횟수를 곱해야 한다.

   for 문이 두 개의 최대 반복 횟수가 각 각 100, 100회라면 100 x 100인 10000이 되고

   이를 O 표기법으로 표현하면 O(N x N) = O(N^2)으로 표현할 수 있다.

 

4. 반복문이 중첩되지 않았지만 따로 2개 이상 존재하는 경우, 가장 큰 횟수를 가진 값으로 계산한다.

   두 개의 for문 중 하나는 반복횟수가 O(N)이 되고 다른 하나의 경우 O(N^2)이라면

   이 알고리즘의 O 표기법은 O(N^2)이 되는 것이다.

 

5. 재귀 함수는 풀어서 그 반복 횟수를 계산해야 한다.

   재귀함수의 대표적인 경우는 팩토리얼 함수의 경우, 1부터 N까지의 곱을 표현하므로

   호출 수가 N번이 되므로 O(N)의 표기법을 가질 수 있다.

 

 

 

 

 

 

---

 

[참고 문헌]

 

1. 위키백과, "알고리즘", https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

2. 박선주, 영진닷컴, "필수 알고리즘 with 파이썬"