[알고리즘] 3. Decrease and Conquer 내용 정리

1. Brute force

2. Divide and conquer
3. Decrease and conquer
4. Transform and conquer
5. Greedy Method
6. Dynamic Programming
7. Backtracking
8. Branch and Bound

여기서는 Decrease and conquer에 대해 다룬다.

---

Decrease and Conquer란

주어진 문제를 같지만 계산을 작게 만들어서 해결하는 방식이다. 분할정복과의 차이는, 분할정복은 작게 쪼갠 후 다시 통합하는 과정이 있지만, Decrease는 작게 쪼개서 없애버린 부분을 다시 합치지 않는다는 차이가 있다. 그래서 여기서는 '통합' 대신 '확장'이라는 말을 쓴다. Greedy나  DP처럼 특정 알고리즘이라기보다는 정의역을 줄인다면 넓은 의미에서 Decrease and Conquer로 해석될 수 있다.   

 

---

Decrease and Conquer 예시

• Decrease by one(한개씩 줄여나감)
  • Insertion sort
  • DFS
  • BFS
  • Topological sort
• Decrease by constant factor(주어진 상수만큼 줄여나감)
  • Binary search
  • Fake-coin problems
  • Multiplication à la russe
  • Josephus problem
• Variable-size decrease (줄어드는 양이 정해져 있지 않음)
  • Euclid's algorithm
  • Selection by partition
  • Interpoolation search

---

Insertion Sort

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

void insertionSort(int arr[],int length){
    for (int i = 1; i < length; i++) {  // 배열 길이에 맞춰 반복
        int key = arr[i];  // 삽입할 원소
        int j = i - 1;

        // 정렬된 부분에서 key가 들어갈 위치를 찾기 위한 루프
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];  // 원소를 오른쪽으로 한 칸 이동
            j--;
        }
        arr[j + 1] = key;  // key를 적절한 위치에 삽입
    }
    for(int i=0; i<length; i++){
        printf("%d, ",arr[i]);
    }
    
}


int main() {
    int dataset[]={83, 17, 19, 34, 29, 52, 45, 97, 15, 22, 6, 16, 31, 31, 88, 12, 16, 15, 48, 74, 26, 67, 73, 18, 1, 29, 98, 8, 97, 47, 78, 51, 81, 53, 98, 25, 95, 27, 29, 17, 8, 66, 40, 27, 58, 14, 37, 67, 63, 35, 20, 54, 38, 78, 71, 55, 25, 53, 80, 59, 6, 35, 98, 14, 48, 39, 18, 33, 16, 55, 30, 94, 84, 99, 88, 59, 26, 22, 53, 99, 72, 55, 71, 76, 76, 12, 79, 1, 33, 87, 26, 63, 52, 42, 28, 61, 59, 8, 3, 60, 99, 54, 36, 93, 59, 46, 77, 9, 81, 66, 53, 42, 43, 79, 64, 43, 1, 16, 77, 42, 94, 44, 46, 1, 8, 97, 93, 70, 94, 9, 94, 62, 26, 10, 34, 53, 11, 83, 68, 27, 43, 45, 72, 94, 78, 98, 95, 40, 11, 72, 4, 94, 18, 47, 16, 77, 34, 12, 60, 14, 60, 17, 77, 21, 75, 85, 87, 73, 65, 49, 87, 98, 48, 22, 26, 21, 22, 94, 90, 75, 63, 22, 33, 74, 12, 82, 62, 26, 14, 12, 29, 25, 65, 95, 27, 69, 59, 76, 74, 77, 17, 100, 92, 38, 19, 2, 44, 5, 83, 38, 42, 77, 13, 23, 61, 64, 54, 17, 79, 82, 42, 52, 57, 30, 12, 100, 65, 80, 81, 61, 13, 19, 68, 33, 88, 77, 48, 48, 48, 55, 39, 26, 61, 66, 96, 89, 15, 20, 16, 71, 82, 62, 98, 6, 14, 92, 4, 43, 12, 3, 80, 15, 35, 16, 50, 34, 58, 42, 22, 30, 24, 29, 9, 66, 10, 60, 48, 90, 66, 71, 34, 2, 46, 63, 12, 71, 10, 47, 59, 52, 41, 77, 8, 72, 83, 46, 43, 97, 91};
    insertionSort(dataset,sizeof(dataset)/sizeof(*dataset));
    return 0;
}

