(S3W1) TIL 46일차 220405 (코딩테스트 준비)

오늘의 학습목표

• 알고리즘이 무엇인지 설명할 수 있다.
• 알고리즘 문제를 이해하고 전략을 세울 수 있다.
• 알고리즘 풀이에 필요한 수도 코드를 작성할 수 있다.
• 수도 코드에서 세운 전략을 코드로 구현할 수 있다.
• 내가 구현한 알고리즘을 자바스크립트 언어로 설명할 수 있다.

학습내용

시간 복잡도

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

시간 복잡도를 표기하는 방법은 다음과 같습니다.

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

위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법입니다.

Big-O 표기법

세 가지 시간 복잡도 표기법 중 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초의 시간이 걸리고, 입력값을 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
	}
}

 

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

 

O(log n) logarithmic complexity

Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가집니다. BST(Binary Search Tree)가 O(log n)의 예시입니다.

BST에선 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듭니다.

 

이해하기 쉬운 게임으로 비유해 보자면 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(n2) quadratic complexity

입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미합니다.

예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면,

이 알고리즘의 시간 복잡도는 O(n2)라고 표현합니다.

// O(n2)의 시간 복잡도를 가진 알고리즘
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)이라고 표현하는 것처럼, n3과 n5 도 모두 O(n2)로 표기합니다. n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에 이렇게 표기합니다.

 

O(2n) exponential complexity

Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다.

 

종이를 42번 접을 수 있다면 그 두께가 지구에서 달까지의 거리보다 커집니다. 고작 42번 만에 얇은 종이가 그만한 두께를 가질 수 있는 것은, 매번 접힐 때마다 두께가 2배로 늘어나기 때문입니다.

 

구현한 알고리즘의 시간 복잡도가 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 이상이면 평생 결과를 반환받지 못할 수도 있습니다.

 

Greedy Algorithm

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

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

김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다.

이때 김코딩은 어떻게 거슬러 주어야 할까요? 탐욕 알고리즘으로 동전의 개수를 헤아리는 일은, 우리가 일반적으로 거스름돈으로 동전을 선택하는 방법과 동일합니다. 거스름돈 960원을 채우기 위해서 먼저, 500원짜리 동전을 한 개 선택합니다. 그다음은 100원짜리 동전을 네 개 선택하고, 그다음엔 50원짜리 동전과 10원짜리 동전을 각각 하나씩 선택할 겁니다. 김코딩의 입장에 탐욕 알고리즘의 문제 해결 과정을 적용하면 다음과 같이 문제를 단계적으로 구분할 수 있습니다.

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

이 과정을 통해 얻은 문제에 대한 해답은 다음과 같습니다.

• 가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 줍니다.

김코딩이 아르바이트를 하러 간 사이에, 안타깝게도 김코딩의 집에 도둑이 들었습니다. 도둑의 가방은 35kg까지의 물건만 담을 수 있고, 김코딩의 집에는 4개의 물건이 있습니다.

도둑이 탐욕 알고리즘을 사용한다면 문제는 다음과 같이 간단해집니다.

 

1. 가방에 넣을 수 있는 물건 중 가장 비싼 물건을 넣습니다.

2. 그다음으로 넣을 수 있는 물건 중 가장 비싼 물건을 넣습니다. 이 과정을 반복합니다.

 

도둑의 가방은 35kg까지 담을 수 있고, 그림이 가장 비싸니 그림을 먼저 가방에 담을 수 있습니다. 남는 공간이 5kg밖에 남지 않아 더 훔칠 수 있는 물건이 없습니다. 그리고 이때 훔친 물건의 총 가치는 그림 하나의 가치와 같은 $3,000입니다. 만약 그림 대신 컴퓨터와 반지를 가방에 담았다면 어떨까요? 35kg이 넘지 않으면서 총 가치는 $3,500으로 그림 하나만 훔칠 때보다 더 많은 가치의 물건을 훔칠 수 있습니다.

 

탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식입니다. 그러나 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 합니다.

 

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

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

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

 

Implementation

알고리즘 문제를 푼다는 것은, 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환해 코드로 구현한다는 것과 같습니다. 

