Algorithm/알기 쉬운 알고리즘 2021. 4. 30. 18:44

  • 알기쉬운 알고리즘(양성봉 저, 생능 출판) 책을 바탕으로 작성한 내용이다.

02. 알고리즘을 배우기 위한 준비

2.1 알고리즘이란

  • 유래 : 페르시아 수학자인 알콰리즈미(al-Khwarizmi)(서기 780~850년)

  • 알고리즘은 문제를 해결하는 단계적 절차 또는 방법이다.

    • 이는 컴퓨터로 해결할 수 있어야 하며 입력과 출력이 존재한다.

  • 알고리즘의 일반적인 특성

    • 정확성

      • 주어진 입력에 대해 올바른 해를 준다.

    • 수행성

      • 컴퓨터에서 수행이 가능해야 한다. (애매모호한 표현이 없어야 한다.)

    • 유한성

      • 현실적인 시간 내로 종료되어야 한다.

    • 효율성

      • 시간적, 공간적인 효율성을 최대한 고려해야 한다.

2.2 최초의 알고리즘

  • 기원전 300년경에 만들어진 유클리드(Euclid)의 최대공약수를 찾는 알고리즘이 최초이다.

  • 유클리드의 최대공약수 알고리즘

    a >= b >= 0 일 때,

    pseudo code

    int Euclid(int a, int b)
{
  if (b == 0) return a;
  return Euclid(b, a mod b);
}

2.3 알고리즘의 표현 방법

  • 알고리즘의 각 단계는 보통 말로 서술할 수 있지만, 일반적으로 의사 코드(pseudo code)로 표현된다.

  • 1장의 "1.1 최대 숫자 찾기"의 의사 코드는 다음과 같다.

    pseudo code

    max = Array[0]
for i = 1 to 9
  if (Array[i] > max) max = Array[i]
return max

  • 이외에도 플로우차트(flow chart) 형태로 표현하기도 한다.

2.4 알고리즘의 분류

  • 알고리즘은 문제의 해결 방식에 따라 대략 다음과 같이 분류된다.

    • 분할 정복(Divide-and-Conquer) - 3장

    • 그리디(Greedy) - 4장

    • 동적 계획(Dynamikc Programming) - 5장

    • 근사(Approximation) - 8장

    • 백트래킹(Backtracking) - 9장

    • 분기 한정(Branch-and-Bound) - 9장

    • 랜덤(Random)

    • 병렬(Parallel)

    • 분산(Distributed)

    • 양자(Quantum)

    • 유전자(Genetic)

  • 문제에 기반하여 분류한 알고리즘들

    • 정렬 - 6장

    • 그래프(Graph)

    • 기하(Geometry)

2.5 알고리즘의 효율성 표현

  • 일반적으로 시간 복잡도가 알고리즘의 비교 척도로 사용된다.

  • 시간 복잡도(Time Complexity)

    • 알고리즘의 수행 시간

      • 실제로 수행되는 시간이 아닌, 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현하는 것이다.

    • 알고리즘의 복잡도를 분석하는 방법은 다음과 같다.

      • 최악 경우 분석(Worst Case Analysis)

        • 어떤 입력이 주어지더라도 넘지 않는 시간을 분석한다.

      • 평균 경우 분석(Average Case Analysis)

        • 입력이 균등 분포(Uniform Distribution)일 경우를 가정하고 분석한다.

      • 최선 경우 분석(Best Case Analysis)

        • 최적(Optimal) 알고리즘을 고안할 때 참고 자료로 활용된다.

  • 공간 복잡도(Space Complexity)

    • 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기

2.6 복잡도의 점근적 표기

점근적 표기(Asymptotic Notation)

  • 복잡한 식을 간단히 표현하기 위해 사용되는 표기법

  • 일반적으로 빅오 표기법이 사용된다.

  • O(Big-Oh) 표기

    • 복잡도의 점근적 상한을 나타낸다.

      • 점근적 상한

        • 단순화된 함수에 임의의 양수를 곱하여 나온 함수가, n이 증가함에 따라 f(n)의 상한이 되는 경우

    • 다항식의 최고 차항만 계수 없이 취하면 된다.

  • Ω(Big-Omega) 표기

    • 복잡도의 점근적 하한을 나타낸다.

      • 점근적 하한

        • 단순화된 함수에 임의의 양수를 곱하여 나온 함수가, n이 증가함에 따라 f(n)의 하한이 되는 경우

    • 다항식의 최고 차항만 계수 없이 취하면 된다.

  • θ(Theta) 표기

    • 복잡도의 상한과 하한이 동시에 적용되는 경우를 나타낸다.

      • n이 증가함에 따라 복잡도와 동일한 증가율을 가진다는 것을 의미한다.

    • 즉 빅오 표기법과 빅오메가 표기법의 복잡도가 같은 경우 사용한다.

예제

  • 복잡도가 f(n) = 2n2-8n+3 일 때

    • O(n2)

      • 임의의 양수 c를 곱한 cn2은 n이 증가함에 따라 f(n)의 상한이 된다. (예를 들면 c = 5인 경우)

    • Ω(n2)

      • 임의의 양수 c를 곱한 cn2은 n이 증가함에 따라 f(n)의 하한이 된다. (예를 들면 c = 1인 경우)

    • θ(n2)

      • f(n)은 n이 증가함에 따라 n2과 동일한 증가율을 가진다.

자주 사용되는 O 표기

O 표기 의미
O(1) 상수 시간(Constant Time)
O(logn) 로그(대수) 시간(Logarithmic Time)
O(n) 선형 시간(Linear Time)
O(nlogn) 로그 선형 시간(Log-linear TIme)
O(n2) 제곱 시간(Quadratic Time)
O(n3) 세제곱 시간(Cubic Time)
O(nk) 다항식 시간(Polynomial Time)
O(2n) 지수 시간(Exponential Time)

2.7 왜 효율적인 알고리즘이 필요한가?

  • 입력 크기가 커질 수록 수행 시간의 차이가 엄청나며, 하드웨어 기술 개발보다는 효율적인 알고리즘 개발이 훨씬 경제적이다.
저작자표시

'Algorithm > 알기 쉬운 알고리즘' 카테고리의 다른 글

최단 경로 찾기(Shortest Path)  (0) 2021.05.03
최소 신장 트리(Minimum Spanning Tree)  (0) 2021.05.03
03. 분할 정복 알고리즘  (0) 2021.04.30
선택 문제 (Selection Problem)  (0) 2021.04.30
01. 알고리즘의 첫걸음  (0) 2021.04.30

티스토리툴바