• 삽입 정렬이다. 앞에서 2번째부터 정렬된 부분과 비교해서 올바른 자리로 찾아 넣는 방식이다. 
• 우리가 일반적으로 카드를 정렬할때 쓰는 방식이다.
• 한 개씩 처리해야 하는 문제를 줄여나가니 Decrease by One 방식이라고 할 수 있다.

---

DFS, BFS

#include <iostream>
#include <queue>
#include <vector>
#define sizes 10
using namespace std;



int graph[sizes][sizes] = {
    {0, 1, 0, 1, 1, 0, 0, 0, 0, 0},
    {1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
    {0, 1, 0, 1, 0, 0, 0, 0, 0, 0},
    {1, 0, 1, 0, 0, 0, 0, 0, 0, 0},
    {1, 0, 0, 0, 0, 1, 0, 0, 0, 0},
    {0, 0, 0, 0, 1, 0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 0, 1, 0, 1, 0},
    {0, 0, 0, 0, 0, 1, 0, 1, 0, 1},
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}
};

int checked[sizes]={0};
int checked2[sizes]={0};

void DFS(int pos){
    if(checked[pos]){
        return;
    }
    checked[pos]=1;
    printf("%d ",pos+1);
    for(int i=0; i<sizes; i++){
        if(graph[i][pos]){
            DFS(i);
        }
    }

}

queue<int> q;

void BFS(int pos){
    q.push(pos); //처음 케이스 처리
    checked2[pos] =1;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        printf("%d ",current+1);
        for (int i = 0; i < sizes; i++) {
            if (graph[current][i] == 1 && !checked2[i]) {
                q.push(i);
                checked2[i] = true;  
            }
        }
    }

}

int main() {
    printf("DFS: ");
    DFS(0);
    printf("\n");
    printf("BFS: ");
    BFS(0);


    return 0;
}

• 그래프를 순회하며 하나씩 처리해 나가는 DFS, BFS 역시 decrease by one 방식이라고 할 수 있다.
• DFS는 재귀함수를 이용하고, BFS는 큐를 이용한다. 그리고 둘 모두 이미 방문했는지 확인하는 배열이 공통적으로 쓰인다. 

---

Topological sort

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

void topologicalSort(int V, unordered_map<char, vector<char>>& adj) {
    unordered_map<char, int> in_degree;  // 각 정점의 진입 차수를 저장할 맵
    for (auto& pair : adj) {
        char u = pair.first;
        for (char v : adj[u]) {
            in_degree[v]++;
        }
    }

    // 진입 차수가 0인 노드를 큐에 추가
    queue<char> q;
    for (auto& pair : adj) {
        char u = pair.first;
        if (in_degree[u] == 0) {
            q.push(u);
        }
    }

    while (!q.empty()) {
        char u = q.front();
        q.pop();
        cout << u << " ";  // 현재 노드를 출력하거나 정렬된 리스트에 추가

        for (char v : adj[u]) {
            if (--in_degree[v] == 0) {  // 진입 차수를 줄이고 0이 되면 큐에 추가
                q.push(v);
            }
        }
    }
}

int main() {
    int V = 14;  // 노드 수
    unordered_map<char, vector<char>> adj;  // 그래프 인접 리스트 표현
    
    // 예시로 정점 연결 추가

    adj['m'] = {'q','r','x'};
    adj['n'] = {'o','q'};
    adj['o'] = {'r','s','v'};
    adj['p'] = {'o','s','z'};
    adj['q'] = {'t'};
    adj['r'] = {'u','y'};
    adj['s'] = {'r'};
    adj['t'] = {};
    adj['u'] = {'t'};
    adj['v'] = {'x','w'};
    adj['w'] = {'z'};
    adj['x'] = {};
    adj['y'] = {'v'};
    adj['z'] = {};


    cout << "Topological Sort: ";
    topologicalSort(V, adj);
    cout << endl;
    return 0;
}

