1. 알고리즘
1-1. 알고리즘이란?
- 입력 정수에서 출력 정수를 구하기 위한 일반화된 작업을 정리하여 의사코드나 소스코드의 형태로 구현한 것이다.
- 문제를 해결하는 방법 그 자체를 말한다.
(알고리즘 충족 조건)
ex) 요리 레시피
- 타당성 : 구현할 수 있고 실용적이어야 한다.
=> 알고리즘의 성능 담당 - 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다.
- 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다.
- 유한성 : 특정 수의 작업 이후에 정지해야한다.
- 입력 : 정의된 입력을 받아들일 수 있어야 한다.
- 출력 : 답으로 출력을 내보낼 수 있어야 한다.
- 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다.
1-2. 알고리즘 성능 기준
- 시간 기준 - 알고리즘이 적은 시간이 사용될 수록 빠르게 동작했다는 것을 의미한다.
- 공간 기준 - 알고리즘이 적은 공간을 사용 할수록 적은 용량의 메모리를 사용했다는 것을 의미한다.
(어떤 것을 기준으로 하는 것이 중요한가?)
- 주어진 상황에 따라서 필요한 속도, 메모리의 기준이 다르기 때문에 명확하게 정할 수 없다.
- 하지만 코딩테스트에서는 제한 시간 및 사용가능한 메모리가 주어지기 때문에 명확하다.
- 따라서 알고리즘의 수행속도와 특성을 분석하는 능력을 키우는게 필요하다.
2. 시간 복잡도 분석
: 동일한 입력값으로부터 출력값까지의 시간을 측정하는 방법으로
좀 더 빠른 알고리즘을 만들기 위해는 "알고리즘의 속도를 어떻게 측정할지"를 정해야 한다.
(알고리즘 속도 측정을 해야하는 이유는?)
- 알고리즘을 바뀌었을때 어떤 알고리즘이 더 빠른지 알 수 없지 때문에
- 문제에서 해결할 입력의 크기가 매우 작을 경우 시간복잡도는 큰 의미를 갖지 못할 수 있다.
-> 따라서 입력값이 매우 크다고 보통 가정한다.
(1) 절대시간 측정
: 알고리즘이 동작이 완료 할때까지 걸리는 시간 측정
(절대시간 측정시 문제점)
- 여러가지 변수에 따라 결과가 다르게 나올 수 있기 때문에 환경에 제약받지 않는 기준이 있어야 한다.
ex) 언어, 하드웨어, 운영체제, 컴파일러등 - 수행시간이 다양한 입력에 대한 실행시간을 반영하지 못한다.
(2) 연산횟수 측정
: 알고리즘의 동작이 완료될 때까지 연산횟수가 몇번인지 계산
- 코딩테스트에서는 제한시간 내에 수행 할 수 있을지가 중요하기 때문에,
최악의 경우를 기준으로 연산 횟수를 정하는게 합리적 - 알고리즘의 수행시간을 지배하는 것은 반복문이다.
=> 입력의 크기에 따라 수행횟수가 정해질 수 있기 때문
ex)
- (입력의 크기가 작을때) 반복문보다 다른 부분이 갖는 비중이 클 수 있음
- (입력의 크기가 클 때) 반복문이 알고리즘 수행시간을 지배함
3. 함수에 따른 시간복잡도
(함수에 따른 시간복잡도 크기)
=> (1)부터 (7)까지 우선순위이면 높은 순위일수록 복잡한 함수라고 볼 수 있다.
(시간 복잡도에 영향을 미치는 것)
ex) 다항(지수) vs 선형 vs 선형이하(로그)
=> 주로 입력되는 값에 따라서 알고리즘을 다르게 써야할 수도 있다.
ex) 간단하게 밑값이 2인 식들을 기준으로 예시로 잡았다.
- 그래프를 보면(root 2 ~ 4) 범위를 기준으로 값의 대소관계가 바뀐다.
- 만약에 주로 쓰이는 입력값이 해당 범위 내부에 속한다면 오히려 지수함수를 쓰는게 더 효율적일수 있다.
- 따라서 시간복잡도로 알고리즘의 성능을 파악할 수도 있지만
주로 쓰이는 입력값의 분포나 특징도 파악하는 것도 알고리즘을 선택시 반영하는게 좋다.
3-1. 선형시간 알고리즘
=> 다항함수, 로그함수와 다항함수의 조합
ex) 배열 내부의 최대값을 찾는 코드
#include <stdio.h>
int findMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
int max = findMax(arr, n);
printf("The maximum value in the array is: %d\n", max);
return 0;
}- findmax함수 내부에서 배열의 크기 N 만큼만 실행되기 때문에 시간복잡도는 N이다.
- 입력값을 넣으면 직선의 형태를 띠고 있기 때문에 선형 시간 알고리즘이라고 부른다.
- 선형 시간에 실행되는 알고리즘을 대개 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘이다.
3-2. 선형이하 시간 알고리즘
=> 로그함수, 상수함수
ex) 배열내에 값 검색
#include <stdio.h>
int binarySearch(int arr[], int l, int r, int x) {
while (l <= r) {
int m = l + (r - l) / 2;
// 값이 중간 값과 같은 경우
if (arr[m] == x)
return m;
// 값이 중간 값보다 작은 경우
if (arr[m] < x)
l = m + 1;
// 값이 중간 값보다 큰 경우
else
r = m - 1;
}
// 값이 배열에 없는 경우
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result != -1)
printf("Element is present at index %d\n", result);
else
printf("Element is not present in array\n");
return 0;
}- binarysearch함수는 내부에서 이미 정렬된 배열에서 원하는 값을 함수이다.
- 매 반복마다 탐색 범위를 절반으로 줄이기 때문에 배열의 크기가 n이라고 할 때 시간복잡도는 log_2(n)이다.
(증명 - 왜 시간복잡도가 지수함수인가?)
"1 + 2^1 + 2^2 + ... + 2^k = N " 식에 대한 등비수열의 합
$$ N = \frac{a(1 - r^n)}{1 - r} (r=2) $$
r=2이고 a=1이기 때문에 식을 전개했을 때 "N = 2^k"가 나온다.
지수로그 변환으로 k = log_2(N)이 된다.
따라서 이분탐색알고리즘의 시간복잡도는 로그함수이다.
3-3. 지수시간 알고리즘
=> 지수 함수
ex) 재귀함수 형식의 피보니치 수열
#include <stdio.h>
// 재귀적으로 피보나치 수를 계산하는 함수
int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n = 10; // 계산할 피보나치 수의 위치
printf("Fibonacci number at position %d is: %d\n", n, fibonacci(n));
return 0;
}- n이 1이 될때까지 2개의 재귀함수를 호출하여 진행된다.
- 반복횟수는 "func(n) = func(n-1) + func(n-2)"로 계속 중복되는 하위 함수들이 반복되기 때문에 2^n이다.
3-4. 재귀적 팩토리얼 함수
=> 가장 비효율적인 수식
ex) 재귀적 팩토리얼 계산
#include <stdio.h>
// 재귀적으로 팩토리얼을 계산하는 함수
int factorial(int n) {
if (n == 0 || n == 1)
return 1;
return n * factorial(n - 1);
}
int main() {
int n = 5; // 계산할 팩토리얼의 값
printf("Factorial of %d is: %d\n", n, factorial(n));
return 0;
}- "팩토리얼 계산"이란 n!이라고 표기될 때 n부터 1사이에 모든 정수를 곱한 값을 의미한다.
- 해당 값을 계산하기 위해 매번 값을 나열 할 수 없기 때문에 반복문이나 재귀함수로 자동으로 처리한다.
- 재귀함수로 이루어진 알고리즘의 경우 계속되는 함수 호출로 인한 메모리 오버헤드 발생으로 인해 스택 오버플로우가 발생할 수 있다.
[가장 비효율적인 알고리즘]
1. 지수 시간 알고리즘
2. 재귀적 팩토리얼 시간 알고리즘
3. 다항 시간 안에 해결할 수 없는 NP-완전 문제
3-5. 재귀적 알고리즘 vs 반복적 알고리즘
[요약]
- 재귀적 알고리즘 : 문제의 자연스러운 표현을 제공하고 코드를 간결하게 만들어준다.
- 반복적 알고리즘 : 효율적인 실행속도와 메모리 관리를 제공한다.=> 재귀함수로 피보나치 수열, 팩토리얼 함수를 위에 예시로 들었다.
위에 함수들은 연산횟수면에서 비효율적이기 때문에 반복적 알고리즘으로 바꿀 필요가 있다.
ex) 반복적 팩토리얼을 계산하는 함수
#include <stdio.h>
// 반복적으로 팩토리얼을 계산하는 함수
int factorial_iterative(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}
int main() {
int n = 5;
printf("Factorial of %d is: %d\n", n, factorial_iterative(n));
return 0;
}
ex) 반복적 피보나치 수열을 계산하는 함수
#include <stdio.h>
// 반복적으로 피보나치 수열을 계산하는 함수
int fibonacci_iterative(int n) {
if (n <= 1)
return n;
int a = 0, b = 1, temp;
for (int i = 2; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return b;
}
int main() {
int n = 5;
printf("Fibonacci number at position %d is: %d\n", n, fibonacci_iterative(n));
return 0;
}
팩토리얼의 경우 반복문으로 변경했어도 큰 차이가 없어 보이지만
피보나치 수열의 경우 반복문으로 변경했을 경우 내부 연산이 추가된 것을 확인할 수 있다.
코드를 비교해봤을때 재귀적, 반복적 알고리즘마다 장단점이 존재하며 위와 같이 정리할 수 있다.
(재귀적 알고리즘을 사용해야하는 경우)
[고려야해할점]
1. 문제의 특성과 해결 방법에 대한 직관적 이해 - (1), (4)
2. 코드의 가독성 - (2)
3. 재귀호출의 안정성 - (3)
하지만 반복적 알고리즘이라고 다 좋은 것은 아니다.
상황에 따라서 재귀적 알고리즘이 더 좋은 경우가 있다.
(1) 문제의 재귀적 정의가 명확할 경우
문제 정의 자체가 재귀적으로 되어있어서 재귀적 알고리즘이 자연스럽고 직관적으로 표현될 수 있는 경우
ex) 트리구조탐색, 그래프 순회등
(2) 코드의 가독성이 중요한 경우
- 코드의 가독성을 높이고 유지보수를 용이하게 만들 수 있는 경우
- 문제의 본질을 더 잘 반영할 수 있어서 코드 이해하기 쉽게 만듦
(3) 재귀 호출의 깊이가 제한적인 경우
깊이를 제한하거나 입력크기를 제한할 경우 재귀적 알고리즘을 코드의 가독성을 높이고 보다 효율적으로 사용할 수 있다.
(4) 동적계획법에서의 재귀적 접근
문제를 재귀적으로 정의하고 하향식(top-down) 접근할 때가 있습니다.
이때 동적 계획법을 이용하여 부분적으로 해결가능합니다.
(재귀적 알고리즘의 사용 사례)
- 트리구조의 순회
- 분할정복 알고리즘(병합정렬)
- 백트래킹 알고리즘(N-Queens 문제해결)
- etc
=> 따라서 특정 문제에 대한 해결방식을 선택할 때 그 문제의 특성과 실행환경을 고려해야한다.
4. 점근적 표긱법: O표기
4-1. 정의를 알기 전 알아야할 사항
- 매번 시간복잡도를 상세히 정의하면 좋지만 코드가 클수록 오래걸린다.
- 또한 "N^2+3N+5"이 경우 N이 커질수록 N^2의 영향력이 커져서 3N,5의 값이 의미없게 된다.
- 코딩테스트는 연산회수를 측정하는 시험이 아니기에 대략적으로만 알면 된다.
- N^2+3N+5 ≈ N^2 이라고 생각해도 된다.
4-2. 점근적 표기법이란?
- 정확한 연산횟수가 아닌, <b>연산횟수의 추이</b>를 활용해 시간 복잡도를 표기
- 표시할 때 빅요 표기를 사용하는데
빅오 표기란 최악의 경우를 고려해서 점근적 표기법으로 나타내는 것을 말한다. - 시간 복잡도를 통해서 내가 작성한 알고리즘의 성능을 유추할 수 있다.
ex) N^2 + 3N + 5 => O(N^2)
빅오 표기법의 시간 복잡도
- 함수의 따른 시간 복잡도를 빅오표기법으로 표현한 그래프이다.
- 입력값이 커질 수록 각 함수의 영향력 차이가 어느정도인지 유추할 수 있다.
[코딩테스트에서의 활용법]
=> 입력값을 기준으로 가용한 자료구조 및 알고리즘을 고려가능하다.
ex) 입력값이 100만까지 가능
-> 만약 연산횟수가 N^M이라면 시간초과 / 연산횟수가 log N이면 Pass 로 예상할 수 있다.
4-3. 메서드의 시간 복잡도 파악
- 저장되는 메모리 공간의 특징이나 메서드에 따라서 시간 복잡도가 달라질 수 있다.
- 따라서 이 부분은 알고리즘의 성능을 좌지우지 할 수 있기 때문에 직접 코딩을 수행하고 분석하여 파악해두는게 좋다
ex)
- std::set vs std::unordered_set
- set::vector vs std::set
- std::map vs std::unordered_map
=> c++의 경우 일부 예시를 아래 링크에서 확인할 수 있다.
(https://github.com/dremdeveloper/codingtest_cpp/tree/main/performance)
참고링크
(1) https://www.desmos.com/calculator/ifg3mwmqun?lang=ko
=> 그래프 그려주는 사이트
=> 참고한 인프런 강의
(3) Book - 알고리즘 문제해결전략
(4) https://chatgpt.com/share/923ae9ae-3032-4814-a7cc-751e149a935a
=> 알고리즘 예시 chatgpt
(5) https://velog.io/@jacob3015/2022.04.13-BIG-O-표기법
=> 빅오표기법 비교 그래프
