알고리즘 설계와 분석의 기초

알고리즘이란

문제를 해결하기 위한 단계적 절차를 말한다. 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것이다.

점근적 분석

점근적 분석이란 입력이 충분히 큰 경우에 대한 분석을 말한다. 컴퓨터는 빠른 처리 능력을 가지므로 입력의 크기가 작을땐 속도의 차이가 뚜렷하지 않다. 하지만, 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다.

좋은 알고리즘 = 성능이 좋은 = 효율적인 = 같은 시간에서 더 빠른 알고리즘이다.

알고리즘 표현법

• 순서도를 이용한 표현

  • 여러 종류의 상자와 상자를 이어 주는 화살표를 이용해서 명령 순서를 표현

  • 간단한 알고리즘은 쉽게 표현할 수 있지만, 복잡한 알고리즘은 표현하기 어려운 경우가 많다.

    <순서도 예시>

    

• 의사 코드를 이용한 표현

  • 프로그래밍언어 + 자연어를 사용한 표기법
  • 프로그램 코드를 직접 코딩하는 것 보다 좀 더 명확하게 정립하는 데 도움이 되고 코드에 설명을 달지 않아도 이해하는 데 무리가 없다.

• 프로그램 코드로 표현

  • 실제로 사용하는 프로그래밍 언어의 코드로 바로 작성 가능

알고리즘은 자료구조의 확장이다!
자료구조는 생각의 전개를 위해 필요한 기본적인 도구이다.알고리즘을 설계하는 것은 자료구조에서 출발한다. 어떤 문제를 해결하기 위해서는 자료를 어떻게해야 효율적으로 표현, 조직, 저장 관리할지 알아야하기 때문이다.

몇가지 기초 사항들

1. 알고리즘 분석의 필요성

   알고리즘을 설계한 후 설계한 알고리즘이 자원을 얼마나 소모하는지 분석해야한다.
   여기서 자원은 소요 시간, 메모리, 통신 대역 등이 되는데 대부분 '소요 시간'이 중요한 관심 대싱이다.

   사용하고자 하는 알고리즘의 소요 시간이 입력의 크기에 어떤 비율로 비례하는지 안다면 주어진 시간에 요구하는 작업을 완료할 수 있을지 대략 짐작할 수 있다.

2. 알고리즘의 수행 시간

   알고리즘의 수행 시간 : 입력의 크기에 대해 시간이 어떤 비율로 소요되는지 표현.

3. 재귀(자기호출)과 귀납적 사고

   자기호출은 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식이다.
   수학적 귀납법은 자신보다 작은 문제에 대해 결론이 옳음을 가정하고 자신과 이 작은 문제의 관계를 통해서 자신에게도 결론이 옳음을 보이는것이다. 따라서 귀납적 사고라는 것은 성격이 같지만 크기가 다른 "관계"를 파악하는 것이라는 점에서 자기호출과 관계가 깊다.

   자기호출을 이용하는 알고리즘에서 자기호출을 제외한 나머지 부분은 대부분 크키가 다른 문제간의 관계를 반영하는 것이다.

점근적 표기

알고리즘의 수행시간은 항상 입력의 크기가 충분히 클 때를 분석하는 점근적 분석을 한다.

n이 작을 때는 차이가 그리 크지 않지만 n이 커짐에 따라 차이는 극적으로 벌어진다.

알고리즘을 분석하려고 입력의 크기로 무엇을 잡을지는 대부분 명확하다. 예를 들어, 여러 수를 크기 순으로 정렬하는 알고리즘이라면 정렬하고자 하는 수의 개수가 입력의 크기가된다.
그래프 알고리즘에서는 대부분 정점의 개수가 간선의 개수 둘을 입력의 크기로 사용한다.

• 가정 :
  앞으로 알고리즘의 소요 시간이나 자원의 소모량을 표현하는 함수는 양의 값을 갖는다고 가정한다. 음의 시간은 의미가 없기 때문이다.

• 표기법은 집합으로 정의되며, $\in$ 대신 = 를 쓴다.

1. $\Theta$ - 표기법

   $\Theta(f(n))$은 최고차항의 차수가 f(n)과 일치하는 모든 함수의 집합이다.
   예를들어, $\Theta(n^2)$은 $n^2, 3n^2-50, 7n^2+16$ 등을 포함한다.

2. $\Omicron$ - 표기법

   $\Omicron(f(n))$은 점근적 증가율이 $f(n)$을 넘지 않는 모든 함수의 집합이다.
   $\Omicron(f(n))$은 최고차항의 차수가 $f(n)$과 일치하거나 더 작은 함수의 집합이다.
   예를들어, $\Omicron(n^2)$은 $n^2, 3n^2-49m 5n+19,n , 2nlogn+3n$ 등을 포함한다.

   $\Omicron$-표기는 함수의 점근적 상한을 나타낸다.

3. $\Omega$ - 표기법

   $\Omega(f(n))$ 은 점근적 증가율이 적어도 $f(n)$이 되는 모든 함수의 집합이다.
   다시말하면 $\Omega(f(n))$은 최고차항의 차수가 $f(n)$과 일치하거나 더 큰 함수의 집합이다.
   예를들어, $\Omega(n^2)$는 $n^2, 3n^2-40, 4n^3+14, 2n^2logn+1$ 등을 포함한다.

   $\Omega$ - 표기법은 함수의 점근적 하한을 나타낸다.

