[삼성 알고리즘] 분할 상환 알고리즘

알고리즘 복잡도 계산에 있어 빅오는 최악의 경우를 바탕으로 이루어진다. 이로 인해 문제가 발생하는데 바로 O(1)의 알고리즘을 지속적으로 가지다가 100 번에 1번정도만 O(n)을 가진다면..? 이 때도 빅오 표기법과 같이 O(n)으로 실행하는 것이 맞는가 이다.

 

즉 평소에는 빠른 알고리즘이나 정말 가끔 발생하는 최악의 경우로 인해 상대적으로 실제 가치보다 저평가되는 알고리즘들을 위한 표기법이 바로

분할 상황 분석을 통해 구제하는 것이다.

 

분할 상환 분석은 Amoritized Analysis라고 하며 해당 알고리즘으로 비용을 계산하는 방법은 아래와 같다.

최악의 경우에 드는 비용을 최악의 경우가 발생하는 횟수로 나누어 계산한다.

 

예를 들어 N번에 한 번 최악의 경우 O(N)이 나오는 알고리즘의 경우

빅오 표기로는 O(N)

분할 상환 분석으로는 Amoritized O(1)이 된다.

 

결과적으로 수학적으로 N번의 횟수를 진행할 때 발생하는 모든 COST를 N으로 나누면 분할 상황 분석이다.

 

ref)

https://8iggy.tistory.com/25

 

1. 두 포인터 기법

투 포인터 기법은 1차원 배열에 있어 부분합의 값을 구할 때 사용하는 기법으로 두 개의 포인터를 바탕으로 빠른 시간에 해당 문제를 해결할 수 있도록하는 알고리즘이다. 두 개의 포인터를 사용하는 알고리즘으로는 이외에도 플로이드-Tortoise and Hare 알고리즘 등과 같은 알고리즘이 존재한다.

아마 두 개의 포인터를 활용하면 이외에도 다양한 알고리즘 풀이 과정에서 좋은 효율을 만들 수 있을 것 같다.

 

1) 원리

부분합으로 구하고자 하는 값을 X라고 하자. 두개의 포인터를 만들고 두 개의 포인터로 만든 부분집합에 포함되는 값들의 합이 X가 되도록 구한다.

• 만들어진 부분집합의 합을 A라고했을 때 A<X인 경우 우측 커서를 한칸 씩 이동
• A>X가 되는 경우 좌측 커서를 이동
• A=X가되면 해당 부분집합 발견

2) 소스 코드(백준 - 소수의 연속합)

#include<iostream>

#include<cmath>

#include<vector>

 

using namespace std;

bool flags[4000001] = { false, };

int main(void) {

int N,count=0;

vector<int> prime_num;

cin >> N;

 

flags[0] = true;

flags[1] = true;

 

//Sieve of Eratosthenes(To get prime number)

for (int i = 2; i <= (int)sqrt(N); i++) {

bool flag = true;

for (int j = 2; j <= (int)sqrt(i); j++) {

if (i%j == 0) {

flag = false;

break;

}

}

if (flag) {

for (int k = i*i; k <= N; k += i) {

flags[k] = true;;

}

}

else {

flags[i] = true;

}

}

for (int k = 2; k < 4000001; k++) {

if (flags[k] == false) {

prime_num.push_back(k);

}

}

 

//Two Pointer Algorithm

int p = 0,q=0;

while (q<prime_num.size()) {

int sum = 0;

for (int i = p; i <= q; i++) {

sum += prime_num.at(i);

}

if (sum < N) {

q += 1;

} else if (sum > N) {

p+=1;

} else {

count += 1;

p += 1;

q += 1;

}

}

cout << count << endl;

return 0;

}

 

3) 에라토스테네스의 체

에라토스테네스의 체는 2) 소스코드에서 백준 문제를 풀이하는데 사용한 알고리즘 입니다.

해당 알고리즘은 소수를 구하는 알고리즘으로 좋은 효율성을 보여줍니다. 기존의 소수를 구하는 알고리즘은 특정 숫자 N에 대해서 2부터 N까지 %를 통해 나누어지는지 확인하는 기본적인 방법 혹은 루트를 활용하여 2부터 √N 까지만 %를 통해 나누어지는지 확인하여 소수인지 판별할 수 있었습니다.

 

여기서 특정 범위내 숫자에 한해 소수는 어떤 숫자인지 구하기 위해서는

위의 루트를 활용한 소수인지 판별 알고리즘은 범위내 모든 숫자에 진행해야하는 비효율성이 존재했는데 에라토스테네스의 체는 이러한 문제점을 해결합니다.

 

기본적으로 에라토스테네스의 체는 1부터 N까지의 특정 숫자가 있을 때 1부터 √N까지의 소수를 기존의 방법을 통해 구하고 이후 √N에서 N까지의 숫자 범위에서는 1부터 √N사이에 존재하는 소수의 배수가 아닌 숫자면 모두 소수임을 이용하여 소수들을 구하는 알고리즘입니다.

 

코드에 적용하면..( 2)의 소스 코드에도 코드로 작성되어 있음)

• 가장 먼저 1을 제외한 모든 수가 소수라고 bool대수 배열을 통해 선언
• 1부터 √N까지 범위에 한해서 소수 판별을 진행하고 소수가 아닌 숫자는 소수가 아닌 표시를 bool 배열에 합니다.
• 동시에 1부터√N까지 범위 소수를 발견할 때마다 N이하인 해당 수의 배수를 찾아 소수가 아님을 bool 배열에 표시 합니다.
• 1부터 N까지 bool 배열을 순회하면서 소수인 숫자들을 찾을 수 있습니다.

 

2. 2SUM 문제

해당 문제는 목표합 x에대해 합이 x가되는 배열 원소 두개를 구하거나 그러한 원소조합이 존재하지 않음을 찾는 알고리즘 입니다.

 

1) 원리

• 가장 먼저 오름차순으로 정렬을 진행 합니다.
• 왼쪽 포인터는 가장 왼쪽, 우측 포인터는 가장 우측에서 시작합니다.
• 우측 포인터는 좌측 포인터와의 합이 x이하가 될때 까지 왼쪽으로 이동합니다.(x가딱 되면 해당 원소조합 발견)
• 우측 포인터 이동 후 좌측 포인터를 우측으로 이동하며 위 과정을 반복합니다.

(우측 포인터와 좌측 포인터가 만날 때까지 찾지 못하면 해당 원소 조합은 존재하지 않음을 알 수 있습니다.)

 

 

3. 기타 포인터를 활용한 알고리즘

두 개의 포인터를 활용한 알고리즘은 위 투 포인터, 2SUM문제 뿐 아니라 활용도에 따라서(약간의 변형을 통해)

플로이드-Tortoise and Hare 알고리즘, 슬라이딩 윈도의 최솟값 구하기, 보다 작으면서 가장 가까운 원소 구하기 등

여러 가지 알고리즘을 해결하는데 도움이 될 수 있습니다.