알고리즘

ㅇ2020.12.21 알고리즘 스터디 시작.

# 알고리즘이 뭐죠

* 최초로 사칙연산을 만든 수학자의 라틴어 이름(algorismus) 에서 유래되었다. 참고로 발음이나 표기나 알고리듬이 맞는 표현이나 한국에선 알고리즘으로 많이 불린다.

 

어떠한 문제가 생겼을 때 그 문제를 푸는 방법을 의미한다.

사실 Algorithm은 반복되는 문제를 풀기 위한 작은 procedure(진행절차)를 의미했었다. 컴퓨터가 등장하기 이전부터도 알고리즘이라는 단어는 자주 사용되었으며 컴퓨터의 등장과 함께 여러 알고리즘이 급속도로 발전하게 되었다.

음료수 구매 알고리즘 = 음료수를 구매하는 procedure(진행절차)

 

'알고리즘'은 수학자, 개발자들만 쓰는 공학 용어가 아니라 우리 일상생활에도 사용할 수 있다. 우리가 요리를 하는데 무엇부터 하는게 효율적일지, 길을 잃었는데 어떻게 해야 쉽게 찾을 수 있는지 방법을 고민하는 것도 전부 그 문제를 해결하는 알고리즘을 만드는 과정이다.

---

# 알고리즘의 성능

어떠한 알고리즘을 만들었을 때 성능을 측정하는 방법은 여러가지 방법이 있다.

그 중 가장 쉽게 계산 할 수 있는 방법이 사용하는 시간과 공간을 확인하는 방법이다.

1. 공간 - 메모리를 얼마나 적게 쓰는가?
2. 시간 - 계산 시간이 얼마나 걸리는가?

 

정도가 되겠다. 사실 2000년대 전 만해도 컴퓨터의 메모리는 넉넉하지 않았기 때문에 하드코딩을 해서라도 공간을 어떻게든 확보했던 시절이 있었다. 지금은 넘쳐나는게 메모리이기에 어마어마하게 큰 대형 프로그램가 아니라면 보통 공간보다는 시간 효율을 더 중요하게 본다.

 

하지만 컴퓨터마다, 프로그램 실행환경에 따라 실행시간은 다르게 측정될 것이다. 당연하게도 정말 더럽게 느린 알고리즘과 대부분의 상황에서 빠르게 처리되는 알고리즘은 존재한다. 이를 어떻게 측정하고 구분할 수 있을까?

---

# Big-O 표기법

해당 자료구조(알고리즘)의 대략적인 시간 성능을 알아보는 방법이다.

쉽게 말하면 복잡도(=성능)의 ‘증가율’을 본다는 말이다.

 

자료구조나 알고리즘이 있을 때 대략적인 '작동하는 시간' 성능을 알아보기 위해 사용하는 방법이다. 3개가 증가했을 때 3초가 더걸린다면 $O(n)$, 그의 제곱인 $3^2 = 9$초가 걸린다면 $O(n^2)$ 이런식으로 표기하는 방법이다.

물론 f(n)+100,000 같은 연산을 하는 코드가 있다면, 이렇게 계산하는 방법이 틀린게 아닌가 싶을 수 있겠지만 현대의 컴퓨터 CPU는 초당 억단위로 연산을 한다. 즉 연산 횟수가 어마어마하게 크기 때문에 상수값(100,000)은 신경 쓸 필요가 없다. 그래서 이름이 Big-O (큰 차수만 기록한다는 의미)

 

물론 실제 알고리즘의 성능을 측정 할때는 그 알고리즘의 최악, 평균, 최고 성능을 측정하고 연산 성능을 수식으로 표현하기 어려운 경우가 있다. (ex 바둑, 체스 알고리즘) 하지만 지금 시점에서는 그 정도로 따질 필요는 없으니 궁금하면 해당 링크를 참고하자.

 

## O(log n) 은 어떻게 나오는거죠?

이진 탐색처럼 연산을 1회 할때마다 연산횟수가 제곱으로 줄어들면 log(n) 복잡도가 나오게 된다.

예를 들어 3000페이지를 가진 책에서 내가 원하는 페이지를 찾는 알고리즘을 생각해보자.

책을 펼칠 때 마다 해당 페이지의 위치를 알 수 있으므로, 계속해서 반을 나눠 찾으면 탐색할 범위가

(페이지 수)$  * \frac{1}{2}$ 만큼 줄어든다. 이를 수식으로 n의 개수에 따라 시간이 $O(log_2 n)$으로 변하게 된다.