[알고리즘/개념정리] 2. 알고리즘이란?

2-1 알고리즘이란

알고리즘이란?

알고리즘의 일반적 특성

• 정확성
  • 알고리즘은 입력값에 대해 항상 올바른 로직을 거쳐 올바른 해를 주어야 한다.
• 수행성
  • 컴퓨터 내에서 모든 단계가 수행 가능해야 한다.
  • 코드로 바꿀 수 없다면 컴퓨터에서 수행 가능한 알고리즘이 아니다.
• 유한성
  • 너무 오래 걸린다면 알고리즘으로써의 가치가 없다.
  • 일정 시간 내에 종료되어야 한다.
• 효율성
  • 커지면 커질수록 더 오래 걸린다면 효율적이라고 볼 수 없다.
  • 입력값이 크면 클수록 점점 적은 시간이 걸리는 것이 효율적이다.
  • 시간복잡도

---

2-2 최초의 알고리즘

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

• 곱셈을 통해 푸는 방법

12 → 12 x 1 , 6 x 2, 4 x 3

30 → 30 x 1, 15 x 2, 10 x 3, 6 x 5

공약수 중 가장 큰 것이 최대공약수이다.

• 소인수분해로 푸는 방법 (숫자가 커질 수록 유리)

12 = 2^2 x 3
30 = 2 x 3 x 5

 

• 나눗셈을 이용한 방법

 

• 유클리드 호제법
  • 큰 수에서 작은 수를 뺀수 = 작은 수와의 최대공약수

 

(30, 12)의 최대공약수 = 6
30-12 = 18
(18, 12)의 최대공약수 = 6

Euclid(a, b)
입력: 정수 a, b; 단, a≥b≥0
출력: 최대공약수(a, b)
1. If (b=0) return a
2. return Euclid(b, a mod b)

a, b = map(int, input().split())

while(a!=b):
  if(a>b) : a-=b
  else    : b-=a

print(a)

 

 

---

 

2-3 알고리즘의 표현 방법

• 알고리즘의 형태는 단계별 절차이므로, 마치 요리책의 요리를 만드는 절차와 유사
• 알고리즘의 각 단계는 보통 말로 서술할 수 있으며, 컴퓨터 프로그래밍 언어로만 표현할 필요는 없음 → 하지만 우리는 프로그래밍 언어로 표현하도록 한다.
• 일반적으로 알고리즘은 프로그래밍 언어와 유사한 의사 코드 (pseudo code)로 표현

최대 숫자 찾기 문제를 위한 알고리즘

• 카드의 숫자를 하나씩 비교하면서 본 숫자들 중에서 가장 큰 숫자를 기억해가며 진행하는 방법
• 마지막 카드의 숫자를 본 후에, 머릿속에 기억된 가장 큰 숫자가 적힌 카드를 바닥에서 집어 든다
• 배열 A에 10개의 숫자가 있다고 가정
  1. max = A[0]
  2. for i = 1 to 9
  3. if (A[i] > max) max = A[i]
  4. return max

---

2-4 알고리즘의 분류

• 문제 해결 방식에 따른 분류
  • 분할 정복 (Divide-and-Conquer) 알고리즘
  • 그리디 (Greedy) 알고리즘
  • 동적 계획 (Dynamic Programming) 알고리즘
  • 근사 (Approximation) 알고리즘
  • 백트래킹 (Backtracking) 기법
  • 분기 한정 (Branch-and-Bound) 기법
• 문제에 기반한 분류
  • 정렬 알고리즘
  • 그래프 알고리즘
  • 기하 알고리즘
• 특정 환경에 따른 분류
  • 병렬 (Parallel) 알고리즘
  • 분산 (Distributed) 알고리즘
  • 양자 (Quantum) 알고리즘

문제에 따라 효율적인 알고리즘은 모두 다르다. → 효율성이란?

 

---

2-5 알고리즘의 효율성

• 알고리즘의 수행 시간 또는 알고리즘이 수행하는 동안 사용되는 메모리 공간의 크기로 나타낼 수 있다.
• 이들을 각각 시간복잡도 (time complexity), 공간복잡도 (space complexity)라고 한다.
• 일반적으로 알고리즘들을 비교할 때에는 시간복잡도가 주로 사용됨

 

시간복잡도

알고리즘의 복잡도 표현 방법

 💡 등교 시간 분석 집에서 지하철 역까지 6분, 지하철을 타면 학교까지 20분, 강의실까지 걸어서 10분 걸린다.

 

• 최악경우 분석 (Worst-case Analysis) → 가장 많이 사용
  • ‘어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다‘라는 상 (Upper Bound)의 의미

  최악경우
  – 열차에 승차하려는 순간, 열차의 문이 닫혀서 다음
  열차를 기다려야 하고 다음 열차가 4분 후에
  도착한다면, 최악경우는 6 + 4 + 20 + 10 = 40분
  

• 평균경우 분석 (Average-case Analysis)
  • 입력의 확률 분포를 가정하여 분석하는데, 일반적으로 균등분포(Uniform Distribution)를 가정

  평균시간
  – 대략 최악과 최선의 중간이라고 가정했을 때, 38분
  

• 최선경우 분석 (Best-case Analysis) → 거의 사용하지 않는다.
  • 가장 빠른 수행시간을 분석하며, 최적(Optimal) 알고리즘을 찾는데 활용

  최선경우
  – 집을 나와서 6분 후 지하철역에 도착하고, 운이 좋게
  바로 열차를 탄 경우를 의미
  – 최선경우 시간은 6 + 20 + 10 = 36분
  

• 상각 분석 (Amortized Analysis)
  • 일련의 연산을 수행하여 총 연산 횟수를 합하고 이를 연산 횟수로 나누어 수행시간을 분석
  • amortize는 ‘분할 상환하다’라는 뜻을 가짐. 그리고 상각(償却)은 ‘보상하여 갚아주다’라는 뜻

  상각분석
  – 단순히 한 번의 등교시간을 분석하는 것이 아니라, 
  예를 들어, 한 학기 동안의 등교시간을 분석해본다는
  점에서 그 의미를 가짐
  – 한 학기 동안 100번 학교에 간다고 하면, 최악경우는
  100 x 40 = 4,000분
  – 한 학기 동안에 항상 지하철만 타고 또 최악경우인
  40분씩 걸린다고 가정하여 계산된 4,000분은 실제
  등교 시간보다 지나치게 긴 시간
  – 실제로 어떤 날은 택시를 타고도 학교에 갈 수 있으며, 
  지하철이나 버스를 타고 학교에 갈 수도 있기 때문
  – 상각분석은 한 학기 동안 학교에 가는데 소요된 시간을
  모두 합해서 학교에 간 횟수인 100으로 나눈 값을 1회
  등교 시간으로 분석
  

---

2-6 복잡도의 점근선 표기

O(Big-Oh)-표기

- 점근적 상한

- g(n)이 n0보다 큰 모든 n에 대해서 항상 f(n)보다 크다

 

Ω(Big-Omega)-표기

- 점근적 하한

- n0 보다 큰 모든 n 대해서 f(n)이 cg(n)보다 작지 않다

 

 

 

Θ(Theta)-표기

- 동일한 증가율

- 수행시간의 O-표기와 Ω-표기가 동일한 경우에 사용한다. 즉 동일한 증가율을 의미