• 데이터를 정렬할 수 있는가?
• 데이터를 효율적으로 탐색할 수 있는가?
• 데이터를 조합할 수 있는가? ...etc

카테고리를 분류한다고 해도 내가 생각한 로직을 '코드로 구현'한다는 건 전부 공통적인 속성입니다. 이러한 문제 해결을 코드로 풀어낼 때, 정확하고 빠를 수록 구현 능력이 좋다고 말합니다.

구현 능력이 좋은 개발자를 선발할 의도로 구현 능력을 직접 평가하기도 합니다. 정해진 시간 안에 빠르게 문제를 해결하는 능력을 보기 위함입니다. 머리로 이해하고 있어도 코드로 작성하지 않거나 시간 부족으로 못한다면 정답이 될 수 없기 때문입니다. 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것을 구현 문제, 구현 유형이라고 통칭할 수 있습니다.

 

보통 이러한 문제들은 구현하는 것 자체를 굉장히 까다롭게 만듭니다. 지문을 매우 길게 작성하거나, 까다로운 조건이나 상황을 붙인다거나, 로직은 쉽지만 구현하려는 코드가 굉장히 길어지게 되는 문제들이 대다수입니다. 그렇기 때문에 깊은 집중력과 끈기가 필요합니다.

 

구현 능력을 보는 대표적인 사례에는 완전 탐색(brute force)과 시뮬레이션(simulation)이 있습니다.

 

완전 탐색

모든 문제는 완전 탐색으로 풀 수 있습니다. 굉장히 단순하고 무식하지만 답이 무조건 있다는 강력함이 있습니다.

예를 들어, 양의 정수 1부터 100까지의 임의의 요소가 오름차순으로 하나씩 담긴 배열 중, 원하는 값 N을 찾기 위해서는 배열의 첫 요소부터 마지막 요소까지 전부 확인을 한다면 최대 100 번의 탐색 끝에 원하는 값을 찾을 수 있습니다.

그렇지만, 문제 해결을 할 때엔 기본적으로 두 가지 규칙이 붙습니다.

• 문제를 해결할 수 있는가?
• 효율적으로 동작하는가?

완전 탐색은 첫 번째 규칙을 만족시킬 수 있는 강력한 무기이지만 두 번째 규칙은 만족할 수 없는 경우가 있습니다

완전 탐색은 단순히 모든 경우의 수를 탐색하는 모든 경우를 통칭합니다.

완전히 탐색하는 방법에는 brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등 여러 가지가 있습니다.

Brute Force (무차별 대입)

문제를 풀 때, 반복문이 아닌 배열을 전부 순회하는 메서드를 사용한다거나 간결한 코드를 위한 문법을 사용한다고 하더라도 배열을 전부 탐색하여 값을 도출한다는 것엔 변함이 없습니다.

 

시뮬레이션

시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형입니다.

문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있습니다.

 

문제에 대한 이해를 바탕으로 제시하는 조건을 하나도 빠짐없이 처리해야 정답을 받을 수 있습니다.

하나라도 놓친다면 통과할 수 없게 되고, 길어진 코드 때문에 헷갈릴 수도 있으니 주의해야 합니다.

 

Dynamic Programming (DP; 동적 계획법)

탐욕 알고리즘과 함께 언급하는 알고리즘으로, 줄임말로는 DP라고 하는 이 알고리즘은, 탐욕 알고리즘과 같이 작은 문제에서부터 출발한다는 점은 같습니다.

그러나 탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, Dynamic Programming은 모든 경우의 수를 조합해 최적의 해법을 찾는 방식입니다.

 

Dynamic Programming의 원리

주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결합니다.

하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄입니다. 다시 말해, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍입니다.

 

다이내믹 프로그래밍은 다음 두 가지 가정이 만족하는 조건에서 사용할 수 있습니다.

1. 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다. (Overlapping Sub-problems)
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. (Optimal Substructure)

첫 번째 조건인 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다 (Overlapping Sub-problems) 는 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다 는 말과 같습니다.

피보나치 수열을 예로 살펴보겠습니다.

피보나치 수열은 첫째와 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두 항의 합과 같은 수열입니다

