Basic

알고리즘 기초

알고리즘은 완전탐색(Brute-Force, 모든 경우의 수를 탐색해보는 것)에서 시작한다. 이는 모든 경우의 수를 다 따져보기 때문에 강력하지만, 최대의 시간복잡도를 가지게 된다. 모든 경우의 수를 생각해보고, 시간복잡도를 줄일 수 있는 부분이 있다면 그러한 알고리즘을 생각해보고, 그 알고리즘을 정확하게 코드로 구현할 수 있어야 한다. 좋은 코드를 짜기 위해서는 다음 과정의 연습이 필요하다.

• 문제를 파악하고 알고리즘을 생각하기
• 알고리즘의 공간복잡도와 시간복잡도를 계산하여 문제의 제약 조건 내에 수행될 수 있는 알고리즘인지 판단하기
• 알고리즘을 빠르고 정확하게 구현하기 (연습만이 정답)

알고리즘(Algorithm) 이란?

문제를 해결하기 위한 여러 동작들의 모임을 말하며, 고대 페르시아의 수학자 알콰리즈미(Al-Khwarizmi)에서 유래하였다.

알고리즘의 조건

• 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다.
• 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다.
• 입력 : 정의된 입력을 받아들일 수 있어야 한다.
• 출력 : 답으로 출력을 내보낼 수 있어야 한다.
• 유한성 : 특정 수의 작업 이후에 정지해야 한다. (정지 조건)
• 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다.

시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)

구현한 알고리즘의 효율성을 따질 때 시간복잡도와 공간복잡도의 개념이 나온다.
입력 데이터의 크기가 커질수록 알고리즘의 성능 차이는 두드러진다. 성능이 좋지 않은 알고리즘일 경우 입력 데이터의 크기가 커졌을 때 실행 시간이 빠르게 늘어난다. 따라서 문제에 따라 미리 시간복잡도를 계산해보고 문제 조건에 적합한 알고리즘인지 판단하는 과정이 중요하다.

시간복잡도(Time Complexity)

시간복잡도란 작동하는 알고리즘의 수행시간을 정량화하는 것을 뜻한다.
알고리즘의 시간복잡도는 연산의 횟수 T(N)을 구하는 방법이 주로 쓰인다. 보통 1억(10^8)번의 연산당 1초의 시간이 걸린다고 간주한다.

시간복잡도의 표기법

• 빅-오(Big-Oh, ) 표기법 : Worst Case의 연산횟수를 나타낸다.
• 빅-오메가(Big-Omega, ) 표기법 : Best Case의 연산횟수를 나타낸다.
• 빅-세타(Big-Theta, 표기법 : Average Case의 연산횟수를 나타낸다.

일반적으로 시간복잡도를 표현할 땐 **빅-오 표기법(Big-O Notation)**을 사용한다. 빅-오 표기법은 연산 횟수 T(N)에서 최고차항만을 표기하는 표기법이다. 알고리즘의 실행 시간이 n + n^2에 비례한다고 할 때, n이 매우 커지면 n^2이나 n + n^2이나 큰 차이가 나지 않게 되기 때문이다.

시간복잡도의 종류

• 상수형 O(1) : 항상 일정한 시간 안에 실행 완료
• 로그형 O(logN) : 실행 시간이 입력 크기의 로그에 비례해서 늘어남
• 선형 O(N) : 실행 시간이 입력 크기에 바로 비례 (선형적으로 증가)
• 선형로그형 O(NlogN) : 선형 알고리즘과 다항식 알고리즘의 중간쯤 속도
• 다항식형 O(N^c) : 입력 크기가 늘어나면 실행 시간이 빠르게 늘어남
• 지수형 O(c^N) : 다항식 알고리즘보다도 더 빠르게 늘어남
• 팩토리얼형 O(N!) : 가장 느린 알고리즘. n이 작아도 금방 거의 쓰기 힘든 수준으로 느려진다.

그림을 보면 알 수 있 듯이, O(n^2)부터 실행 시간이 크게 늘어난다. 선형로그형(준선형) O(NlogN) 알고리즘 또는 그보다 더 빠른 알고리즘을 찾으면 애플리케이션 성능을 크게 향상시킬 수 있다.

공간복잡도(Space Complexity)

공간복잡도란 알고리즘의 메모리 사용량에 대한 분석 결과로, 알고리즘 문제를 해결하기 위해 사용하는 메모리의 크기를 말한다. 임베디드 시스템처럼 제약이 많은 환경에서는 메모리 용량이 실행 시간 못지않게 중요하다.

이를 잘 알기 위해서는 자료형 별 메모리 크기가 어떤지, 실제 자료구조가 어떻게 구현되는지 등을 제대로 이해하는 것이 중요하다.