1. 알고리즘 개요(Algorithm Overview)

알고리즘(Algorithm)

알고리즘은 수학, 컴퓨터과학, 언어학 또는 관련분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.

• 계산 또는 작업을 처리하기 위한 순서
• 요리의 레시피(요리의 재료를 이용하여 레시피 대로 요리한 다음 요리를 완성)
• 특정문제를 컴퓨터로 해결하기 위한 순서
• 어떤 문제를 해결하는 방법을 모두 알고리즘이라 한다.

입력	0개 이상의 입력이 존재햐아한다
출력	1개 이상의 출력이 존재해야한다
명백성	각 명령어의 의미는 모호하지 않고 명확해야한다
유한성	한정된 수의 단계 후에는 반드시 종료되어야한다
유효성	각 명령어들은 실행 가능한 연산이어야 한다

코딩 테스트나 인터뷰에서 알고리즘을 보는 이유는 문제를 모델링하고 해결하는 능력을 알아보기 위해서이다.

알고리즘의 효율성(Efficiency)

알고리즘 문제를 해결하는 어떤 코드를 작성했을 때, 이 프로그램의 효율성을 알고싶을 때

• 수행시간
• 사용한 메모리
• 코드의 길이

중 수행시간이 중요하다.

예를들어 어떤 프로그램을 작성했는데, 시간이 10일 걸리면 10일동안 실행해야하고, 메모리가 64GB가 필요할 경우 메모리가 부족하면 램을 구매하면 된다.
이런 문제를 해결할 때는 시간이 중요.

문제의 크기(Scale Of Problem)

개발중 접하게 되는 문제를 해결하는 과정에는 항상 문제의 크기가 발생한다.

1. '게임 동시 접속자 수', '쇼핑몰 장바구니 물건의 수' 등 이런 문제의 크기를 보통 N이라 하고, N에 따라 걸리는 시간이 다르다.
2. 웹 사이트를 만드는 경우 100명이 동시에 접속하는 것과 10만명이 동시에 접속하는 사이트를 만드는 방법은 큰차이가 있으며 접속자가 많을 경우 사이트를 만드는 방법은 더 어렵다. 이럴 때도 문제의 크기에 따라 최적은 방법을 선택해야한다.

문제를 해결할 때는 문제의 크기를 먼저 보고 방법을 생각해야 한다.

알고리즘의 복잡도 분석(Complexity Analysis)

알고리즘 복잡도 분석은 직접 구현하지 않고 모든 입력을 고려하는 방법으로 하드웨어나 소프트웨어어 환경과 관계없이 알고리즘의 수행시간 및 효율성을 평가할 수 있다.

• 알고리즘이 수행하는 연산의 횟수를 측정
• 연산의 횟수는 N함수로 표현된다.

알고리즘의 분석 방법에는 기억 공간을 분석하는 공간 복잡도(Space Complexity)와 실행 시간을 분석하는 시간복잡도(Time Complexity)가 있다.

공간복잡도(Space Complexity)

알고리즘의 메모리 사용량에 대한 분석결과로 대략적으로 얼마나 공간을 사용할지 예상할 수 있다.

시간복잡도(Time Complexity)

알고리즘의 수행시간 분석결과로 시간 복잡도를 이용하면 작성한 코드의 수행 시간이 얼마나 걸릴지 예상할 수 있다.

시간복잡도에서 불필요한 정보를 제거하여 알고리즘 분석을 쉽게할 목적으로 빅-오 표기법(Big-O Notation)을 이용하여 복잡도를 표시한다.

빅오 표기법의 수학적 정의

두 개의 함수 $f(n)$ 과 $g(n)$이 주어졌을 때 모든 $n \geqq n_0$ 에 대하여 $|f(n) \leqq c|g(n)|$을 만족하는 2개의 상수 $c$와 $n_0$가 존재하면 $f(n) = O(g(n))$이다

즉 입력크기 N에 대하여 얼마나 시간이 걸릴지 나타내고, 최악의 경우 시간이 얼마나 걸리지 알 수 있다.

빅오 표기법은 연산의 횟수가 다항식으로 표현되었을 경우 다항식의 최고차 항만을 남기고 다른 항들과 상수항을 버리는 것이다. 궁극적으로 최고차 항의 계수도 버리고 단지 최고차 항의 차수만을 사용한다.

1. 상수는 버린다.
   • $O(3N^2) = O(N^2)$
   • $O({1 \over 2} N^2) = O(N^2)$
   • $O(5) = O(1)$
2. 두 개 이상 항이 있을 때 최고차의 항의 차수만 사용한다.
   • $O(N^2 + N) = O(N^2)$
   • $O(N^2 + N\log N) = O(N^2)$
3. 두 가지 항이 있는데 다른 변수가 있으면 둔다
   • $O(N^2 + M)$

대표적인 시간복잡도

• $O(1)$ : 상수
• $O(\log N)$ : 로그
• $O(N)$ : 선형
• $O(N\log N)$ : 선형로그
• $O(N^2)$ : 2차
• $O(N^3)$ :3차
• $O(2^N)$ : 지수
• $O(N!)$ : 팩토리얼

*실행시간 *

$O(1) < O(\log N) < O(N) < O(N\log N) < O(N^2) < O(N^3) < O(2^N) < O(N!)$

Ex1) 1부터 N까지의 합

• i 는 1부터 N번을 수행하므로 시간복잡도 : $O(N)$

 int sum = 0;
 for (int i = 1; i<=N; i++) {
     sum+= i;
 }

Ex2) 1부터 N까지의 합

• N번을 2번 수행하므로 시간복잡도 : $O(N^2)$

 int sum = 0;
 for (int i = 1; i<=N; i++) {
     for (int j = 1; j<=N; j++) {
        sum+= j;
     }
 }

Ex3) 1부터 N까지의 합을 계산

• 1번의 연산만 수행하므로 시간복잡도 : $O(1)$
• int sum = 0; sum = N * (N + 1) / 2;

---

참조

• code.Plus : https://code.plus/course/41
• C언어로 쉽게 풀어쓴 자료구조
• 위키피디아 : https://ko.wikipedia.org/wiki/알고리즘