function fib(n) {
	if(n <= 2) return 1;
	return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8...

7번째 피보나치 수 fib(7) 를 구하는 과정은 다음과 같습니다.

fib(7) = fib(6) + fib(5)
fib(7) = (fib(5) + fib(4)) + fib(5) // fib(6) = fib(5) + fib(4)
fib(7) = ((fib(4) + fib(3)) + fib(4)) + (fib(4) + fib(3)) // fib(5) = fib(4) + fib(3)
.....

피보나치 수열은 위 예시처럼 동일한 계산을 반복적으로 수행해야 합니다. 이 과정에서 fib(5) 는 두 번, fib(4) 는 세 번, fib(3) 은 다섯 번의 동일한 계산을 반복합니다.

 

이렇게 작은 문제의 결과를 큰 문제를 해결하기 위해 여러 번 반복하여 사용할 수 있을 때, 부분 문제의 반복(Overlapping Sub-problems)이라는 조건을 만족합니다.

 

그러나 이 조건을 만족하는지 확인하기 전에, 한 가지 주의해야 할 점이 있습니다.

 

주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라, 작은 문제의 결과가 큰 문제를 해결하는 데에 여러 번 사용될 수 있어야 합니다.

 

두 번째 조건인 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다에서 말하는 정답은 최적의 해결 방법(Optimal solution)을 의미합니다.

 

따라서 두 번째 조건을 달리 표현하면, 주어진 문제에 대한 최적의 해법을 구할 때 주어진 문제의 작은 문제들의 최적의 해법을 찾아야 합니다. 그리고 작은 문제들의 최적의 해법을 결합하면 결국 전체 문제의 최적의 해법을 구할수 있습니다.

 

Recursion + Memoization (Top-down)

다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 이용합니다. 이때 결과를 저장하는 방법을 Memoization이라고 합니다.

 

Memoization의 정의는 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술 입니다. 

// 재귀 함수에 Memorization을 적용하는 법
function fibMemo(n, memo = []) {
		// 이미 해결한 하위 문제인지 찾아본다
    if(memo[n] !== undefined) return memo[n];
    if(n <= 2) return 1;
		// 없다면 재귀로 결괏값을 도출하여 res 에 할당
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
		// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
    memo[n] = res;
    return res;
}

이런 풀이 과정이 마치, 위에서 아래로 내려가는 것과 같습니다. 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여, 이 방식을 Top-down 방식이라 부르기도 합니다.

 

Iteration + Tabulation (Bottom-up)

하위 문제의 결괏값을 배열에 저장하고, 필요할 때 조회하여 사용하는 것은 재귀 함수를 이용한 방법과 같습니다.

 

이번에는 반복문을 이용하여 다이내믹 프로그래밍을 구현합니다.

function fibTab(n) {
    if(n <= 2) return 1;
    let fibNum = [0, 1, 1];
		// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
    for(let i = 3; i <= n; i++) {
        fibNum[i] = fibNum[i-1] + fibNum[i-2];
		// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
		// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다 
    }
    return fibNum[n];
}

재귀 함수를 이용한 방법이 문제를 해결하기 위해 큰 문제부터 시작하여 작은 문제로 옮아가며 문제를 해결하였다면, 반복문을 이용한 방법은 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법입니다.

 

따라서 이 방식을 Bottom-up 방식이라 부르기도 합니다.

 

오늘의 회고

오늘은 알고리즘 공부를 했는데, 토이를 보다가 풀만한 문제들이 나와서 행복했습니다 ㅋㅋ 1번부터 3번까지는 코플릿 잘 풀었는데 4번 Advanced는 많이 어렵더군요 .. 일단 주변 분들이 Dynamic Programming은 기초를 좀더 닦고 하는게 좋을 것 같다고 하셔서 기본을 다지는데 좀더 시간을 투자할 계획입니다.

기본을 다지는데 시간을 투자할 계획으로는! 프로그래머스 레벨 1 부터 풀어보기 입니다!

오늘 프로그래머스 레벨 1 두문제를 풀어봤는데 생각보다 할만 하고 재밌었습니다.

프로그래머스 굉장히 잘되있더라고요! 게임처럼 좀 재밌게 꾸준히 해보려고 노력해보겠습니다 ㅎㅎ