[알고리즘] 1장. Algorithm : efficiency, analysis, order

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 1-1

* 알고리즘 기원

- 페르시아의 수학자, 천문학자, 지리학자 알코와리즘

* 알고리즘

- 문제를 해결할 수 있는 잘 정의된(well defined) 유한(finite) 시간 내에 종료되는 계산적인(computational) 절차(procedure)

- 확률적(probabilistic) 알고리즘은 무작위성을 포함한다.

* 알고리즘 사용 예시

- 자율주행, 인공지능, 로봇, 메타버스, 암호화폐, NFT

* 알고리즘 학습 목표

- Design(설계), Analysis(분석), Computational Complexity(계산복잡도), Application Capability(응용력)

* 문제 분야

- 정렬, 탐색, 계산기하, 암호화

* 문제 해결 방법 유형

- n분할정복, 탐욕적인방법, 동적계획법, 분기한정법

* Algorithm vs Method

- 유한시간 내에 종료 vs 유한시간 내에 종료하는 지 모름

---

📌 1-2

* 문제의 표기 방법
- 문제 : 답을 찾고자 던지는 질문
- 파라미터(parameter) : 문제에서 특정값이 주어지지 않은 변수
- 문제의 사례(instance) (입력) : 파라미터에 특정 값을 지정한 것
- 사례에 대한 해답(solution) (출력) : 주어진 사례에 관한 질문에 대한 답

* 알고리즘 표기 방법
- 자연어 : 한글 또는 영어 / 문제를 정확하게 기술하는데 어려움 있음.
- 프로그래밍 언어 : C, C++, Java, ML 등 / 너무나 구체적인 기술을 해야 하므로, 알고리즘을 이해하는데 어려움.
- 의사코드(pseudo-code) : "실제와 비슷한" / 간결하면서도 정확한 의미 표현 가능
- 순서도(흐름도,플로차트)

* C++와 의사코드의 차이점
- 배열 인덱스의 범위에 제한이 없다.
- 프로시저의 파라미터에 2차원 배열 크기의 가변성을 허용한다.
- 지역배열에 변수인덱스를 허용한다.
- 수학적 표현식을 허용한다.
- C++에 없는 타입 사용 가능하다.
- 제어 구조
- 프로시저 (void 함수) 함수 (returntype 함수)
- 참조 파라미터를 사용하여 프로시저의 결과값을 전달한다.

* <A1.1> 순차검색 알고리즘(sequential search)

- 문제 : 크기가 n인 배열 S에 x가 있는가?
- 입력 : 양의 정수 n, 1에서 n까지의 첨자를 가진 키의 배열 S, x
- 출력 : x가 S의 어디에 있는지 위치, 만약 없으면 0.

location = 1;
while (location <= n && S[location] != x)
	location++;
if (location > n)
	location = 0;

* <A1.2> 배열의 수 더하기

- 문제 : n개의 수로 된 배열 S에 있는 모든 수를 더하라.
- 입력 : 양의 정수 n, 키의 배열 S(첨자는 1부터 n)
- 출력 : S에 있는 수의 합, sum

number sum (int n, const number S[]) {
	index i;
	number result;
	result = 0;
	for (i = 1; i <= n; i++)
		result = result + S[i];
	return result;
}

* <A1.3> 교환정렬

- 문제 : 비내림차순으로 n개의 키를 정렬하라.
- 입력 : 양의 정수 n, 키의 배열 S(첨자는 1부터 n)
- 출력 : 키가 비내림차순으로 정렬된 배열 S

void exchangesort(int n, keytype S[]) {
	index i, j;
	for (i = 1; i <= n - 1; i++)
		for (j = i + 1; j <= n; j++)
			if (S[j] < S[i])
				exchange S[i] and S[j]
}

* <A1.4> 행렬곱셈

* <A1.4> 행렬곱셈
- 문제 : 두 개의 n x n 행렬의 곱을 구하라.
- 입력 : 양의 정수 n, 수의 2차원 배열 A와 B. 여기서 이 행렬의 행과 열은 모두 1부터 n가지의 첨자를 갖는다.
- 출력 : A와 B의 곱이 되는 수의 2차원 배열 C. 이 행렬의 행과 열은 모두 1부터 n까지의 첨자를 갖는다.

for (i = 1; i < n; i++) {
	for (j = 1; j < n; j++) {
		C[i][j] = 0;
		for (k = 1; k <= n; k++)
			C[i][j] = C[i][k] + A[i][k] * B[k][j];
	}
}

* <A1.5> 이분검색 알고리즘 (binary search) / 분할정복법 (Divide and Conquer)

* <A1.5> 이분검색 알고리즘 (binary search) / 분할정복법 (Divide and Conquer)
- 문제 : 크기가 n인 정렬된 배열 S에 x가 있는가?
- 입력 : 양수 n, 배열 S[1..n], 키 x
- 출력 : x가 S의 어디에 있는지의 위치. 만약 없으면, 0.

index location (index low, index high) {
	index mid;
	if (low > high)
		return 0;
	else {
		mid = (low + high) / 2;
		if (x == S[mid])
			return mid;
		else if (x < S[mid])
			return location(low, mid - 1);
		else
			return location(mid + 1, high);
	}
}
locationout = location(1, n);

---

📌 1-3

* 황금 분할
r = (1 + root5) / 2 = 1.61803...

* <A1.6> 피보나치 수 구하기 (재귀적 방법-분할정복방법)