• 그래프를 선형적으로 정렬하는 방법으로 DAG(선끼리 방향성은 있지만 순환하는 사이클은 없는 그래프)에서 모든 정점들을 순서대로 나열하는 방법을 다룬다.
• 방향성이 있는 간선으로 이어져있기에 순서가 존재한다. 그래 방향성에 거스르지 않도록 어떻게 순서대로 나열할 수 있을지를 나타낸다. 
• 여기서 진입차수와 진출차수라는 개념이 나오는데 진입차수가는 그 노드로 들어오는 선의 수, 진출차수는 그 노드에서 나가는 선의 개수이다. 
• 그래서 시작점은 진입차수가 0인점에서 시작한다. 그리고 그 점부터 시작하여 그 점을 큐에 넣고, 그 점과 그 점에서 진출한 차수를 모두 제거하면서 시작한다.
• 그렇게 제거하면 새롭게 진입차수가 0이되는 점이 나오는데 그러면 그 점이 큐에 들어가게 된다.
• 만약 큐를 다 비웠는데도 모든 점을 해결하지 못했다면 그 그래프는 사이클이 있다는 뜻이다. 
• 위상정렬은 여러가지가 나올 수 있다. 

---

Binary Search

#include <iostream>
#include <algorithm>
#include <cstring>  // 문자열 비교를 위한 헤더
using namespace std;

void binarySearch(int arr[], int left, int right, int a) {
    // 종료 조건: left가 right보다 커지면 더 이상 찾을 수 없음
    if (left > right) {
        printf("값을 찾을 수 없습니다.\n");
        return;
    }

    // mid 계산 시 오버플로우 방지
    int mid = left + (right - left) / 2;

    // 값을 찾으면 인덱스를 출력
    if (arr[mid] == a) {
        printf("%d번째에 값이 있습니다.\n", mid);
        return;
    }
    
    // 값을 찾지 못하면 이진 탐색을 계속 진행
    if (a > arr[mid]) {
        binarySearch(arr, mid + 1, right, a);    
    } else {
        binarySearch(arr, left, mid - 1, a);  
    }
}

int main() {
    int arr[10000];
    
    // 배열에 랜덤 값 채우기
    for (int i = 0; i < 10000; i++) {
        arr[i] = rand() % 10000;
    }

    // 배열 정렬
    sort(arr, arr + 10000);

    char input[10];  // 입력을 받기 위한 배열
    while (true) {
        printf("찾을 값을 입력하세요 (종료하려면 'Q' 입력): ");
        scanf("%s", input);

        // 입력이 'q'라면 반복문 종료
        if (strcmp(input, "Q") == 0) {
            break;
        }

        // 입력 받은 값이 숫자라면 이진 탐색
        int a = atoi(input);  // 문자열을 정수로 변환
        binarySearch(arr, 0, 9999, a);
    }

    printf("프로그램을 종료합니다.\n");
    return 0;
}

• 정렬된 값들에서 계속 반씩 줄여나가는 이진탐색 알고리즘이다.
• 인덱스 중간 값을 보고 그것보다 크면 오른쪽, 그보다 작으면 왼쪽을 재귀적으로 탐색한다.
• 중요한 건 종료조건이다. 값이 배열에 없는 경우를 선택해 보자. 이 경우 값이 2칸 범위까지 좁혀졌을 때 left와 right는 바로 옆에 붙어 1만큼 차이 날 것이다. 하지만 값이 없으니 left+1~right 범위를 탐색하거나 left~right-1 범위를 탐색하려 할 것이다. 그러면 어떻게 되든 left==right 인 것이다. 여기서도 값을 찾지 못하면 다음번에는 left와 right의 역전현상이 일어난다. 그래서 left보다 right가 커지면 값이 없음을 밝히고 종료하게 된다. 
• mid 계산시 (right+left)/2가 아니라 left+(right-left)/2를 하는 이유는 뭘까? right+left가 정수범위를 초과하는 경우 순간적으로 2를 나누기 전에 오버플로우가 날 수도 있다. 그래서 저렇게 계산한다. 그 정도 크기의 수가 들어오지 않는다고 전제하면 그냥 (right+left)/2로 계산해도 상관없다.

