티스토리 뷰
더보기
❗️이 글은 구종만 - 알고리즘 문제해결 전략 책을 참고하여 작성되었습니다.
📍 Algorithm vs Source Code
Algorithm: 주어진 문제를 해결하는 명료한 방법, 다른 언어로 쓰인 program도 같은 원리로 동작한다면 같은 알고리즘을 사용한다고 할 수 있다.
Source Code: 알고리즘을 구현하는 한 방법
=> Source Code가 Algorithm을 정의하는 것은 아니다.
📍 Algorithm을 평가하는 기준
- 시간 : 알고리즘이 빠르게 동작하는지
- 공간 : 알고리즘이 적은 용량의 메모리를 사용하는지
✔️ 시간 <=> 공간
- 메모리 사용량을 희생해 속도를 높이거나
- 속도를 희생해 메모리 사용량을 줄이거나
1. 알고리즘 속도 분석
두 알고리즘의 속도를 비교하기 위한 방법으로 두 프로그램의 수행시간을 비교하는 것을 생각해보자.
이 방법에는 다음과 같은 문제점이 있다.
- 프로그램의 수행 시간은 여러 요소(프로그래밍 언어, 하드웨어, 운영체제, 컴파일러)에 의해 바뀔 수 있다.
- 입력의 크기나 특성에 따라 수행시간이 달라질 수 있다.
📍반복문이 지배한다
입력의 크기에 따라 반복문이 알고리즘의 수행시간을 지배하는 정도가 달라진다.
만약 0~N까지 돌아가는 반복문이 있을 때,
- 반복문이 하나있는 코드라면 수행시간 N
- 중첩 반복문이면 수행시간 N^2
2. 선형 시간 알고리즘
📍다이어트 현황 파악: 이동 평균 계산하기
- 이동 평균: 시간에 따라 변화하는 값들을 관찰할 때 유용하게 사용할 수 있는 통계적 기준
- M-이동 평균은 마지막 M개의 관찰 값의 평균으로 정의
// 실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균 값을 구한다.
vector<double> movingAverage1(const vector<double> &A, int M) {
vector<double> ret;
int N = A.size();
for (int i = M - 1; i < N; ++i) {
// A[i]까지의 이동 평균평균을 구한다.
double partialSum = 0;
for (int j = 0; j < M; ++j)
partialSum += A[i - j];
ret.push_back(partialSum / M);
}
return ret;
}N개의 측정치가 주어질 때, 매달 M달 간의 이동 평균을 계산하는 프로그램
- j 사용하는 반복문 => M번 실행
- i 사용하는 반복문 => N-M+1번 실행
==> M*(N-M+1) = N*M-M^2+M
📍선형 시간에 이동평균 구하기
좀 더 빠른 프로그램을 만들기 위해 중복된 계산을 없애자!
- M-1일의 이동 평균과 M일의 이동평균에 포함되는 수 찾기
- 0일과 M일 몸무게 제외하면 모두 겹침
- M-1일에 구했던 몸무게의 합에서 0일째에 측정한 몸무게를 빼고 M일째 측정한 몸무게 더하기
// 길이가 N인 실수 배열 A가 주어질 때, 각 위치에서의 M-이동 평균 값을 구한다
vector<double> movingAverage2(const vector<double> &A, int M) {
vector<double> ret;
int N = A.size();
double partialSum = 0;
for (int i = 0; i < M - 1; ++i)
partialSum += A[i];
for (int i = M - 1; i < N; ++i) {
partialSum += A[i];
ret.push_back(partialSum / M);
partialSum -= A[i - M + 1];
}
return ret;
}하나로 묶여있던 반복문을 두 개로 분리
==> M-1 + (N-M+1) = N
수행시간은 N에 정비례 => 선형시간(linear time) 알고리즘
3. 선형 이하 시간 알고리즘
✏️ 선형 이하 시간 알고리즘
: 입력의 크기가 커지는 것보다 수행시간이 느리게 증가
📍성형 전 사진 찾기
연예인이 언제 성형했는지를 알고 싶은 경우, 사진이 10만장이 있다면 모두 확인할 것인가?
다음과 같은 방법으로 해결한다.
- 사진을 시간 순으로 정렬한다.
- 10만장의 사진을 절반으로 나눈다.(5만장)
- 성형 전 사진이라면 가운데(7만 5천번째)를 다시 절반으로 나눈다. (2.5만장)
- 성형한 시점을 찾을 때까지 반복
사진의 장수를 N이라고 한다면, N을 계속 절반으로 나눠 1 이하가 될 때까지 몇번이나 나눠야 하는가??
로그(log)를 사용하여 표현할 수 있다. (l o g 2 N)
==> 선형 이하 시간 알고리즘
📍이진 탐색
위와 같은 예제에서 사용한 알고리즘이 이진 탐색(binary search)이다.
binsearch(A[], x) -> 오름차순으로 정렬된 배열 A[]와 찾고 싶은 값 x가 주어질 떄,
A[i-1] < x <= A[i] 반환
🔎 성형 전 사진 문제
- 길이 N인 정수 배열 A[]일 때, 성형한 경우(1) / 성형하지 않은 경우(0)로 생각해보자.
- A는 {0,0, ... 0,0,1,1, ... ,1,1}과 같은 형태이고, A[i-1] < 1 <= A[i]으로 1의 첫 번째 위치를 찾을 수 있다.
- 결과적으로 i-1번 사진과 i번 사진 사이에 성형을 했다.
📍선형 시간이 아닌 이유
1. A[]를 실제로 계산하여 가질 필요 x
2. 사진을 다운받고 정렬하는 과정 ≠ 성형 전 사진 찾는 과정
4. 지수시간 알고리즘
📍 다항 시간 알고리즘
- 반복문의 수행횟수를 입력크기의 다항식으로 표현할 수 있는 알고리즘
- 변수 N과 N^2, 그 외 N의 거듭제곱들 => 다항 시간
📍알러지가 심한 친구들
만약 집들이에 N명의 친구들을 초대하는 경우,
M가지의 음식 중 친구들의 알러지를 피해 어떤 음식을 준비해야 할까?
📍모든 답 후보를 평가하기
위의 문제를 해결하기 위한 가장 단순한 방법으로 모든 답을 고려하는 것이 있다.
만들 수 있는 음식 목록에서 순서대로 탐색하며, 만들지 여부를 결정한다.
const int INF = 987654321;
// 이 메뉴로 모두가 식사할 수 있는지 여부를 반환한다.
bool canEverybodyEat(const vector<int> &menu) {
// 각 친구들이 주어진 메뉴를 먹을 수 있는지 여부를 담은 배열을 만든다.
vector<bool> edible(menu.size(), false);
for (int i = 0; i < edible.size(); ++i)
for (int j = 0; j < menu.size(); ++j)
if (menu[j] <= i + 1)
edible[i] = !edible[i - menu[j]];
return edible.back();
}
int M;
// food 번째 음식을 만들 지 여부를 결정
int selectMenu(vector<int> &menu, int food) {
// 기저 사례: 모든 음식에 대해 만들지 여부를 결정했을 때
if (food == menu.size()) {
if (canEverybodyEat(menu))
return menu.size();
return INF; // 아무것도 못 먹는 사람이 있는 경우
}
// 이 음식을 만들지 않을 경우
int ret = selectMenu(menu, food + 1);
// 이 음식을 만드는 경우의 답을 계산해서 더 작은 것을 취한다.
menu.push_back(food);
ret = min(ret, selectMenu(menu, food + 1));
menu.pop_back();
return ret;
}- M가지 음식마다 두 선택지(만든다, 안 만든다) => 2^M
- 답을 만들 때마다 canEverybodyEat() 수행 => 2^M * N * M
==> 지수 시간 알고리즘
📍지수 시간 알고리즘
- N이 하나 증가할 때마다 걸리는 시간이 배로 증가하는 알고리즘
- 입력의 크기에 따라 다항 시간보다 비교도 안 되게 수행시간 빠르게 증가
- 지수 시간을 다항 시간으로 바꾸지는 못한다.
📍소인수 분해의 수행 시간
입력되는 숫자의 개수가 아닌 크기에 따라 수행시간이 달라진다. => 지수 수행 시간
자연수 N이 주어질 때 N의 소인수 분해 결과를 반환하는 예제
// 자연수 n의 소인수 분해 결과를 담은 정수 배열을 반환한다
vector<int> factor(int n) {
if (n==1) return vector<int>(1, 1); // n=1인 경우 예외 처리
vector<int> ret;
// 가장 작은 소인수부터 시작해 한 번에 하나씩 추가한다
for (int div = 2; n > 1; ++div) {
while (n % div == 0) {
n /= div;
ret.push_back(div);
}
}
return ret;
}
- 입력의 개수와 수행시간 비례(이진탐색, 이동 평균 계산)
- 입력이 차지하는 비트 수에 따라 수행시간 증가(소인수 분해 문제)
- 비트 수가 하나 증가할 때마다 수의 범위와 수행시간 두 배로 증가
- 입력의 크기를 입력이 차지하는 비트 수로 정의
5. 시간 복잡도
📍시간 복잡도
- 기본적인 연산(더 쪼갤 수 없는 최소 크기 연산)의 수를 입력의 크기에 대한 함수로 표현
- 시간복잡도가 높다 => 입력의 크기가 증가할 때 수행시간 더 빠르게 증가
- 시간복잡도가 낮다 => 입력의 크기가 증가할 때 더 빠르게 동작
- 입력의 크기가 매우 작을 경우 시간복잡도 큰 의미 x
📍 입력의 종류에 따른 수행 시간의 변화
입력의 크기뿐만 아니라 입력의 종류에 따라 수행시간에 영향을 미친다.
ex) 배열에서 주어진 숫자를 찾아 그 위치를 반환하는 함수
// array[i] = element인 첫 i를 반환. 없으면 -1
int firstIndex(const vector<int> &array, int element) {
for (int i = 0; i < array.size(); ++i)
if (array[i] == element)
return i;
return -1;
}- 최선의 수행시간 : 찾으려는 원소가 배열의 맨 앞에 있는 경우 => 수행횟수 = 1
- 최악의 수행시간: 배열에 해당 원소가 없을 때, N번 반복 => 수행횟수 = N
- 평균적인 경우 수행 시간: 모든 입력의 등장 확률이 같다 => 수행횟수 = N/2
=> 많이 사용 (최악의 수행시간 or 수행시간 기대치)
📍점근적 시간 표기: O 표기
- 전체 수행시간에 큰 영향 주지 않은 상수부분 무시하고 반복문의 반복 수만 고려
- O 표기법: 주어진 함수에서 가장 빨리 증가하는 항만 남기고 다 버린다.
- 어느 한쪽이 빠르게 증가한다고 할 수 없는 경우 => 둘 다 O 표기
- 입력의 크기와 상관없이 항상 같은 시간 걸리는 경우 => O(상수), 상수 시간 알고리즘
📍O 표기법 의미
- 대략적으로 수행시간의 상한을 나타낸다.
- 각 경우의 수행시간을 간단히 나타내는 표기법일 뿐, 최악의 수행시간과 관련 없다.
- 퀵 정렬의 최고 차항 N^2으로 최악의 시간복잡도 O(N^2)
- 평균 수행 시간을 계산해보면 최고차항 NlgN으로, 평균 시간 복잡도 O(NlgN)
📍시간 복잡도 분석 연습
// 선택 정렬과 삽입 정렬
void selectionSort(vector<int> &A) {
for (int i = 0; i < A.size(); ++i) {
int minIndex = i;
for (int j = i + 1; j < A.size(); ++j)
if (A[j] < A[minIndex])
minIndex = j;
swap(A[i], A[minIndex]);
}
}
void insertionSort(vector<int> &A) {
for (int i = 0; i < A.size(); ++i) {
// A[0..i-1]에 A[i]를 끼워넣는다.
int j = i;
while (j > 0 && A[j - 1] > A[j]) {
swap(A[j - 1], A[j]);
j--;
}
}
}1️⃣ 선택 정렬
- O(N)번 실행되는 for문이 중첩되어 있어 => O(N^2)
2️⃣ 삽입 정렬
- 최선의 경우: 처음부터 이미 정렬된 배열이 주어지는 경우 => O(N)
- 최악의 경우: 역순으로 정렬된 배열이 주어지는 경우 => O(N^2)
=> 대부분의 경우 삽입 정렬이 선택 정렬보다 빠르다.
📍 시간 복잡도의 분할 상환 분석
시간 복잡도를 항상 반복문의 개수로 결정하지 않는다.
🔎 분할 상환 분석(amortized analysis)
- 문제의 조건에 따라 정확한 시간 복잡도 계산
- N개의 각 작업이 걸리는 시간은 모두 다르지만 전체 작업에 걸리는 시간이 일정한 경우
- 각 작업에 걸리는 평균 시간 = 전체 시간/작업 개수
6. 수행 시간 어림짐작하기
📍 주먹구구 법칙
- 입력의 최대 크기와 알고리즘의 시간 복잡도를 보고 수행 시간 짐작할 수 있어야 한다.
- 알고리즘의 시간복잡도에 따라 프로그램 속도 몇배가 빠르거나 느려질 수 있다.
- 주먹구구 법칙: 1초당 반복문 수행횟수 1억을 넘는다면 시간 제한 초과할 가능성이 있다.
- 예측한 수행횟수가 기준의 10%이하와 기준의 10배를 넘는 경우 적용 가능
📍주먹구구 법칙은 주먹구구일 뿐이다
주먹구구 법칙은 하나의 기준이지 늘 맞지는 않는다.
🔎 시간복잡도 외에 고려해야 할 요소
- 시간 복잡도가 프로그램의 실제 수행속도 반영하지 못하는 경우
- 시간 복잡도 식에 입력 최대 크기를 대입한 결과는 어디까지나 예측 값일 뿐이다.
- 반복문의 내부가 복잡한 경우
- 메모리 사용 패턴이 복잡한 경우
- 언어와 컴파일러의 차이
- 구형 컴퓨터를 사용하는 경우
📍 실제 적용해 보기
1차원 배열에서 연속된 부분 구간 중 그 합이 최대인 구간을 찾는 문제를 이해해보자.
각 알고리즘에 따라 수행시간이 어떻게 다를까?
1️⃣ 배열 모든 구간 순회
// 최대 연속 부분 구간 합 문제를 푸는 무식한 알고리즘들
const int MIN = numeric_limits<int>::min();
// A[]의 연속된 부분 구간의 최대 합을 구한다
int inefficientMaxSum(const vector<int> &A) {
int N = A.size(), ret = MIN;
for (int i = 0; i < N; ++i)
for (int j = i; j < N; ++j) {
// 구간 A[i..j]의 합을 구한다
int sum = 0;
for (int k = i; k <= j; ++k)
sum += A[k];
ret = max(ret, sum);
}
return ret;
}
// A[]의 연속된 부분 구간의 최대 합을 구한다
int betterMaxSum(const vector<int> &A) {
int N = A.size(), ret = MIN;
for (int i = 0; i < N; ++i) {
int sum = 0;
for (int j = i; j < N; ++j) {
sum += A[j];
ret = max(ret, sum);
}
}
return ret;
}- inefficientMaxSum()은 모든 구간을 탐색=> 시간복잡도 = O(N^3)
- betterMaxSum()은 중복 구간을 탐색 => 시간복잡도 = O(N^2)
2️⃣ 분할 정복 기법
// 최대 연속 부분 구간 합 문제를 푸는 분할 정복 알고리즘
const int MIN = numeric_limits<int>::min();
// A[lo..hi]의 연속된 부분 구간의 최대합을 구한다. (분할 정복)
int fastMaxSum(const vector<int> &A, int lo, int hi) {
// 기저 사례: 구간의 길이가 1일 경우
if (lo == hi)
return A[lo];
// 배열을 A[lo..mid], A[mid+1..hi]의 두 조각으로 나눈다
int mid = (lo + hi) / 2;
// 두 부분에 모두 걸쳐 있는 최대 합 구간을 찾는다. 이 구간은
// A[i..mid]와 A[mid+1..j] 형태를 갖는 구간의 합으로 이루어진다
int left = MIN, right = MIN, sum = 0;
for (int i = mid; i >= lo; --i) {
sum += A[i];
left = max(left, sum);
}
sum = 0;
for (int j = mid + 1; j <= hi; ++j) {
sum += A[j];
right = max(right, sum);
}
// 최대 합 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출을
// 이용해 찾는다
int single = max(fastMaxSum(A, lo, mid), fastMaxSum(A, mid + 1, hi));
// 두 경우 중 최대치를 반환한다
return max(left + right, single);
}- 입력받은 배열을 절반으로 잘라 왼쪽/오른쪽으로 나눈다.
- 각 경우의 답을 재귀 호출과 탐욕법을 이용해 계산
- 시간 복잡도 = O(NlgN)
3️⃣ 동적 계획법
// 최대 연속 부분 구간 합 문제를 푸는 동적 계획법 알고리즘
const int MIN = numeric_limits<int>::min();
// A[]]의 연속된 부분 구간의 최대 합을 구한다
int fastestMaxSum(const vector<int> &A) {
int N = A.size(), ret = MIN, psum = 0;
for (int i = 0; i < N; ++i) {
psum = max(psum, 0) + A[i];
ret = max(psum, ret);
}
return ret;
}- 점화식 : maxAt(i) = max(0, maxAt(i-1)) + A[i]
- 하나의 반복문을 가져 시간 복잡도 = O(N)
📍 알고리즘 수행 시간 비교
- N = 1,000
- O(N^3)은 10억으로 주먹구구 법칙의 기준을 넘어 주의 필요
- N = 10,000
- O(N^3)은 불가능, O(N^2)은 1억 정도로 주의필요
- N = 100,000
- O(N^3)과 O(N^2) 불가능, O(NlgN)은 2천만 정도로 시간 안에 수월하게 동작
=> 주먹구구 법칙으로 예측한 것보다 느리게 동작하는 프로그램은 없다.
주먹구구 법칙의 기준보다 느리지만 시간 안에 수행되는 알고리즘도 있고 기준보다 빠르지만 시간 안에 수행되지 않는 프로그램도 있다.
'알고리즘' 카테고리의 다른 글
| [Algorithm Strategy] - 6. 무식하게 풀기 (1) | 2023.07.31 |
|---|---|
| [Algorithm Strategy] - 5. 알고리즘의 정당성 증명 (0) | 2023.07.25 |
| [Algorithm strategy] - 3장 코딩과 디버깅에 관하여 (0) | 2023.07.04 |
| [Algorithm strategy] - 2장 문제 해결 개관 (0) | 2023.07.03 |
| [Algorithm] - Dynamic Programming 알고리즘 (0) | 2023.05.01 |