[TIL] 알고리즘 이해하기

Jade·2022년 12월 9일

Today I learn

목록 보기

70/77

❓ 알고리즘

알고리즘은 어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제의 풀이 방법, 해(解). 프로그래밍에서는 input 값을 통해 output 값을 얻기 위한 계산 과정을 의미한다고 한다.

😈 사실 비전공자 개발자 지망생들에게 알고리즘이란...선배들의 입으로 전해내려오기를 그 위세가 가히 무시무시한... 그런 공부 영역 중 하나라고 할 수 있겠다. 모쪼록 교육 과정에 알고리즘과 코딩 테스트 대비가 포함되어 있어서 다행이라는 생각이 든다...

알고리즘이 되기 위한 일정한 조건들

Input : 출력에 필요한 자료를 입력 받을 수 있다. (입력 받지 않아도 되는 알고리즘 ‘ex: 원주율의 1조번째 자리를 구하는 경우 입력은 없으나 출력은 있다’ 도 있음)
Output : 실행 시 적어도 한가지 이상의 결과를 반드시 출력해야 함.
Finiteness : 유한한 명령어를 수행하고, 유한한 시간 내 종료해야 함.
Definiteness : 각 단계가 단순하고 명확해야 한다.
Efficiency : 가능한 한 효율적이어야 함. 모든 과정이 명백하게 실행 가능해야 함. 시간 복잡도와 공간 복잡도가 낮을수록 효율적인 알고리즘.

알고리즘의 중요성

좋은 알고리즘은 절차가 명확하게 표현되어 있고 효율적이므로 다양한 문제 해결 과정에서 나타나는 불필요한 작업들을 줄여줄 수 있음.

⏰ 시간 복잡도 (Time Complexity)

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

효율적인 알고리즘은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 말한다.

시간 복잡도는 주로 빅-오 표기법을 사용해 나타내는데, 시간 복잡도를 나타내는 방법에는 빅-오 표기법(최악) 외에도 빅-오메가(최선), 빅-세타(중간/평균) 표기법이 있다.

Big-O 표기법

빅오 표기법은 최악의 경우를 고려하는 지표이다.
예를 들어 최소한 특정 시간 이상이 걸린다, 이 정도 시간이 걸린다를 고려하는 것보다는 (최악일 경우) 이정도 시간까지 걸릴 수 있다를 고려하는 것이 그에 맞는 대응이 가능해진다.

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

O(n) = linear complexity : 입력값이 증가함에 따라 시간 또한 같은 비율로 증가함.

//입력값 1 증가할 때마다 코드 실행시간이 1초씩 증가
function O_n_algorithm(n) {
	for (let i = 0; i < n; i++) {
	// do something for 1 second
	}
}

//입력값 증가할 때마다 코드 실행시간이 2초씩 증가 
//이 역시 O(n)에 해당됨. 
function another_O_n_algorithm(n) {
	for (let i = 0; i < 2n; i++) {
	// do something for 1 second
	}
}

O(log n) = logarithmic complexity : O(1) 다음으로 빠른 시간 복잡도 가짐.

자료구조에서 배웠던 BST(Binary Search Tree)에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다. 이해하기 쉬운 게임으로 비유해 보자면 up & down을 예로 들 수 있음.

    1. 1~100 중 하나의 숫자를 플레이어1이 고른다 (30을 골랐다고 가정).
    2. 50(가운데) 숫자를 제시하면 50보다 작으므로 down을 외친다.
    3. 1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
    4. 25보다 크므로 up을 외친다.
    5. 경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.

매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어들기 때문에 최악의 경우에도 7번이면 원하는 숫자를 찾아낼 수 있게 된다.
BST의 값 탐색도 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)이다.

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

//n3과 n5 도 모두 O(n2)로 표기한다. 
//n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에 이렇게 표기함.

O(2**n) = exponential complexity : 빅 오 표기법 중 가장 느린 시간 복잡도.

구현한 알고리즘의 시간 복잡도가 위와 같다면 다른 접근 방식 고민해보는 게 나음. 😅

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

재귀로 구현하는 피보나치 수열은 O(2**n)의 시간 복잡도를 가진 대표적인 알고리즘으로 브라우저 개발자 창에서 n을 40으로 두어도 수초가 걸리는 것을 확인할 수 있으며, n이 100 이상이면 평생 결과를 반환받지 못할 수도 있음.

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

일반적으로 코딩 테스트 문제를 풀 때는 정확한 값을 제한된 시간 내에 반환하는 프로그램을 작성해야 한다.
그러므로 시간제한과 주어진 데이터 크기 제한에 따른 시간 복잡도를 어림잡아 예측해보는 것이 중요함.

입력 데이터가 클 때는 O(n) 혹은 O(logn)의 시간 복잡도를 충족할 수 있도록 문제를 풀어야 하지만,
주어진 데이터가 작을 때는 시간 복잡도가 크더라도 문제를 풀어내는 것에 집중하는 게 좋다고 한다.

🏠 공간 복잡도 (Space Complexity)

공간 복잡도는 알고리즘이 수행되는 데에 필요한 메모리의 총량을 의미.
= 프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미함.