---

Russian Peasant Mulitplication

import time

def regular_multiplication(n, m):
    return n * m

def russian_peasant_multiplication(n, m):
    result = 0  # 결과를 저장할 변수
    while n > 0:
        if n % 2 != 0:  # n이 홀수일 경우
            result += m  # m을 결과에 더함
        n = n // 2  # n을 2로 나눔
        m = m * 2  # m을 2배로
    return result


n = 519534236238247351384500342837
m = 239925363457925217438408


start_time = time.time()
result_regular = regular_multiplication(n, m)
end_time = time.time()
regular_time = end_time - start_time


start_time = time.time()
result_russian_peasant = russian_peasant_multiplication(n, m)
end_time = time.time()
russian_peasant_time = end_time - start_time


print(f"일반 곱셈 결과: {result_regular}, 처리 시간: {regular_time}초")
print(f"러시안 페이잔트 방법 결과: {result_russian_peasant}, 처리 시간: {russian_peasant_time}초")

• 컴퓨터 곱연산은 여러 자릿수끼리 곱할 때 그만큼 곱셈이 늘어난다는 문제가 있다. 이 알고리즘 역시 컴퓨터의 곱연산을 줄이고 합연산을 늘리는 알고리즘이다.
• 두 수를 곱할 때 한쪽 수는 2로 나누고 다른 쪽 수는 두배로 증가시킨다. 그래서 한쪽 수는 계속 나누기만 해서 궁극적으로 1로 만들어 다른쪽 수만 구할 수 있게 하는 것이 목표다.
• 만약 2로 나누어야 하는데 홀수라면, 1을 빼준 상태로 계산한다. 그래서 그 빠진 만큼은 나중에 모아두었다가 한 번에 더해준다.
• 곱셈 연산이 클 때 더 빠른 속도로 계산할 수 있게 해 준다.

---

Josephus Problem

#include <iostream>
#include <algorithm>
using namespace std;

int josephus(int n, int k){
    if(n==1){
        return 1;
    }else{
        return ((josephus(n-1,k)+k-1)% n)+1;
    }
}


int main() {
    int n,k;
    scanf("%d %d",&n, &k);
    printf("%d",josephus(n,k));
    return 0;
}

 

• n명을 원으로 세워놓고, k번째 사람 제거, 다시 제거한 사람으로부터 k번째 사람을 제거... 반복하여 마지막 살아남는 사람의 위치를 찾는 알고리즘이다.
• 그냥 원형 배열을 만들어 시뮬레이션할 수도 있으나 재귀함수로 찾을 수 있다.
• 요세푸스 문제에서는 매번 한 명씩 제거하므로, 제거되는 사람을 기준으로 문제를 축소해 나갈 수 있다. 각 단계에서 한 명이 제거될 때마다 남은 사람들로 새로운 요세푸스 문제를 형성한다.
• 만약 n이 1 즉, 한 명 남았다면 더 이상 시뮬레이션 할 필요 없이 그 사람 생존으로 끝나므로 1을 반환한다.
• josephus(n,. k) 즉 n명이 남아있는 상태에서 다음단계를 생각해 보자. 다음단계는 사람이 한 명 줄었으니 n은 n-1이 될 테고, k는 상수값이므로 변하지 않는다. 그 대신 마지막으로 생존한 사람은 k번째로 더 나아간 사람이다.
• 예시를 들면 5명인 상태에서 2번째 사람을 제거하면 4명이 남은 상태에서의 요세푸스 문제인 것이다. 그런데 이전에 돌던 번호 체계를 다시 부여해야 하니 그만큼 k를 더하고 m의 모듈러 연산으로 값을 부여해 주는 것이다. 
• 여기서 원형으로 있으니 값을 초과한 경우 n으로 나누어 주고, 첫 번째 사람을 0번이 아닌 1번으로 잡았으므로 1을 +- 계산 추가로 처리해 준다.  

---

Euclid's algorithm

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int m, int n){
    int r = m%n;
    if(r==0){
        return n;
    }else{
        return gcd(n,r);
    }
}


