4.1 도입
반복문이 시간복잡도를 지배한다.
알고리즘 수행시간은 반복문이 수행되는 횟수로 측정한다.
-> 이유 : 입력의 크기가 커짐에 따라 수행 시간도 상승
예제 1 ) 주어진 배열에서 가장 많이 등장하는 수를 찾기 (수행 시간 n^2)
int majority1(const vector<int> &A)
{
int n = A.size();
int majority = -1, majorityCount = 0;
for(int i=0; i<n; i++)
{
int v = A[i], count = 0;
for(int j = 0; j<n; j++)
{
if(A[j] == v) ++count;
}
if(count > majorityCount)
{
majorityCount = count;
majority = v;
}
}
return majority;
}위와 같은 코드가 있을때
첫번째 반복문에서는 총 n번을 수행한다.
두번째 반복문에서도 총 n번을 수행한다.
총 수행량은 중첩 반복문이기 때문에 n*n번 수행하고 수행시간은 n^2이 된다.
예제2) n^2의 수행시간 n으로 변경하는 코드
int majority2(const vector<int> &A)
{
int n = A.size();
vector<int>count(101, 0);
for(int i=0; i<n; i++)
{
count[A[i]]++;
}
int majority = 0;
for(int i = 1; i<=100; i++)
{
if(count[i] > count[majority])
{
majority = i;
}
}
return majority;
}이 코드의 경우
첫번째 반복문은 총 n번 수행
두번째 반복문은 100번 수행한다.
총 수행량은 n+100번이고 수행시간은 n+100이 된다.
4.2 선형 시간 알고리즘
선형 시간 알고리즘이란?
함수의 총 수행량이 선형으로 증가하는 알고리즘을 의미한다
이동평균을 계산하는 예제를 살펴보기전에 이동평균의 개념을 정리 해보자
| 날짜 | 0 | 1 | 2 | 3 | 4 | M-1 | M | M+1 |
| 몸무게 | 3.5 | 3.5 | 3.5 | 3.6 | 3.5 | 80.2 | 80.1 | 80.3 |
날짜 별로 측정한 몸무게가 있다.
이동 평균이라는 것은 날짜 M이 될때까지의 몸무게를 합산 해 M날짜에 도달 했을때
합산한 총 몸무게 / 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++)
{
double partialsum = 0;
for(int j = 0; j<M; j++)
{
partialsum += A[i-j];
}
ret.push_back(partialsum / M);
}
return ret;
}이 코드의 경우 모든 이동 평균값을 다 탐색하여 값을 저장한다.
하나씩 해석해보면
M이 3이라고 해보자(3일마다 측정한다는 의미)
첫번째 이동 평균의 경우 i = 2일날의 이동 평균을 구한다는 의미가 된다
아래 중첩 반복문에 의해 A[2-0] + A[2-1] + A[2-2] / M 으로 이동 평균이 구해진다.
두번째 이동 평균의 경우 i = 3이되고 즉 3일날 이동평균 값을 구해야 하므로
A[3-0] + A[3-1] + A[3-2] / M 이 된다.
총 수행을 계산하면 (N-M+1) * M이 되고 수행시간은 NM - M^2 + M이 된다
위 코드는 테스트케이스 1개의 실행제한시간이 1초이고 N이 10만개가 들어오면 시간초과가 된다
좀 더 빠른 코드를 만들기 위해서는 중복된 계산을 줄여야한다.
중복된 계산을 줄이는 방법은
M-1번까지의 부분합을 구한 상태에서 M 번째 합을 더해주고 이동평균을 구하고 첫번째 몸무게를 빼준다
이 방법을 반복하면 M+1, M+2 값을 구할 수 있게 되고 모든 이동평균을 구할 수 있다
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번 수행하므로 (M-1)+(N-M+1) = N이 되므로 총 N번 수행하는 코드로
개선 가능하다.
4.3 선형 이하 시간 알고리즘
선형 이하 시간 알고리즘은 보통 log 형태의 수행하는 알고리즘을 의미한다.
예제1) 성형전 사진 찾기
성형한 A군이 있고 A군의 성형전 사진을 찾는 알고리즘을 개발한다고 하자
1. A군의 사진이 10만장 존재하는 상태(사진은 찍은 날짜 순으로 오름차순 정렬된 상태)
2. 가장 처음 성형한 시기의 사진을 찾자
| 확인한 사진수 | 0 | 1 | 2 | ... | 9 | 10 | ... | 16 |
| 남은 사진 | 100,000 | 50,000 | 25,000 | ... | 195 | 97 | ... | 1 |
오름차순으로 정렬된 상태에서 첫번째 탐색에서 남은사진/2 번째의 사진으로 이동한다.
만약 해당 사진이 성형전 사진이 아니면 볼 필요가 없기 때문에 또 절반씩 줄여 나간다
이렇게 줄여나가다보면 총 16번만에 가장 처음 성형한 시기의 사진을 찾을 수 있다.
이런 케이스를 선형 이하 시간 알고리즘이라 한다.
위 알고리즘은 BinarySearch 탐색이다.
4.4 지수 시간 알고리즘
다항시간 알고리즘
다항식으로 표현가능한 시간을 다항시간 알고리즘이라 한다.
예제) 알러지가 심한 친구들
1. 집들이에 N명의 친구를 초대하려 한다.
2. 할줄 아는 음식 M가지 중에 무엇을 대접해야할까 고민한다.
3. 친구들은 각각 알러지 때문에 못먹는 음식들이 있어서 아무거나 대접할 수 없다
4. 각 친구들이 먹을 수 있는 음식이 한가지 이상 있으려면 최소 몇가지 음식을 해야할까?
| 갈비찜 | 피자 | 잡채 | 떡볶이 | 탕수육 | |
| 페이 | x | o | o | o | x |
| 지아 | x | x | x | x | o |
| 민 | o | x | o | x | o |
| 수지 | o | o | x | x | x |
모든 답 후보 평가하기
가장 좋은 답을 찾는 문제들을 풀때 가장 간단한 방법은 모든 답을 고려하여 풀면 된다
모든 답을 고려하는 방법을 완전 탐색이라고 하는데
이 경우는 모든 음식에 대해서 만들지 말지 결정하여 최소 음식을 구하는 방법으로 접근할 수 있다.
이 트리 구조가 나타내는 의미는 가장 최상위 노드(-)는 아무것도 선택안한 상태를 나타낸다
다음 층에서 갈비찜을 선택할 것인가?
선택한다면 갈비찜은 추가 되고, 선택하지 않는다면 아무것도 선택 안한 상태가 된다
이 다음 층에서 피자를 선택할 것인가?
피자를 선택하면 갈,피가 되고 선택하지 않으면 갈만 남는다.
아무것도 선택 안한 노드에서는 피자를 선택하게 되면 피자가 추가 되고, 선택하지 않는다면 -가 된다
이렇게 모든 음식에 대해서 탐색을 다 하게 되고, 선택한 음식 중 알러지가 아무도 없는 경우가 최소 음식 선택한 경우가 된다.
코드로 구현하자면 아래와 같다.
const int INF = 987654321;
bool alerge[1000][1000];
bool CanEveryBodyEat(const vector<int>& memu)
{
for(int i=0;i<menu.size(); i++)
{
for(int j=0; j<n; j++)
{
if(alerge[j][menu[i]] == true) return false;
}
}
return true;
}
int SelectMenu(vector<int>&menu, int food)
{
if(food == M)
{
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 menu;
}이 코드의 총 수행시간을 계산하면 메뉴를 선택하는것은
2^m * n*menu.size() 이 된다 그 이유는 각 메뉴를 선택할지 말지 결정하는것과 선택하고 CanEveryBodyEat 함수를 실행하기 때문이다.
4.5 시간 복잡도
알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것
시간복잡도가 낮은 알고리즘은 입력이 커질수록 더 효율적
예시) 같은일을 하는 알고리즘 A와 B가 있다
A의 시간복잡도는 10240 + 35logN
B의 시간복잡도는 2N^2이다
A의 알고리즘은 선형시간 이하 알고리즘이고 B는 선형시간 알고리즘이다.
입력 종류에 따른 수행시간 변화
입력 크기가 수행 시간을 결정하는 유일한 척도는 아니다
입력이 어떤 형태로 구성되어 있는지도 수행시간에 영향을 미친다
예시) 찾고자 하는 원소 Index 반환
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번만에 찾을 수 있다
찾고자하는 값이 배열의 가장 첫번째 위치면 최상의 경우로 1번의 수행만에 찾을 수 있다
하지만 찾고자하는 값이 배열의 마지막에 위치한다면 최악의 경우로 찾고 n번 수행해야한다.
최악과 최상의 중간인 평균 시간 복잡도는 n/2이 된다
보통 알고리즘 시간 복잡도를 측정할때 최상의 경우는 배제하고 최악의 경우나 평균 시간 복잡도를 주로 사용한다
점근적 시간 표기 : O표기
Big O표기법 : 주어진 함수에서 가장 빨리 증가하는 항을 제외하고 나머지는 버리는 표기법
예시) f(N) = 2/3N^2 - NlogN/2 + 16N - 7 이라는 함수가 존재한다고 하자
이 함수에서 가장 빨리 증가하는 항은 2/3N^2이 된다
그 다음 상수값을 제거하게 되면 O(N^2)으로 표기 할 수 있다
2^n * M = O(2^n * M)
1/64N^2*M + 64NM = O(N^2*M)
N^2*M + NlogM + NM^2 = O(N^2*M+N*M^2) -> 이 케이스의 경우 N이 빨리 증가할지 M이 빨리 증가할지 모른다.
42 = O(1)
O표기법의 의미
함수의 상한을 나타낸다
f(N) = O(g(N))
아주 큰 N0와 C(N0, C>0)을 적절히 선택하면 N0<=N인 모든 N에 대해 |f(N)| <= C*|g(N)|이 참이 되도록 할 수 있다
예시) N^2 + 100 * N + 1 = O(N^2)
N이 아주 커지면 N^2과 N^2 + 100 + N + 1 이랑 큰 차이가 없다
이때 적절한 상수 C를 N^2에 곱하면 C*N^2 >= N^2 + 100 + N + 1 을 만족한다
*O표기법은 수행시간의 최악을 나타내는것은 아니다 그 이유는 퀵소트의 경우 최악의 수행시간은 N^2이지만 평균 NlogN이고
퀵소트의 시간복잡도는 O(NlogN)이기 때문이다.
시간 복잡도 분석 연습
예제) 선택정렬, 삽입 정렬
void SelectionSort(vector<int>&A)
{
for(int i=0; i<A.size(); i++)
{
int minIndex = i;
for(int j=0; j<A.size(); j++)
{
if(A[minIndex] > A[j])
{
minIndex = j;
}
}
swap(A[i], A[minIndex]);
}
}
void InsertionSort(vector<int>&A)
{
for(int i =0; i<A.size(); i++)
{
int j = i;
while(j>0 && A[i-1] > A[j])
{
swap(A[i-1], A[j]);
j--;
}
}
}선택 정렬과 삽입 정렬의 경우 O(N^2)의 시간복잡도를 가진다
그러나 삽입 정렬의 경우 정렬 된 상태이면 while문은 즉시 종료하여 O(1)이 된다
하지만 역순으로 정렬 되어 있는 경우 while문은 O(N)이 되고 최종적으로 O(N^2)이 된다
O(N^2) 정렬 중 가장 빠른것은 삽입 정렬이다.
4.6 수행시간 어림짐작하기
시간복잡도와 입력 크기로 대략 짐작 가능하다
입력이 최대 크기가 10000이고 테스트케이스 하나 푸는데 제한이 1초 인 경우
O(N^3), O(N^2), O(NlogN)으로 풀 수 있을까?
1초에 1억을 넘어가면 제한 시간 초과 가능성이 있다
O(N^3) = 10^12
O(N^2) = 10^8
O(NlogN)= 10^4 * 4
이중 통과 가능한것은 NlogN이다
N^2의 경우 될 수도 있고 안될수도 있다.
N^3의 경우 명백한 시간 초과다
실제 적용해보기
예제) 1차원 배열에서 연속된 부분 구간 합 중 합이 최대인것은?
[-7, 4, -3, -8, 3, 4] 에서 최대 합 구간은 [4, -3, 6, 3]으로 합이 10이다
case 1) O(N^3) 방법
const int Min = numeric_limits<int>::min();
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++)
{
int sum = 0;
for(int k = i; j<=j; k++)
{
sum += A[k]
}
ret = max(ret, sum);
}
}
return ret;
}
case2) O(N^2) 방법
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;
}
case3) O(NlogN) 분할 정복 방법
int fastMaxSum(const vector<int>&A, int lo, int hi)
{
if(lo == hi) return A[lo];
int mid = (lo + hi)/2;
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);
}
case4) O(N) DP 방법
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;
}'Algorithm > JongMan' 카테고리의 다른 글
| [알고리즘 문제해결 전략] 6장 무식하게 풀기 (0) | 2019.12.08 |
|---|---|
| [알고리즘 문제해결 전략] 5장 알고리즘 정당성 증명 (0) | 2019.12.08 |
