다이어트 현황 파악: 이동 평균 계산하기
//실수 배열 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);
//push_back: vector의 메소드로 마지막에 원소 추가
}
return ret;
}
//길이가 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;
}
선형 이하 시간 알고리즘 - 이진 탐색
입력의 크기가 커지는 것보다 수행 시간이 느리게 증가하는 알고리즘들을 선형 이하 시간 알고리즘이라 부른다.
지수 시간 알고리즘 - 다항 시간 알고리즘 - 재귀 함수
음식 메뉴 정하기
const int INF = 987654321;
// 이 메뉴로 모두가 식사할 수 있는지 여부를 반환한다.
bool canEverybodyEat(const vector<int>& menu);
// 요리할 수 있는 음식의 종류 수
int M;
//food번째 음식을 만들지 여부를 결정한다.
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, selctMenu(menu, food+1));
menu.pop_back();
return ret;
}
지수 시간 알고리즘
소인수 분해의 수행 시간
//자연수 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;
}
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[minIndex] > A[j])
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;
}
}
}
const int MIN = numeric_limits<int>::min();
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(N^3)
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[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: 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) {
//구간 A[i, j]의 합을 구한다.
sum += A[j];
ret = max(ret, sum);
}
}
return ret;
}
//A[lo, hi]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(nlogn)
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] 형태를 갖는 구간의 합으로 이루어진다.
//A[i, mid] 형태를 갖는 최대 구간을 찾는다.
int left = MIN, right = MIN, sum = 0;
for(int i = mid, i >= lo; --i){
sum += A[i];
left = max(left, sum);
}
//A[mid+1, j] 형태를 갖는 최대 구간을 찾는다.
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);
}
//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도: O(N)
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;
}
P : 다항 시간 내에 풀 수 있는 문제
NP : 다한 시간 내에 풀 수 없는 문제
알고리즘의 정당성 증명 - 수학적으로 증명
수학적 귀납법
단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눈다.
첫 단계 증명 : 첫 단계에서 증명하고 싶은 내용이 성립한다.
귀납 증명 : 한 단계에서 증명하고 싶은 내용이 성립한다면 다음 단계에서도 성립함을 보임
반복문 불변식
//(*) 불변식은 여기에서 성립해야 한다.
while(condition) {
//반복문 내용의 시작
..
//반복문 내용의 끝
//(**) 불변식은 여기에서도 성립해야 한다.
}
이진 탐색과 반복문 불변식
// 필수 조건: A는 오름차순으로 정렬되어 있다.
// 결과: A[i-1] < x <= A[i]인 i를 반환한다.
// 이때 A[-1] = 음의 무한대, A[n] = 양의 무한대라고 가정한다.
int binsearch(const vector<int>& A, int x) {
int n = A.size();
int lo = -1, hi = n;
//반복문 불변식 1: lo < hidden
//반복문 불변식 2: A[lo] < x < A[hi]
//(*) 불변식은 여기서 성립해야 한다.
while(lo + 1 < hi) {
int mid = (lo + hi) / 2;
if(A[mid] < x)
lo = mid;
else
hi = mid;
//(**) 불변식은 여기서 성립해야 한다.
}
}
삽입 정렬과 반복문 불변식
void insertionSort(vector<int> A) {
for(int i = 0; i < A.size(); ++i) {
// 불변식 a:A[0..i-1]은 이미 정렬되어 있다.
// A[0..i-1]에 A[i]를 끼워넣는다.
int j = i;
while(j > 0 && A[j-1] > A[j]) {
// 불변식 b: A[j + 1 .. i]의 모든 원소는 A[j]보다 크다.
// 불변식 c: A[0 .. i] 구간은 A[j]를 제외하면 정렬되어 있다.
swap(A[j-1], A[j]);
--j;
}
}
}
귀류법
내가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법
비둘기집의 원리
동전 뒤집기
순환 소수 찾기
구성적 증명
안정적 결혼 문제
