[이산수학] 알고리즘

📌 들어가며

이번 글에서는 IT의 꽃 알고리즘을, IT 관점이 아닌 수학적 관점에서 다룬다.

알고리즘: 주어진 문제를 해결하기 위한 방법을 순차적으로 나열한 것.

---

1. 알고리즘의 5가지 특징

특징	설명
입력(input)	입력값을 가진다
출력(output)	출력값을 가진다
유한성(finiteness)	유한 시간 내에 종료
정확성(precision)	각 단계가 명확히 서술
일반성(generality)	여러 입력에 적용 가능

---

2. 표현 방법

방법	설명
순서도(flow chart)	도표로 순차 흐름 표현
의사 코드(pseudo code)	실제 언어를 닮은 코드
실제 언어	프로그래밍 언어 등

---

3. 분석 기준

기준	의미
정확도	값이 얼마나 정확한가
코드 복잡도	코드가 얼마나 복잡한가
공간 복잡도	하드웨어(RAM 등)를 얼마나 쓰는가
시간 복잡도	실행 시간이 얼마나 긴가

💡 정확도와 시간 복잡도가 가장 중요하다. 다만 정확도는 참값이 필요한 문제도, 근삿값으로 충분한 문제도 있어 상황에 따라 다르므로, 여기서는 시간 복잡도 위주로 다룬다.

---

4. 시간 복잡도 — Big-O 표기법

정의: 두 양의 정수 c와 n₀가 존재하여, n ≥ n₀인 모든 n에서 |f(n)| ≤ c|g(n)|를 만족하면 f(n) = O(g(n))이라 쓰고 “Big-O of g(n)”이라 읽는다.

일반적으로 g(n)에 들어가는 함수는 다음과 같다.

빠름 ◄────────────────────────────────► 느림
1 < log n < n < n log n < n² < n³ < ... < n!

💡 정보처리기사 책의 빅오 설명과 달리 어려워 보이지만, 수학은 모든 것을 확실하게 정의하기 때문에 이렇게 정확히 서술한 것이다. 여기서 말하는 것은 n이 충분히 클 때의 이야기다.

---

5. 재귀적 알고리즘

재귀적 함수: 함수가 자기 자신을 스스로 호출하는 함수. 이를 포함한 알고리즘이 재귀적 알고리즘이다.

예 — 팩토리얼:

f(n) = n · f(n-1)
     = n(n-1)(n-2)…2 · f(1)
     = n! · f(1)

재귀 문제 해결에는 두 가지가 필요하다.

요소	역할
초기 조건(initial condition)	종료값 (예: f(1))
재귀 조건(recursion condition)	자기 호출 규칙

💡 재귀법은 반복법보다 구성이 간단하지만 실행시간·메모리를 더 사용한다. 대부분 재귀법과 반복법은 서로 동등하게 대체 가능하다.

---

📝 정리

알고리즘 (수학적 관점)
├─ 특징     입력·출력·유한·정확·일반
├─ 표현     순서도 / 의사코드 / 실제언어
├─ 분석     정확도·시간·공간·코드 복잡도
├─ Big-O   n 충분히 클 때 상한 (1<logn<n<...<n!)
└─ 재귀     자기 호출 (초기조건 + 재귀조건)

개념	한 줄 정의
알고리즘	문제 해결 절차의 나열
Big-O	시간 복잡도의 상한 표기
재귀	자기 자신을 호출하는 함수

알고리즘을 수학적으로 정의하면 입력·출력·유한성 같은 조건이 명확해진다. 특히 Big-O는 “n이 충분히 클 때의 상한”이라는 수학적 관점으로 이해하면, 정보처리기사식 암기보다 훨씬 깊이 있게 다가온다.