티스토리 뷰
[알고리즘] 시간 복잡도/ 공간 복잡도, Greedy Algorithm, Dynamic Programming
codeyun2 2023. 2. 7. 22:51코딩 테스트
기업에서는 알고리즘 풀이로 지원자의 역량을 가늠하고, 개발자다운 사고방식을 봄
알고리즘 문제풀이에 중요한 것은 해답을 효율적인 방법으로 찾는 것
새로운 문제에 봉착했을 때 전략과 알고리즘을 구상하여 실제 코드로 구현해 보는 경험은 매우 중요함
알고리즘
문제를 해결하는 최선의 선택
문제를 해결하기 위해 절차를 정의하고 공식화한 형태로 표현한 문제 풀이 방법
프로그래밍에서 알고리즘: input을 통해 output을 얻기 위한 계산 과정
절차가 명확하게 표현되어 있고,
다양한 문제 해결 과정에서 나타나는 불필요한 작업들을 효율적으로 줄여주는 알고리즘이 좋은 알고리즘임
문제 해결이 정확하고 빠를수록 구현 능력이 좋다고 말함
(구현 능력을 보는 대표적 사례: 완전 탐색, 시뮬레이션)
구현 문제, 구현 유형
: 본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어,
문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표하는 것
알고리즘이라고 불리기 위한 조건
1. 입력(input)
출력을 위해 필요한 자료를 입력받아야 함(입력 받지 않아도 되는 알고리즘도 있음)
2. 출력(Output)
알고리즘이 실행되면 반드시 한 가지 이상의 결과를 출력해야 함
출력이 없다면 알고리즘이 끝났는지 확인할 방법이 없음
유한성과도 연관
3. 유한성(Finiteness)
유한한 명령어를 수행하고 유한한 시간 내에 종료해야 함(= 반드시 종료되어야 함)
무한하다면 제대로된 알고리즘으로 동작하는 것이 아님
4. 명확성(Definiteness)
알고리즘의 각 단계는 단순하고 명확해야하며 모호해서는 안 됨
5. 효율성(Efficiency)
모든 과정은 명백하게 실행 가능해야 하며 실행 가능성이 떨어지는 알고리즘은 효율적이지 못한 알고리즘임
시간 복잡도와 공간 복잡도가 낮을 수록 효율적인 알고리즘임
알고리즘 순서가 달라지면 결과 또한 다르게 나타날 수 있어 주의 필요
정확하지 않은 알고리즘은 정확하지 않은 해(解)를 내놓게 됨
-> 정확하지 않은 답은 혼란을 주고 프로그래밍 자체에 큰 문제를 야기할 수 있음
시간 복잡도(Time Complexity)
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가
효율적인 알고리즘이란 입력값이 커짐에 따라 시간이 증가하는 비율을 최소화하는 알고리즘을 구현하는 것
Big-O 표기법
프로그램이 실행되는 과정에서 소요되는 최악의 시간을 고려
Big-O | 빅오 | 최악 |
Big-Ω | 빅오메가 | 최선 |
Big-θ | 빅세타 | 중간(평균) |
1. O(1) constant complexity
입력값이 증가하더라도 시간이 늘어나지 않음
입력값의 크기와 관계없이 즉시 출력값을 얻어낼 수 있음
function arrIndex(arr, index) {
return arr[index]
}
2. O(log n) logarithmic complexity
O(1) 다음으로 빠른 시간 복잡도
BST(Binary Search Tree): 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어드는 알고리즘
3. O(n) linear complexity
입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것
ex. 1일 때 1초 100일 때 100초
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배 상관x)
O(2n)이 아닌 O(n)으로 표기
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)과 마찬가지로 n이 커질수록 지수의 영향력이 점점 퇴색하기 때문에 n^3, n^5도 모두 O(n^2)로 표기
5. O(2^n) exponential complexity
가장 느린 시간 복잡도
구현한 알고리즘의 시간 복잡도가 O(2^n)이라면 다른 접근 방식을 고민해 보는 것이 좋음
n이 40인 경우 수초, n이 100 이상이라면 결과를 받지 못할 수도 있음
ex. 재귀로 구현한 피보나치 수열
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
데이터 크기에 따른 시간 복잡도
코딩 테스트 문제를 풀 때에는 정확한 값을 제한된 시간 내에 반환하는 프로그램을 작성해야하기 때문에
시간 제한과 데이터 크기 제한에 따른 시간 복잡도를 어림잡아 예측해 보는 것이 중요
데이터 크기 제한 | 예상되는 시간 복잡도 | |
n <= 1,000,000 | O(n) 또는 O(log n) | 시간 복잡도 고려 |
n <= 10,000 | O(n^2) | |
n <= 500 | O(n^3) | 시간 복잡도에 신경 쓰기보다 구현에 집중 |
공간 복잡도(space complexity)
알고리즘을 수행하는데 필요한 메모리 총량
시간 복잡도와 비슷하게 Big-O 표기법 사용
프로그램이 요구하는 공간
1. 고정적인 공간
처리할 데이터의 양과 무관하게 항상 요구되는 공간이라 프로그램 성능에 큰 영향을 주지 않음
2. 가변적인 공간
처리할 데이터의 양에 따라 다르게 요구되는 공간으로 프로그램 성능에 큰 영향을 끼침
ex. 팩토리얼: 변수 n에 따라서 n부터 1까지 재귀 함수가 스택에 쌓이게 됨. 공간 복잡도 O(n)
function factorial(n) {
if(n === 1) {
return n;
}
return n*factorial(n-1);
}
공간 복잡도의 중요성
시간 복잡도보다는 중요성이 떨어지며, 보통 시간 복잡도에 충족하면 공간 복잡도도 얼추 통과함
공간 복잡도가 크다면 변수가 너무 많은 공간을 차지하도록 설정하지 않았는지 확인
아래의 경우 공간 복잡도를 중요하게 봐야 함
- 하드웨어 환경이 한정되어 있는 경우(ex. 임베디드, 펌웨어 등) 가용 메모리가 한정되어 있기 때문
- Dynamic Programming(DP, 동적 계획법)
: DP 알고리즘 자체가 구현 시 메모리를 많이 요구하기 때문에 입력값의 범위가 넓어지면 사용하지 못하는 경우가 많음
알고리즘 유형
1. Greedy Algorithm 그리디 알고리즘
탐욕스러운, 욕심 많은
탐욕적 알고리즘
선택의 순간마다 당장 눈앞에 보이는 최적의 값을 쫓아 최종적인 해답에 도달하는 방법
문제를 해결하는 매순간 최적이라 생각하는 해답(locally optimal solution)을 찾으며
이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식
Greedy Algorithm 문제 해결 단계
① 선택 절차(Selection Procedure): 현재 상태에서 최적의 해답을 선택
② 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
③ 해답 검사(Solution Check): 문제가 해결되는지 검사하고, 해결되지 않았다면 ①로 돌아가 과정 반복
탐욕 알고리즘을 적용하려면 성립해야 하는 조건
① 탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않음
② 최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성
항상 최적의 결과를 도출하는 것은 아니지만 어느정도 최적에 근사한 값을 빠르게 도출할 수 있음
-> 근사 알고리즘으로 사용
최적의 해가 아닌 경우
마시멜로를 당장 받으면 1개를 얻고, 1분 뒤에 받으면 2개를 얻음
당장은 1개 받는 것이 최선이지만 전체적으로 봤을 때 1분 뒤에 받는 것이 최적의 선택임
Greedy 알고리즘 예제
거스름돈 잔돈수를 최소화하기
조건
- 물건을 구매하고 항상 1000엔을 지불
- 잔돈의 종류는 500엔, 100엔, 10엔, 5엔, 1엔
- 리턴값: 동전 개수
function keepTheChange(input) { // 지불해야 할 금액
// 1000엔 지폐를 내고 거슬러 받아야 할 금액
let change = Number(1000 - input);
// 동전 개수
let count = 0;
// 잔돈 종류 배열
const joiCoins = [500, 100, 50, 10, 5, 1];
// 잔돈 종류 만큼 반복
for(let i = 0; i < joiCoins.length; i++){
// 거스름돈이 0원이 되면 break
if(change === 0) break;
// 거스름돈과 잔돈을 나눈 몫을 카운팅
count += Math.floor(Number(change/joiCoins[i]));
// change에 거스름돈을 잔돈으로 나눈 나머지를 재할당
change %= joiCoins[i];
}
//count 리턴
return count;
}
2. Dynamic Programming 동적 계획법
탐욕 알고리즘과 함께 언급되는 알고리즘
모든 경우의 수를 조합해 최적의 해법을 찾음
주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제 해결
하위 문제를 계산한 뒤 그 해결책을 저장, 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄임
-> 하나의 문제는 단 한번만 풀도록 하는 알고리즘
두 조건을 만족해야 함
① Overlapping Sub-problems: 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제가 중복해서 발견됨
큰 문제로부터 나누어진 작은 문제의 결과가 큰 문제를 해결하는데 여러 번 반복해서 사용됨(피보나치 수열 재귀)
② Optimal Substructure: 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제의 정답과 같음
최적의 문제 해결 방법(Optimal solution).
주어진 문제의 작은 문제들의 최적의 해법을 찾아 결합하면 전체 문제의 최적의 해법을 구할 수 있음
Dynamic Programming 예시
- 피보나치 수열
1. Recursion + Memoization
하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해놓은 해결책 이용(= Memoization)
Memoization: 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거함으로써 프로그램 실행 속도를 빠르게 하는 기술
큰 문제를 해결하기 위해 작은 문제를 호출하는 Top-down방식
재귀로만 푸는 경우 O(2^n)
메모이제이션을 이용하면 O(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;
}
2. Iteration + Tabulation
Tabulation: 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때 제일 작은 값부터 구해 리스트에 작성함으로써 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술
하위 문제의 결과값을 배열에 저장하고 필요할 때 조회하여 사용
재귀 함수를 이용한 방법과 같으나
반복문을 이용한 방법은 작은 문제에서 시작하여 큰 문제를 해결해 나가는 Bottom-up방식
function fibTab(n) {
if(n <= 2) {
return 1;
}
// n 이 1 & 2일 때의 값을 배열에 미리 저장
let fibNum = [0, 1, 1];
for(let i = 3; i <= n; i++) {
fibNum[i] = fibNum[i-1] + fibNum[i-2];
// n >= 3 부터 앞서 배열에 저장해 놓은 값을 이용하여
// n번째 피보나치 수를 구한 뒤 배열에 저장
}
return fibNum[n];
}
- 2*1 타일링
맨 마지막 타일은 세로 타일 1개이거나 가로 타일 2개인 2가지 경우
n = 4일 때 세로 타일 1개를 뺀 n = 3의 경우와, 가로 타일 2개를 뺀 n-2의 경우의 수를 더해 5
function tiling2x1(n) {
let memo = [0, 1, 2];
for (let i = 3; i <= n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n];
};
3. 완전 탐색
가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식
모든 문제는 완전 탐색으로 풀 수 있지만 효율적으로 동작하지 않기 때문에
문제를 풀 가능한 모든 방법을 고려한 후 효율적으로 동작하는 알고리즘이 완전 탐색 밖에 없다고 판단될 때 사용
ex. Brute Force, 재귀, 순열, DFS, BFS
Brute Force(무차별 대입)
조건/반복을 사용하여 해결
시행착오 방법론. 특정 암호를 풀기 위해 지능형 전략을 사용하지 않고 모든 값을 대입하는 방법
- 0-9의 수를 가진 4자리 숫자 자물쇠의 비밀번호를 잊은 경우 0000부터 9999까지 대입하며 최악의 경우 10000번의 시도 필요
컴퓨터 성능에만 의존하여 모든 가능성을 시도하기 때문에 최적의 솔루션이 아님
- 공간 복잡도와 시간 복잡도를 고려하지 않음
-> 프로세스 속도를 높일 수 있는 다른 알고리즘이 없을 때, 문제를 해결하는 여러 솔루션을 모두 확인해야 할 때 사용
일반적으로 문제의 규모가 현재 자원(시간, 공간)으로 충분히 커버가 가능한 경우에 사용하고,
불가능하다면 정확도를 조금 희생하고 더 효율적인 알고리즘 사용
Brute Force 알고리즘 예제
- 순차 검색 알고리즘(Sequential Search)
배열에 특정 값이 존재하는지 처음부터 끝까지 차례로 검색
function SequentialSearch2(arr, k) {
// 입력: 배열 arr와 찾을 값 k
// 출력: arr에 k가 있다면 인덱스 없다면 -1
let n = arr.length;
arr[n] = k; // 검색 키를 arr n인덱스에 할당
let i = 0; // while 반복문의 초기 값 지정
while (arr[i] !== k) { // 배열의 값이 k와 같지 않다면 반복
i = i + 1;
}
if (i < n) { // 배열 안에 k값이 있다면
return i; // i 반환
} else {
return -1; // -1 반환
}
}
- 문자열 매칭 알고리즘(Brute-Force String Matching)
길이가 n인 전체 문자열에 길이가 m인 문자열 패턴을 포함하는지 검색
function BruteForceStringMatch(T, P) {
// 입력: 문자열 T, 문자 패턴을 나타내는 문자열P
// 출력: T에 P가 존재하면 일치하는 첫번째 인덱스를 반환 없다면 -1을 반환
let n = T.length;
let m = P.length;
for (let i = 0; i <= n - m; i++) {
// 전체 요소개수에서 패턴개수를 뺀 만큼만 반복. 그 수가 마지막 비교요소이기 때문
// i 반복문은 패턴과 비교의 위치를 잡는 반복문
let j = 0;
// j는 전체와 패턴의 요소 하나하나를 비교하는 반복문
while (j < m && P[j] === T[i + j]) {
// j가 패턴의 개수보다 커지면 안되기때문에 개수만큼만 반복합니다.
// 패턴에서는 j인덱스와 전체에서는 i + j 인덱스의 값이 같은지 판단합니다.
// 같을때 j에 +1 합니다.
j = j + 1;
}
if (j === m) {
// 패턴의 문자열과 완전히 같은 부분이 존재한다면
// 이 때의 비교했던 위치를 반환
return i;
}
}
return -1;
}
- 선택 정렬 알고리즘 (Selection Sort)
컬렉션이 완전히 정렬될 때까지 현재 요소와 전체 배열을 비교하여
현재 요소보다 더 작거나 큰 요소(오름차순/내림차순에 따라)를 교환하는 정렬 알고리즘
function SelectionSort(arr) {
// 주어진 배열을 Selection Sort로 오름차순 정렬
// 입력: 배열
// 출력: 오름차순으로 정렬된 배열
for (let i = 0; i < arr.length - 1; i++) {
let min = i;
for (let j = i + 1; j < arr.length; j++) {
// arr[j]가 arr[min]보다 작다면
if (arr[j] < arr[min]) {
// min을 j로 재할당
min = j;
}
}
// 반복문이 끝났을 때(모든 비교가 끝났을때)
// min은 최소값의 인덱스를 가짐
// i값과 최소값을 바꿔줌
let temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
return arr;
}
- 버블 정렬 알고리즘 Bubble Sort
- Tree 자료 구조의 완전 탐색 알고리즘 - Exhausive Search(BFS, DFS)
- 동적 프로그래밍 DP(Dynamic Programming)
4. 시뮬레이션
문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠뜨리지 않고 코드로 옮겨 마치 시뮬레이션하는 것과 동일한 모습을 그리는 것
문제에 설명한 로직 그대로 코드로 작성하면 되기 때문에 문제 해결을 떠올리는 것 자체는 쉬울 수 있으나
조건이 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있음
문제 해결 시간 측정 방법
크롬 개발자 도구- 실행 환경에 따라 결과가 다르기 때문에 학습용으로만 사용할 것
함수 실행 후 밀리초- 함수 실행 전 밀리초
var t0 = performance.now();
fib(50); // 여기에서 함수 실행
var t1 = performance.now();
console.log("runtime: " + (t1 - t0) + 'ms')
23.02.07
코스 S4U11 알고리즘
'코드스테이츠(SEB_FE_42)' 카테고리의 다른 글
[자료형] 정규표현식 Regular Expression (0) | 2023.02.08 |
---|---|
[알고리즘] Algorithm Math (0) | 2023.02.08 |
[Deploy] Proxy (0) | 2023.02.06 |
[AWS] 레퍼런스 정리 (0) | 2023.02.05 |
[Deploy] CI/CD 배포 자동화 (0) | 2023.02.03 |