10월 7일 (수) 알고리즘

남이섬·2021년 10월 6일
TIL시간복잡도알고리즘
0

알고리즘이란 ?
알고리즘은 문제를 해결하는 최선의 선택이다

모든 경우의 수를 하나씩 비교해서 그 중 최선을 골라낸다
또, 하나씩 비교하지 않더라도 가장 좋아 보이는 것을 먼저 찾아냈다면, 뒤쪽의 경우의 수를 그냥 무시하는 경우도 있다

문제 해결 방식

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

  2. 문제를 어떻게 해결할 수 있는지 전략을 세운다
    수도코드를 작성한다
    전체적인 그림을 그려본다

  3. 문제를 코드로 옮긴다
    전략을 코드로 옮기고, 구현한 코드의 최적화를 시도해 본다

시간복잡도

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

  • 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성한것
  • 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다

Big-O 표기법

  • Big-O(빅-오)
  • Big-Ω(빅-오메가)
  • Big-θ(빅-세타)

Big-O 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다

"최소한 특정 시간 이상이 걸린다" 혹은 "이 정도 시간이 걸린다"를 고려하는 것보다 "이 정도 시간까지 걸릴 수 있다"를 고려해야 그에 맞는 대응이 가능하다

시간을 계산하는 것보다는 최악의 경우도 고려하여 대비하는 것이 바람직하다 따라서 다른 표기법보다 Big-O 표기법을 많이 사용한다

Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는 방법이다

O(1)

O(1)는 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다, 다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다

O(1)의 시간 복잡도를 가진 알고리즘

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

위 알고리즘에선 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다
예를 들어 arr의 길이가 100만이라도, 즉시 해당 index에 접근해 값을 반환할 수 있다

O(n)

O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다

예를 들어 입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘을 구현했다면, 그 알고리즘은 O(n)의 시간 복잡도를 가진다고 할 수 있다

O(n)의 시간 복잡도를 가진 알고리즘

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
	}
}

O_n_algorithm 함수에선 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가한다
즉 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어나고 있다

함수 another_O_n_algorithm 은 입력값이 1 증가할때마다 코드의 실행 시간이 2초씩 증가한다
이 알고리즘은 O(2n) 이라고 생각할 수 있다
하지만, 사실 이 알고리즘 또한 Big-O 표기법으로는 O(n)으로 표기한다

입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기한다

O(log n)

O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다

BST(Binary Search Tree)의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)이다

O(n^2)

O(n^2)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다

예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n2)라고 표현한다

O(n^2)의 시간 복잡도를 가진 알고리즘

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
			}
		}
	}
}

2n, 5n 을 모두 O(n)이라고 표현하는 것처럼, n^3과 n^5 도 모두 O(n^2)로 표기한다
n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에 이렇게 표기한다

O(2^n)

O(2^n)은 exponential complexity라고 부르며 Big-O 표기법 중 가장 느린 시간 복잡도를 가진다

구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋다

O(2n)의 시간 복잡도를 가지는 알고리즘

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

재귀로 구현하는 피보나치 수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘이다

브라우저 개발자 창에서 n을 40으로 두어도 수초가 걸리는 것을 확인할 수 있으며, n이 100 이상이면 평생 결과를 반환받지 못할 수도 있다

시간제한과 주어진 데이터 크기 제한에 따른 시간 복잡도를 어림잡아 예측해 보는 것은 중요하다

예를 들어 입력으로 주어지는 데이터에는 n만큼의 크기를 가지는 데이터가 있고,
n이 1,000,000보다 작은 수일 때 O(n) 혹은 O(nlogn)의 시간 복잡도를 가지도록 예측하여 프로그램을 작성할 수 있다

n^2의 시간 복잡도를 예측할 수 없는 이유는 실제 수를 대입해 계산해보면 유추할 수 있다

1,000,000^2은 즉시 처리하기에 무리가 있는 숫자이며 (1,000,000 * 1,000,000 = 1,000,000,000,000) 만약 n ≤ 500 으로 입력이 제한된 경우에는 O(n^3)의 시간 복잡도를 가질 수 있다고 예측할 수 있다

입력 데이터가 클 때는 O(n) 혹은 O(log n)의 시간 복잡도를 만족할 수 있도록 예측해서 문제를 풀어야 한다, 그리고 주어진 데이터가 작을 때는 시간 복잡도가 크더라도 문제를 풀어내는 것에 집중한다

대략적인 데이터 크기에 따른 시간 복잡도

Big-O는 상한 점근, Big-Ω(omega)는 하한 점근, Big-Θ(theta)는 그 둘의 평균을 나타낸다

Greedy Algorithm

Greedy는 "탐욕스러운, 욕심 많은" 이란 뜻이며, Greedy Algorithm(탐욕 알고리즘) 은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다
탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있다

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다

예시 1
손님이 물건을 사고 거스름돈을 받을 때,
동전의 갯수를 최소한으로 받는 방법

손님 : 4040원어치 물건을 사고, 5000원을 건냈을때
960원의 거스름돈을 받는다

500원짜리 동전을 한 개 선택합니다. 그다음은 100원짜리 동전을 네 개 선택하고, 그다음엔 50원짜리 동전과 10원짜리 동전을 각각 하나씩 선택

  1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택
  2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다, 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다
  3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다, 액수가 부족하면 1번 과정부터 다시 반복한다

탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다

하지만 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 한다

따라서 두 가지의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립하여야 한다

  • 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않아야한다
  • 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다
이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다

Github TIL 알고리즘

profile
남이섬
즐겁게 살자
이전 포스트

10월 5일 (화) Linux 심화

다음 포스트

10월 7일 (목) 순열, 조합, GCD / LCM, 멱집합

0개의 댓글