int main() {
    int n,k;
    scanf("%d %d",&n, &k);
    printf("%d",gcd(n,k));
    return 0;
}

 

• 최대 공약수를 구하는데 유용한 유클리드 알고리즘이다. 
• 두 수가 나누어 떨어지지 않으면 두 수를 나눈 나머지와 더 작은 수를 재귀함수에 넣고 돌린다.

---

Selection Problem

#include <iostream>
#include <math.h>
using namespace std;

int pivoting(int start,int end, int k, int arr[]){
    int pivot = arr[(start+end)/2];
    int left=start;
    int right =end;
    while(left<=right){
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;
        if (left <= right) { 
            swap(arr[left], arr[right]);
            left++; 
            right--;
        }
    }
   if (k <= right) {
        return pivoting(start, right, k, arr);  
    } else if (k >= left) {
        return pivoting(left, end, k, arr);   
    } else {
        return arr[k];  
    }
}

int main() {
    int n =10000;
    int arr[n];
    for(int i=0; i<10000; i++){
        arr[i]=rand()%10000;
    }
    int k =rand()%10000;
    printf("%d번째로 작은 수: %d",k,pivoting(0,n-1,k,arr));
}

• Pivot을 정해 정렬하는 선택정렬을 이용한 문제다. 정렬되지 않은 배열에서 n번째로 작은 수를 찾는 방법을 다룬다.
• 그냥 일단 다 정렬하고, 그다음에 index로 찾아도 되지만 더 빠른 방법이 있다.
• n번째로 작은 수만 찾으면 되기에 다른 수들을 굳이 다 정렬하여 몇 번째로 작은지 알 필요가 없다. n번째 수의 위치만 확인하면 되는 것이다.
• 그래서 Pivot을 정하여 정렬한다. 그래서 위치를 확인하고 현재 찾는 위치에 따라 절반씩만 정렬해 나가면, 알고리즘 효율이 증가한다.
• Selection sort에서도 마찬가지지만 Pivot은 움직이지 않는 점이 아니다. Pivot은 값만 빌려준 것이고, 얼마든지 swap 하여 움직일 수 있다. Pivot의 좌우가 맞지 않는 것은 아무런 상관이 없다. 애초에 Pivot 정렬은 왼쪽의 포인터가 오른쪽의 포인터를 추월할 때 끝난다. 딱 절반씩 나누어지는 게 아니다. 그래서 Pivot의 값에 따라 그때그때 효율이 달라질 수 있다. 

---

Interpolation Search

#include <iostream>
#include <algorithm>
using namespace std;

int interpolation(int start, int end, int k, int arr[]) {
    if (start > end || arr[start] > k || arr[end] < k) { 
        return -1;
    }
    int pos = start + (k - arr[start]) * (end - start) / (arr[end] - arr[start]);
    if (pos < start || pos > end) {
        return -1;
    }
    int tempans = arr[pos];
    if (tempans == k) {
        return pos;  
    } else if (tempans < k) {
        return interpolation(pos + 1, end, k, arr); 
    } else {
        return interpolation(start, pos - 1, k, arr); 
    }
}

int main() {
    int n = 1000;
    int arr[n];
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % n;
    }
    sort(arr, arr + n);  
    int f;
    cout << "찾으려는 값을 입력하세요: ";
    cin >> f;
    int result = interpolation(0, n - 1, f, arr);
    if (result != -1) {
        cout << "위치: " << result << endl;
    } else {
        cout << "값을 찾을 수 없습니다." << endl;
    }
    return 0;
}

 

• 이진탐색을 조금 더 보완한 문제이다. 이진탐색처럼 그룹을 반으로 나누어 값을 찾는 원리는 같다. 하지만 정확히 절반이 아니다.
• 현재 찾는 그룹의 최솟값과 최댓값을 파악하여, 현재 값이 있을만한 대략적인 위치를 나누는 지점으로 잡는다.
• 따라서 보간탐색의 경우 중간에 값을 얻어걸려 찾을 확률을 높였다. 

---

 

결론

Decrease and Conquer에 관한 알고리즘들이었다.