$\Theta(g(n))$은 $\Omicron(g(n))$과 $\Omega(g(n))$의 교집합이다.

복잡도

복잡도는 알고리즘의 성능을 나타내는 척도이다. 동일한 기능을 수행하는 알고리즘이 있다면 복잡도가 낮을수록 좋은 알고리즘이다.

• 시간 복잡도

  : 알고리즘을 위해 필요한 연산의 횟수

• 공간 복잡도

  : 알고리즘을 위해 필요한 메모리의 양

일반적으로 코딩 테스트에서는 최악의 경우에 대한 연산 횟수가 중요하다. 따라서 최악의 경우의 시간 복잡도를 우선적으로 고려해야한다.

시간 복잡도와 공간 복잡도의 Trade-off
메모리를 많이 사용하는 대신에 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있다. 이때 메모리를 더 소모하는 대신에 얻을 수 있는 시간적 이점이 매우 큰 경우가 종종있다.
Cf) Memorization 메모이제이션 : 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법

표기법

시간 복잡도와 공간 복잡도는 점근적 표기법을 사용하여 표현한다.

시간 복잡도 (Time Complexity)

시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래걸리는지를 의미한다.

시간 복잡도는 알고리즘을 위해 필요한 연산의 횟수를 말한다.
시간 복잡도에 따라서 부르는 명칭이 있는데 저일하면 아래의 표와 같다.

빅오 표기법	명칭
O(1)	상수 시간(Constant time)
O(logN)	로그 시간(Log time)
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

시간순으로 따지면
O( 1) < O( log N) < O(N) < O(NlogN) < O(N²) < O(N³) < O(2N) < O(N!)으로 표현할 수 있다. O내부에 있는 n이 작을수록 성능이 좋은 알고리즘이다.

일반적으로 O(N^3)을 넘어가면 코딩테스트에서 사용하기 어려운 알고리즘이다.CPU기반의 개인 컴퓨터나 채점용 컴퓨터에서는 연산 횟수가 10억을 넘어가면 C언어를 기준으로 1보통 초 이상의 시간이 소요된다. 이때 N의 크기가 5,000이 넘는다면 10초 이상의 시간이 걸릴 수 있다. 특히 파이썬은 더 오랜 시간이 소요되고 코딩테스트에서 시간제한이 1~5초 이므로 연산 횟수가 10억을 넘어가면 오답 판정을 받을 수 있다.

빅오 표기법으로 표시한 시간 복잡도가 같더라도 알고리즘 내부 로직 및 차수가 낮은 항의 영향에 따라 10,000번 100,000번 등 실제 수행되는 연산의 횟수가 다를 수 있다. 예를들어 실제로 N이 작을 때 상수값이 1,000,000인 경우 이 값이 미치는 영향력이 크기 때문이다.

시간 제한이 1초인 문제에 대한 예시

• N의 범위가 500 인 경우 : 시간 복잡도가 O(N³) 인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 2000 인 경우 : 시간 복잡도가 O(N²) 인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 100000 인 경우 : O(NlogN) 인 알고리즘을 설계하면 문제를 풀 수 있다.
• N의 범위가 10000000 인 경우 : O(N) 인 알고리즘을 설계하면 문제를 풀 수 있다.

공간 복잡도 (Space Complextiy)

공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.
일반적으로 코딩 테스트에서 메모리 사용량의 기준은 MB 단위로 제시된다. 코딩 테스트 문제는 대부분 다수의 데이터에 대한 효율적인 처리를 요구하기 때문에 리스트(배열)을 사용해서 풀어야한다. 컴퓨터 시스템에서 차지하는 메모리량은 컴파일러에 따라 조금씩 차이가 있지만 고전적인 프로그래밍 언어에서 정수형 자료형인 int를 기준으로 리스트 크기에 따른 메모리 사용량을 확인해보면 아래와 같다.

• int a[1000] : 4KB
• int a[1000000] : 4MB
• int a[2000][2000] : 16MB

코딩 테스트에서는 보통 메모리 사용량을 128~512MB로 제한한다. 다시 말해 일반적인 경우 데이터의 수가 1,000만 단위가 넘어가지 않도록 알고리즘을 설계해야한다.

파이썬에선 대략 100만 개의 데이터가 들어갈 수 있는 크기의 리스트를 선언하는 경우는 적다.

공간 복잡도는 알고리즘을 위해 필요한 메모리의 양을 말한다.

시간과 메모리 측정

• 수행 시간 측정 소스코드

import time
start_time = time.time() # 측정 시작
# 프로그램 소스 코드
end_time = time.time() # 측정 종료
print("time:", end_time-start_time) # 수행 시간 출력

참고자료

• 나동빈, 이것이 취업을 위한 코딩테스트다, 한빛 미디어
• 문병로,관계 중심의 사고법, 쉽게 배우는 알고리즘, 한빛아카데미