2.1 알고리즘이란 ?

• 알고리즘
  • 문제를 해결하는 단계적 절차 또는 방법
  • 여기서 주어지는 문제는 컴퓨터를 이용하여 해결
  • 알고리즘에는 입력이 주어지고, 알고리즘은 수행한 결과인 “해”
• 알고리즘의 일반적 특성
  • 정확성 : 주어진 입력에 대하여 올바른 해를 주어야 ( 랜덤 알고리즘 제외 )
  • 수행성 : 컴퓨터에서 수행 가능
  • 유한성 : 유한 시간 내에 종료 되어야
  • 효율성 : 효율적일 수록 가치가 높다

---

2.2 최초의 알고리즘

• 유클리드 ( Eucild ) 의 최대 공약수 알고리즘
• 2개의 자연수의 공약수들 중에서 가장 큰 수
  • 2개의 자연수의 최대 공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다.
  • 뺄셈 대신에 나눗셈을 사용하면 빠르게 해를 찾음
• 의사 코드 ( Pseudo Code )

Euclid(a,b)
입력: 정수 a , b; 단 ,  a >= b >= 0

1. if b == 0 return a 
2. return Eucild(b,a mod b); // 재귀 호출

코드 구현

#include <stdio.h>

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

int main() {
	int a, b;

	scanf_s("%d %d", &a, &b);
	printf("%d\n", Euclid(a, b));
	return 0;
}

---

2.3 알고리즘의 표현 방법

• 알고리즘의 형태는 단계별 절차이므로 , 마치 요리책의 요리를 만드는 절차와 유사
• 알고리즘의 각 단계는 보통 말로 서술할 수 있으며, 컴퓨터 프로그래밍 언어로만 표현할 필요 없음
• 일반적으로 알고리즘은 프로그래밍 언어와 유사한 의사 코드 ( Pseudo Code ) 로 표현
• Ex) 최대 숫자 찾기 문제를 위한 알고리즘
• 의사 코드 ( 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 Programing ) 알고리즘
  • 근사 ( Approximaiton ) 알고리즘
  • 백트래킹 ( Backtracking ) 알고리즘
  • 분기 한정 ( Branch-and-Bound) 알고리즘
• 문제에 기반한 분류
  • 정렬 알고리즘
  • 탐색 알고리즘
  • 그래프 알고리즘
  • 기하 알고리즘
• 특정 환경에 따른 분류
  • 병렬 ( Parallel ) 알고리즘
  • 분산 ( Distributed ) 알고리즘
  • 양자 ( Quantum ) 알고리즘
• 패러다임에 의한 분류
  • 기존 규칙 기반 알고리즘 → 우리가 알고리즘 수업에서 다루는 것들
  • 학습 기반 알고리즘 → Transformer, Deep ML, shallow ML …. etc

---

2.5 알고리즘의 효울성 표현

• 알고리즘의 효율성
  • 알고리즘의 수행 시간 또는 알고리즘이 수행하는 동안 사용되는 메모리 크기로 나타낼 수 있다.
  • 시간 복잡도 , 공간 복잡도
  • 일반적으로 알고리즘들을 비교할 때에는 시간 복잡도가 주로 사용
• 시간 복잡도
  • 알고리즘이 실행되는 동안에 사용된 기본적인 연산 횟수를 입력 크기의 함수로 나타낸다.
  • 기본연산 :단순한 연산
• 알고리즘의 복잡도 표현 방법
  • 최악의 경우 분석 ( Worst-case Analysis )
    • 어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다 라는 상한 ( Upper Bound ) 의 의미
  • 평균 경우 분석 ( Average-case Analysis )
    • 일반적으로 균등 분포 ( Uniform Distributed ) 를 가정
  • 최선 경우 분석 ( Best-case Analysis )
    • 가장 빠른 수행 시간을 분석 → 최적 ( Optimal ) 알고리즘을 찾는데 활용
• 상각 분석 ( Amortized Analysis )
  • 일련의 연산을 수행 → 총 수행 시간 합 → 이를 연산 횟수로 나누어 수행 시간을 분석
  • [조건] 알고리즘에서 적어도 두 종류의 연산이 수행되고, 그 중 하나는 수행 시간이 길고, 다른 하나는 짧으며 , 수행 시간이 짧은 연산은 많이 수행되고 수행 시간이 긴 연산은 적게 수행되어야 상각 분석이 의미를 갖는다.
  • “상각”은 ‘보상하여 갚아주다’라는 뜻
• 일반적으로 알고리즘의 수행 시간은 최악 경우 분석으로 표현

---

2.6 복잡도의 점근적 표기

• 시간 복잡도는 입력 크기에 대한 함수로 표기
  • 함수는 여러 개의 항을 가지는 다항식
  • 이를 입력의 크기에 대한 함수로 표현하기 위해 점근적 표기 ( Asymptotic Notation ) 를 사용
• 점근적 표기
  • 입력 크기 N이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용
  • O ( Bic-Oh) 표기
  • Ω ( Big-Omega ) 표기 ← 하한 ( Lower Bound )
  • Θ ( Theta) 표기 ← 유사한 증가율을 가지고 있다
• O ( Bic-Oh) 표기
  • f(n) ≤ cg(n)
  • g(n)을 f(n)의 상한 ( Upper Bound ) 이라고 한다.
  • 점근적 상한
  • 다항식에서 최고 차수의 항만을 취한 뒤, 그 항의 계수를 제거하여 표현

---

요약

• 알고리즘이란 문제를 해결하는 단계적 절차 또는 방법이다.
• 알고리즘의 일반적인 특성
  • 정확성: 주어진 입력에 대해 올바른 해를 주어야
  • 수행성: 각 단계는 컴퓨터에서 수행 가능하여야.
  • 유한성: 유한 시간 내에 종료되어야
  • 효율성: 효율적일수록 그 가치가 높다.
• 알고리즘은 대부분 의사 코드(pseudo code) 형태로 표현된다.
• 알고리즘의 효율성은 주로 시간 복잡도 (Time Complexity)가 사용된다.
• 시간 복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현
• 알고리즘의 복잡도 표현 방법:
  • 최악 경우 분석(Worst case Analysis)
  • 평균 경우 분석(Average case Analysis)
  • 최선 경우 분석(Best case Analysis)
• 점근적 표기(Asymptotic Notation): 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법
  • O-(Big-Oh) 표기: 점근적 상한
  • Ω-(Big-Omega) 표기: 점근적 하한
  • Θ-(Theta) 표기: 동일한 증가율

---