시간 복잡도 표기법 Big-O(빅-오) : 최악의 경우를 고려 Big-Ω(빅-오메가) : 최선의 경우를 고려 Big-θ(빅-세타) : 중간(평균)
알고리즘이란 문제를 해결하는 최선의 선택
효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같은 말
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 의미
효율적인 알고리즘 구현 : 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘 구성
시간 복잡도는 주로 빅-오 표기법을 사용해서 표기
1. Big-O 표기법
최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있음
최소한 특정 시간 이상이 걸린다혹은이 정도 시간이 걸린다를 고려하는 것보다이 정도 시간까지 걸릴 수 있다를 고려해야 그에 맞는 대응이 가능 * 최선의 경우만 고려한 경우 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하므로 문제를 파악하는 데 많은 시간이 필요
최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 최악의 경우도 고려하여 대비하는 것이 바람직
Big-O 표기법의 종류 : O(1) > O(logn) > O(n) > O(n^2) > O(2^n) 순서로 빠름
1초가 걸리는 입력의 크기
시간복잡도
입력의 크기
O(n)
100,000,000
O(n log n)
5,000,000
O(n^2)
10,000
O(n^3)
500
O(2^n)
26
O(n!)
11
1-1. O(1) : constant complexity
function O_1_algorithm(arr, index) {
return arr[index]
}
let arr = [1, 2, 3, 4, 5]
// arr의 길이가 100만이라도, 즉시 해당 index에 접근해 값을 반환할 수 있음
let index = 1
let result = O_1_algorithm(arr, index)
console.log(result)
// 2
입력값이 증가하더라도 시간이 늘어나지 않는데, 이는 입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있음을 의미
1-2. O(n) : linear complexity
// 입력값(n)이 1 증가할 때마다 코드의 실행 시간이 1초씩 증가
function O_n_algorithm(n) {
for (let i = 0; i < n; i++) {
// do something for 1 second
}
}
// 입력값(n)이 1 증가할때마다 코드의 실행 시간이 2초씩 증가
function another_O_n_algorithm(n) {
for (let i = 0; i < 2n; i++) {
// do something for 1 second
}
}
입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미
2n, 5n 을 모두 O(n)이라고 표기 * 입력값이 커지면 커질수록 계수(n 앞에 있는 수)의 의미(영향력)가 점점 퇴색되기 때문
1-3. O(log n) : logarithmic complexity
let i = 4
while(Math.floor(i) > 0) {
i = i / 2
}
console.log(i) // 0.5
Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가짐
같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)
이진탐색트리(Binary Search Tree) : 같은 로직으로 O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법) * 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어듬
1-4. O(n^2) : quadratic complexity
// 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
}
}
}
// n^3 : 삼중반복문
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
}
}
}
}
입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미 * 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 되는 알고리즘의 시간 복잡도
n^3과 n^5 도 모두 O(n2)로 표기 * n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문
1-5. O(2^n) : exponential complexity
function fibonacci(n) {
if (n <= 1) {
return 1
}
return fibonacci(n - 1) + fibonacci(n - 2)
}
Big-O 표기법 중 가장 느린 시간 복잡도를 가짐
재귀로 구현하는 피보나치 수열은 O(2^n)의 시간 복잡도를 가진 대표적인 알고리즘 * n이 100 이상이면 평생 결과를 반환받지 못할 수 있음
2. 크롬 개발자 도구에서 함수 실행 시간 측정 방법
var t0 = performance.now()
fib(50) // 여기에서 함수 실행을 시켜주세요
var t1 = performance.now()
console.log("runtime: " + (t1 - t0) + 'ms')
Greedy Algorithm 탐욕 알고리즘
매 순간 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식
항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있음
1. 단계적 절차
선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복
2. 최적의 해를 보장하지 못하는 특정한 상황
탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음
최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성 * 위의 2가지 조건을 성립해야 함
Dynamic Programming
동적 계획법
주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식 * 탐욕 알고리즘과 같이 작은 문제에서부터 출발한다는 점은 같으나 Dynamic Programming은 모든 경우의 수를 조합해 최적의 해법을 찾는다는 점에 차이가 있음
1. 단계적 절차
하위 문제를 계산한 뒤 그 해결책을 저장
나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄임 * 하나의 문제는 단 한 번만 풀도록 하는 알고리즘
2. 사용 조건
Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견되는 경우 * 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 함
Optimal Substructure : 작은 문제에서 구한 최적의 해결 방법(Optimal solution)의 결합으로 그것을 포함하는 큰 문제의 최적의 해법(Optimal solution)을 구할수 있는 경우 * 작은 문제에서 구한 정답을 큰 문제에서도 사용될 수 있어야 함
3-1. Recursion + Memoization으로 구현하기
큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여, 이 방식을 Top-down 방식이라고도 함
// fibMemo 함수의 파라미터로 n 과 빈 배열을 전달
// 빈 배열은 하위 문제의 결괏값을 저장하는 데에 사용
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
}
3-2. 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]
}
구현(Implementation)
구현 능력 : 정해진 시간 안에 빠르게 문제를 해결하는 능력
구현 문제 : 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것
구현 능력을 보는 대표적인 사례 : 완전 탐색(brute force), 시뮬레이션(simulation)
1. 완전 탐색(brute force)
문제 해결을 할 때의 두 가지 규칙 1. 문제를 해결할 수 있는가? : 모든 문제는 완전 탐색으로 풀 수 있음 2. 효율적으로 동작하는가? : 최악의 경우 끝까지 탐색해야 하기에 두 번째 규칙을 만족할 수 없음
모든 경우의 수를 탐색하는 모든 경우를 통칭
문제를 풀 수 있는 가능한 모든 방법을 고려한 후 효율적으로 동작하는 알고리즘이 전부 탐색할 수밖에 없다고 판단될 때 적용
완전 탐색 : Brute Force(무차별 대입), 재귀, 순열, DFS/BFS 등 여러 가지 존재 * Brute Froce : 조건/반복을 사용하여 해결
2. 시뮬레이션(simulation)
모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형
Algorithm with Math
GCD/LCM(최대공약수, 최소공배수)
최대 공약수(GCD. Greatest Common Divisor) : 둘 이상의 공약수 중에서 최대인 수 * 유클리드호제법 사용
최소 공배수(LCM. Least Common Multiple) : 둘 이상의 공배수 중에서 최소인 수 * 두 자연수의 곱 / 최대공약수
1. 최대공약수 (GCD)
가로 24cm, 세로 12cm인 직사각형 모양 조형물의 가장자리에 조명을 설치하려고 합니다. 네 모퉁이에는 조명을 반드시 설치해야하고, 나머지 조명은 일정한 간격으로 설치하려고 할 때, 필요한 최소한의 조명 개수는 몇 개일까요? 이때, 꼭지점을 제외한 직사각형의 모든 변에는 최소 하나 이상의 조명이 반드시 설치되어야 합니다. (단, 설치한 조명의 간격은 정수로 이루어진 cm 단위입니다.)
24와 12의 최대공약수는 12, 하지만 위 문제에선 12를 제외한 최대 공약수인 6 * 직사각형의 모든 변에, 최소 하나 이상의 조명이 설치되어야 하기 때문
가로 : 6 간격으로 조명 설치 => 24/6 X 2
세로 : 6 간격으로 조명 설치 => 12/6 X 2
반복문을 이용한 방법
function GCD(a, b) {
// 단, a가 b보다 커야함
let R
// R이 0이 될 때까지
while (a % b !== 0) {
R = a % b
a = b
b = R
}
return b
}
재귀를 이용한 방법
function GCD (a, b) {
if(a % b === 0) {
return b
}
return GCD(b, a % b)
}
한줄로 작성한 코드
const GCD = (a, b) => a % b === 0 ? b : GCD(b, a % b);
2. 최소공배수 (LCM)
방역용 마스크를 제작/판매하는 Mask States 사는 이례적인 전염성 독감 예방을 위해 기존 가격을 유지하며 약속된 물량의 방역용 마스크를 제공하고 있습니다. 이 회사는 사장을 포함하여 A, B, C 세 명뿐이고, 이들 모두 마스크를 제작합니다. 각각의 제작 속도는 다음과 같습니다. A는 55분마다 9개를, B는 70분마다 15개를, C는 85분마다 25개의 방역용 마스크를 만들 수 있습니다. 이 회사의 사람들은 05:00 시부터 동시에 마스크를 만들기 시작하여 각 55분, 70분, 85분 동안 연속으로 마스크를 제작한 후,5분씩 휴식을 취합니다. 이들 세 명이 처음으로 동시에 쉬는 시점이 퇴근 시간이라면, 이날 하루에 제작한 마스크는 모두 몇 개인가요? (휴식시간과 퇴근시간이 겹치는 경우, 휴식을 취한 뒤 퇴근합니다.)
60, 75, 90의 최소공배수는 900
A : 900분 동안 135개 (900/60 = 15 => 15 X 9)
B : 900분 동안 180개 (900/75 = 12 => 12 X 15)
C : 900분 동안 250개 (900/90 = 10 => 10 X 25)
GCD를 이용해 LCM 구하기
let LCM = a*b/GCD
LCM을 구하는 함수
function LCM (a, b) {
return a * b / GCD(a, b)
}
한줄로 작성한 코드
// 한줄로 작성한 코드
const LCM = (a, b) => a * b / GCD(a, b)
3. 순열/조합
순열
한 자리 숫자가 적힌 종잇조각이 흩어져 있습니다. 흩어진 종잇조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 종이에 기록된 모든 숫자가 배열로 주어진다면, 이 종잇조각으로 만들 수 있는 소수는 몇 개인가요?
순열 : n개 중에서 일부만을 선택해 순서를 지키며 나열하는 것으로 나열하는 순서가 다르면 서로 다른 경우로 파악
Permutation의 약자 P로 표현
일반식 :nPr = n! / (n - r)!
조합
왕비를 피해 일곱 난쟁이와 함께 평화롭게 생활하고 있던 백설 공주에게 위기가 찾아왔습니다. 하루일과를 마치고 돌아온 "일곱" 난쟁이가 "아홉" 명이었던 겁니다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했습니다. (뛰어난 수학적 직관력을 가지고 있던) 백설 공주는 일곱 난쟁이의 키의 합이 100임을 기억해 냈습니다. 아홉 난쟁이 각각의 키가 주어질 때, 원래 백설 공주와 평화롭게 생활하던 일곱 난쟁이를 찾는 방법은 무엇인가요?
조합 : 순열과 달리 순서를 고려하지 않음
Combination의 약자 C로 표현
일반식 :nCr = n! / (r! * (n - r)!)
멱집합
집합의 모든 부분집합
모든 부분집합을 나열하는 방법 : 가장 앞 원소(혹은 임의의 집합 원소)가 있는지, 없는지에 따라 단계를 나누는 기준을 결정
집합의 요소가 n개일 때 모든 부분집합의 개수는 2n개
멱집합을 구하는 방법은 순환 구조를 띠는 데, 순환구조는 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법 * 문제를 작은 단위로 줄여나가는 재귀를 응용할 수 있음
댓글