공간 복잡도 계산도 시간 복잡도 계산과 비슷하게 빅 오 (Big-O) 표기법
으로 표현함.

프로그램이 요구하는 공간은 고정적 공간과 함께 가변적 공간을 함께 요구하는데, 고정적인 공간은 처리할 데이터 양에 무관하게 항상 요구되는 공간으로서 프로그램에 성능에 그다지 영향을 주지 않음. 그러나 가변적 공간은 처리할 데이터 양에 따라 다르게 요구되는 공간으로 프로그램의 성능에 큰 영향을 준다.

보통 때는 공간 복잡도는 시간 복잡도보다 덜 중요함. 시간이 적으면서 메모리까지 지수적으로 증가하는 경우는 거의 없으며 시간 내에 발생하는 메모리 문제들은 보통 알고리즘을 구현할 때에 발생하는 문제이기 때문.

때에 따라 공간 복잡도를 중요하게 보는 경우가 있는데, 동적 계획법(Dynamic Programming)과 같은 알고리즘이나 하드웨어 환경이 매우 한정되어 있는 경우가 그렇다고 함.

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

공간 복잡도 예시

//factioral 함수는 재귀함수로 구현되어 있고
//변수 n에 따라 변수 n이 n개 만들어지므로 공간 복잡도가 O(n)

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

🧐 알고리즘 유형들

🧩 Greedy Algorithm

순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법

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

탐욕 알고리즘의 특징

탐욕적 선택 속성(Greedy Choice Property)
: 앞의 선택이 이후의 선택에 영향을 주지 않음.

최적 부분 구조(Optimal Substructure)
: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

장발장 빵 예시 🥐

가게에서 빵을 훔칠 때 35g까지만 담을 수 있고, 빵의 가격이 모두 다르고, 4종류가 1개씩 있고, 빵을 쪼개서 담을 수 있을 때 값이 많이 나가는 빵으로 가방을 채우고 싶다면 ?

1달러당 무게(반올림)
빵 1 : 13.3g / 빵 2 : 16.7g / 빵 3 : 2g / 빵 4 : 10g

해결방법
1. 가방에 넣을 수 있는 물건 중 무게 대비 가장 비싼 물건을 넣는다.
2. 그다음으로 넣을 수 있는 물건 중 무게 대비 가장 비싼 물건을 넣는다.
3. 만약, 가방에 다 들어가지 않는다면 쪼개어 넣는다.

$1당 2g인 3번 빵(5g) 먼저 가방에 담는다: 남은 가방의 무게 30g
$1당 10g인 4번 빵(20g)을 다음으로 담는다.: 남은 가방의 무게 10g
$1당 13.3g인 1번 빵(40g)을 다음으로 담을 수 있지만 40g을 온전히 담을 수는 없다. 쪼개서 10g만 넣음. : 남은 가방의 무게 0g

= $2.5 + $2 + $0.75 ⇒ 장발장은 최대 $5.25어치의 빵을 훔칠 수 있다!

이 문제에서 장발장이 빵을 쪼갤 수 없는 상황이라면 탐욕 알고리즘은 최적의 결과를 보장할 수 없다.
해당 상황에서 탐욕 알고리즘을 사용하게 되면 빈자리 5g이 남게 되는데, 빈자리 5g을 채워 더 큰 최대값을 만들 수 있는 최선의 상황이 있을 수 있게 되기 때문.

🧩 Algorithm 구현 유형

본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것을 구현 문제, 구현 유형이라고 통칭할 수 있음.

완전탐색
: 모든 문제는 완전 탐색으로 풀 수 있으며 “답이 무조건 있다”는 강력함이 있다.
하지만 문제 해결을 할 때 효율적으로 동작하는가에 대한 규칙을 만족할 수 없는 경우임.
완전 탐색은 단순히 모든 경우의 수를 탐색하는 모든 경우를 통칭한다. 완전히 탐색하는 방법에는 Brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS등 여러 가지가 있음.
시뮬레이션
: 시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형이다.
보통 문제에서 설명해 준 로직 그대로 코드로 작성하면 되어서 문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있음.

🧩 Dynamic Programming

: 동적 계획법(DP)은 주어진 문제를 여러 개의 작은(하위)문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합해 최종 문제를 해결함.

하위 문제 계산한 뒤 그 해결책을 저장하고 나중에 동일한 하위 문제를 만날 경우 저장된 해결책 적용해 계산 횟수 줄임 = 하나의 문제는 단 한 번만 푼다

(Greedy Algorithm이 매 순간 최적의 선택을 찾는 방식이라면, Dynamic Programming은 모든 경우의 수를 조합해 최적의 해법을 찾는 방식이라고 한다.)

동적 계획법을 사용할 수 있는 조건

Overlapping Sub-problems
: 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다.
그러나 주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라, 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 함.

Optimal Substructure
: 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.
주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아서 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있어야 함.

일단 개념만 이정도로 정리하고, 오늘 푼 문제들은 알고리즘 태그로 다시 정리해봐야겠다 !

Jade

키보드로 그려내는 일

이전 포스트

[TIL] Proxy

다음 포스트