- 피보나치 수 구하기 재귀 알고리즘은 수행속도가 매우 느리다.
- 이유 : 같은 피보나치 수를 중복 계산

- T(n) > 2^n/2

- 문제 : n번째 피보나치 수를 구하라.
- 입력 : 양수 n
- 출력 : n번째 피보나치 수

int fib (int n) {
	if (n <= 1)
		return n;
	else
		return fib(n-1) + fib(n-2);
}

* 수학적 귀납법
- 1. 귀납출발점(basis, base case) : n = 0(또는 1)일 때 주장이 사실임을 보임.
- 2. 귀납가정(induction(inductive) hypothesis) : 어떤 n에 대해서 주장이 사실임을 가정.
- 3. 귀납절차(inductive step) : n+1에 대해서 주장이 사실임을 보임.
- 4. 123에 의해 ~이 성립.

* <A1.7> 피보나치 수 구하기 (반복적 방법-동적계획법)

- 반복 알고리즘은 수행속도가 훨씬 더 빠르다.
- 이유 : 중복 계산이 없음

- T(n) = n + 1

int fib2 (int n) {
	index i;
	int f[0..n];
	f[0] = 0;
	if (n > 0) {
		f[1] = 1;
		for (i = 2; i <= n; i++)
			f[i] = f[i-1] + f[i-2];
	}
	return f[n];
}

* 알고리즘을 실질적인 문제에 사용할 때는 반드시 그 알고리즘이 갖고있는 시간복잡도를 먼저 확인해야 한다.

---

📌 1-4

* 공간복잡도(space(memory) complexity)

- 입력크기에 따라서 작업공간(메모리)이 얼마나 필요한 지 결정하는 절차

* 시간복잡도(time complexity)

- 입력 크기에 따라서 단위연산이 몇 번 수행되는지 결정하는 절차, 알고리즘이 수행되는 기계에 따라 문제를 해결하는 시간이 달라짐.

* 우리의 관심도

- 시간복잡도 > 공간복잡도

* 표현 척도
- 단위연산(basic operation) : 비교문(comparison), 지정문(assignment) 등
- 입력 크기(input size) : 배열의 크기, 리스트의 길이, 행렬에서 행과 열의 크기, 트리에서 마디와 이음선의 수

* 분석 방법의 종류
- 모든 경우 분석(Every-case analysis) : 입력크기에만 종속. 입력값과는 무관하다. 입력값과는 무관하게 결과값이 항상 일정하다.
- 최악의 경우 분석(Worst-case analysis) : 입력크기와 입력값 모두에 종속. 단위연산이 수행되는 횟수가 최대인 경우 선택.
- 평균의 경우 분석(Average-case analysis) : 입력크기에 종속. 모든 입력에 대해서 단위연산이 수행되는 기대치(평균). 각 입력에 대해서 확률 할당 가능. 일반적으로 최악의 경우보다 계산이 복잡하다.
- 최선의 경우 분석(Best-case analysis) : 입력크기와 입력값 모두에 종속. 단위연산이 수행되는 횟수가 최소인 경우 선택.

* 우리의 주요 관심은 Worst-case analysis

- 비관적 시각으로 알고리즘을 고안한다.

- 평균시간 개념의 비현실성이 존재한다.
- 평균적인 경우 시간복잡도 분석은 어렵다.

* 복잡도 함수(complexity function)

- 음이 아닌 정수가 주어지면 음이 아닌 실수를 내주는 함수. f(n) = n, lgn, 3n^2+4n, etc.

* 정확도(correctness) 분석
- 알고리즘이 의도한 대로 수행되는지를 증명하는 절차
- 정확도를 증명하는 것은 쉽지 않다.
- 정확한 알고리즘이란? 어떠한 입력에 대해서도 답을 출력하면서 멈추는 알고리즘.
- 정확하지 않은 알고리즘이란? 어떤 입력에 대해서 멈추지 않거나, 또는 틀린 답을 출력하면서 멈추는 알고리즘.

---

📌 1-5

* 대표적인 복잡도 함수
- Θ(lg n)
- Θ(n) : 1차(linear)
- Θ(n lg n)
- Θ(n^2) : 2차(quadratic)
- Θ(n^3) : 3차(cubic)
- Θ(2^n) : 지수(exponential)
- Θ(n!)
- Θ(n^n)

* 2차 항이 궁극적(Eventually)으로 지배한다.
- n, 0.1n^2, 0.1n^2 + n + 100

* 높은 차수항이 궁극적으로 지배한다.
- n, 0.01n^2, 100n
- 10,000보다 큰 n에 대해서 0.01n^2 > 100n.

* Asymptotic(점근적) Behavior
- f(n)의 asymptotic behavior는 n이 큰 수가 될 때의 함수 f(n)이 갖는 특성
- ex) f(n) = 1/n => 0

* 복잡도 함수 표기법(notation)
- O() - big oh : asymptotic upper bound, 점근적 상한, 하나의 경우라도.
- o() - small oh : upper bound that is not asymptotically tight, 모든 ~에 대해서.
- Ω() - big omega : asymptotic lower bound, 점근적 하한, 하나의 경우라도.
- ω() - small omega : lower bound that is not asymptotically tight, 모든 ~에 대해서.
- Θ() - theta : asymptotic tight bound, 점근적 상한과 하한 모두 포함된다.

 

* 복잡도 함수 순서
- Θ(lg n), Θ(n), Θ(n lg n), Θ(n^2), Θ(n^j), Θ(n^k), Θ(a^n), Θ(b^n), Θ(n!)

---