S4) Unit 11. [자료구조/알고리즘] 알고리즘 & 시간 복잡도 & 공간 복잡도

📣  알고리즘

𝟭. 알고리즘의 개념

✔️ 어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제 풀이 방법

➰ 프로그래밍에서는 input 값을 통해 output 값을 얻기 위한 계산 과정을 의미

    ㄴ 입력(input) : 출력에 필요한 자료

    ㄴ 출력(output) : 알고리즘이 끝이 났다는 의미로 실행이 끝나면 적어도 한가지 결과를 출력해야 한다.

    ㄴ 유한성(Finiteness) : 유한한 명령어를 수행한 후, 유한한 시간 내에 종료해야 한다.

    ㄴ 명확성(Definiteness) : 알고리즘의 각 단계는 단순하고 명확해야 하며, 모호해서는 안된다.

    ㄴ 효율성(Efficiency) : 알고리즘은 가능한 한 효율적이어야 한다.

 

𝟮. 알고리즘의 중요성

✔️ 절차가 명확하게 표현되어 있고, 효율적이므로 다양한 문제 해결 과정에서 나타나는 불필요한 작업들을 줄여준다.

➰ 정확하지 않은 답은 혼란을 주고, 프로그래밍 자체에 큰 문제를 야기하므로 정확하게 짜는 것이 중요하다.

 

𝟯. 알고리즘을 잘 푸는 방법

1️⃣ 문제를 이해한다.

➰ 주어진 조건을 토대로 문제가 무엇인지를 이해하는 것부터 시작한다.

 

2️⃣ 문제를 해결할 전략을 세운다.

➰ 수도코드부터 작성해 본다.

 

3️⃣ 전략을 코드로 옮겨본다.

➰ 전략을 코드로 옮기고, 최적화를 시도해본다.

---

📣  시간 복잡도

𝟭. 시간 복잡도

✔️ 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?

➰ 빅-오 표기법을 사용해서 나타낸다.

 

𝟮. Big-O 표기법

✔️ 최악의 경우를 고려하는 방법으로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다.

1️⃣ O(1)

➰ constant complexity로, 입력값이 증가하더라도 시간이 늘어나지 않는다.

➰ 입력 값의 크기와 상관없이 즉시 출력값을 얻어낼 수 있다.

function O_1_algorithm(arr, index) {
	return arr[index];
}

let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = O_1_algorithm(arr, index);
console.log(result); // 2

 

2️⃣ O(n)

➰ linear complexity로, 입력값이 증가함에 따라 시간도 같은 비율로 증가하는 것을 의미한다.

function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

➰ 입력값이 1 증가할 때 마다 실행 시간도 1초씩 증가한다 => 같은 비율로 증가

➰ 2n, 5n도 모두 O(n)으로 표기한다.

 

3️⃣ O(log n)

➰ logarithmic complexity로, O(1) 다음으로 빠른 시간 복잡도를 가진다.

➰ BST 처럼 입력값이 절반으로 계속 줄어드는 알고리즘이 해당한다.

 

4️⃣ O(n^2)

➰ quadratic complexity로, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

function O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
		// do something for 1 second
		}
	}
}

function another_O_quadratic_algorithm(n) {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			for (let k = 0; k < n; k++) {
			// do something for 1 second
			}
		}
	}
}

➰ O(n^3), O(n^5)도 모두 O(n^2)로 표기한다.

 

5️⃣ O(2^n)

➰ exponential complexity로, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

➰ 매번 2배로 늘어나는 알고리즘이 해당하며 재귀로 구현하는 피보나치 수열이 대표적이다.

function fibonacci(n) {
	if (n <= 1) {
		return 1;
	}
	return fibonacci(n - 1) + fibonacci(n - 2);
}

 

𝟯. 데이터 크기에 따른 시간 복잡도

➰ n ≤ 500 으로 입력이 제한된 경우에는 O(n³)의 시간 복잡도를 가질 수 있다고 예측할 수 있고, 굳이 O(log n)으로 줄일 필요는 없지만, n ≤ 1000000인 경우에는 O(n) 또는 O(log n)의 시간 복잡도를 가질 수 있도록 문제를 풀어야 한다.

데이터 크기 제한	예상 시간 복잡도
n ≤ 1,000,000	O(n) or O (logn)
n ≤ 10,000	O(n2)
n ≤ 500	O(n3)

---

📣  공간 복잡도

𝟭. 공간 복잡도

✔️ 알고리즘이 수행되는 데에 필요한 메모리의 총량을 의미한다.

➰ 프로그램이 필요로 하는 메모리 공간을 산출하는 것

➰ 빅 오 (Big-O) 표기법으로 표현한다.

 

𝟮. 공간 복잡도 예시

function factorial(n) {
	if(n === 1) {
		return n;
	}
	return n*factorial(n-1);
}

➰ n에 따라 변수 n이 n개 만들어지게 되며, factorial 함수를 재귀함수로 1까지 호출할 경우 n부터 1까지 스택에 쌓이게 된다.

➰ 위 함수의 공간 복잡도는 O(n) 이다.

 

𝟯. 공간 복잡도의 중요성

➰ 시간복잡도 보다는 중요성이 떨어지지만, 동적 게획법 처럼 알고리즘이나 하드웨어 환경이 매우 한정된 경우 공간 복잡도가 중요해진다.

➰ 동적 계획법은 알고리즘 자체가 구현 시 메모리를 많이 요구하기 때문에 입력값의 범위가 넓어지면 사용하지 못하는 경우도 많고, 하드웨어 환경이 매우 한정되어 있는 경우, 가용 메모리가 제한되어 있기 때문이다.