Kim Ji Soo

I am an amazing person.

순환

함수(function)

하나의 특별한 목적의 작업을 수행하기 위해 독립적으로 설계된 코드들의 모임으로 하나의 단위를 의미

순환(recursion)

자신을 정의할 때 자기 자신을 재 참조하는 방법

  • 순환 또는 재귀적(recursive) : 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 것

간단한 순환의 예

  • 버스 기다리기(x)
    • 버스를 기다린다.
    • 버스가 오면 버스의 번호를 확인한다.
    • 만일 버스 번호가 x이면 버스를 타고 ‘버스 기다리기(x)’를 종료한다.
    • 만일 버스 번호가 x가 아니면, ‘버스 기다리기(x)’를 다시 수행한다.

순환 함수(recursion function)

자기 자신을 반복적으로 호출하여 수행하는 방식을 통해 주어진 문제를 해결하는 함수(알고리즘)

재귀 함수, 재귀 호출, 되부름이라고 불리기도 함

직접 순환(direct recursion) : 자기 자신을 직접 호출

void DirectRecursion(...){
    ...
    Direct Recursion(...);
    ...
}

간접 순환(indirect recursion) : 피호출 함수 내에서 호출 함수를 다시 호출

void CallingFunction(...){
    ...
    IndirectRecursion();
    ...
}

void IndirectRecursion(...){
    ...
    CallingFunction();
    ...
}


순환의 예

1에서 n까지의 자연수 더하기

1부터 입력된 수까지의 합을 구하기

#include <stdio.h>

int sum(int n);

int main(){
    int n;

    printf("입력 값="); 
    scanf("%d", &n);

    printf("1부터 %d까지의 합은 %d이다.", n, sum(n));
}

int sum(int n) {
    if(n == 1) //종료조건
        return 1;
    else return n + sum(n - 1); //스택을 이용하여 중간계산 결과값과 반환 포인터를 저장
}

실행결과

입력 값=8
1부터 8까지의 합은 36이다.


계승(factorial)

1부터 입력된 수까지의 factorial 값을 구하기

#include <stdio.h>

int factorial(int n){
    if(n == 1) //n이 1일때, 1을 반환하고 재귀호출을 끝냄
        return 1;
    
    return n * factorial(n - 1); //n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱함
}

int main(){

    int n;
    printf("입력 값=");
    scanf("%d", &n);
    printf("입력값 %d의 factorial=%d이다.", n, factorial(n));

    return 0;
}

실행결과

입력 값=5
입력값 5의 factorial=120이다.


피보나치 수열(fibonacci sequence)

1부터 입력된 수까지의 피보나치 수열의 합 구하기

#include <stdio.h>

int fib(int n){
    if(n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

int main(){

    int n;
    printf("피보나치 수 입력:");
    scanf("%d", &n);
    printf("입력된 수%d의 피보나치 수열의 합: %d", n, fib(n));

    return 0;
}

실행결과

피보나치 수 입력:7
입력된 수7의 피보나치 수열의 합: 13

순환의 함정 - 피보나치 수열(fibonacci sequence)

  • Function Call이 쓸데 없이 겹쳐지게 되는 상황
  • 시간복잡도 - O(2n)
    • 높이 n인 이진 트리의 총 노드 수는 2n - 1
  • 순환은 n=40 정도만 되도 사실상 계산이 불가능한 수준임


Memoization 기법

  • 프로그램이 동일한 계산을 반복해야 할 때, 이전에 게산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행속도를 빠르게 하는 기술
    • 함수를 위한 캐싱 기법
    • 주어진 입력에 대해 항상 동일한 출력을 반환하는 알고리즘에 한해 사용
  • Memoization을 사용하게 되면 대략 2000까지 정도는 계산이 가능
  • 시간 복잡도 - O(n)



하노이 탑(hanoi tower)

  • 여러 개의 원반과 세 개의 기둥이 있는데 원반의 크기는 각각 다름
  • 먼저 모든 원반은 기둥 A(source)에 위치하지만 그 원반들을 기둥C(destination)로 이동해야 함
  • 한번에 한 개의 원반만을 옮길 수 있고 어떠한 경우에도 원반은 그 보다 작은 원반 위에 올려질 수 없음

하노이 탑 문제를 해결할 수 있는 순환 알고리즘

  • 모든 원반을 처음 시작한 기둥(from) A에서 다른 하나의 중간 기둥(aux) B를 사용하여 n개의 원반을 목적 기둥(to) C로 이동한다고 가정
  • 제 1단계 : 가장 큰 원반을 제외한 나머지 개의 원반을 A에서 I로 이동
  • 제 2단계 : A에 남아있던 한 개의 원반을 C로 이동
  • 제 3단계 : 작은 피라미드를 I에서 A로 이동
  • 제 3단계에서는 1단계와 2단계에서 했던 과정을 반복하여 수행, 이때 3단계의 원반의 개수는 1단계 보다 1개 적어짐

하노이 탑 문제를 해결할 수 있는 순환 알고리즘 => hanoi(3, ‘A’, ‘B’, ‘C’) 

#include <stdio.h>

void towerOfHanoi(int n, char from, char aux, char to){
    if(n == 1){
        printf("\n Move disk 1 from %c to %c", from, to);
        return;
    }

    towerOfHanoi(n-1, from, to, aux);

    printf("\n Move disk %d from %c to %c", n, from, to);

    towerOfHanoi(n-1, aux, from, to);
}

int main(){

    int n = 3; // Number of disks
    towerOfHanoi(n 'A', 'B', 'C');

    return 0;
}

실행결과

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C


순환 알고리즘을 비순환 알고리즘으로 변환

순환 구조(함수)는 반복 구조로, 반복 구조를 사용하는 알고리즘은 순환 구조를 통해 구현하는 것이 가능

  • 재귀 함수의 메모리와 성능에 대한 문제점을 해결할 수 있음

과정

  1. 순환 함수에서 비 순환을 위한 초기조건을 구함
  2. 순환 함수의 현재 값과 다음 값과의 관계를 이용하여 다음 값을 구하는 관계식을 유도
  3. 관계식을 비 순환으로 표현
int factorial(int n){
    if(n<1) return (1); //종료 조건
    else return (n*factorial(n-1));
}

공간복잡도 : O(n)

시간복잡도 : O(n)


int factorial_interation(int n){
    int k, v = 1; //비순환을 위한 초기 조건

    for(k=n; k>0; k--)
        v = v*k; //관계식
    
    return v;
}

공간복잡도 : O(1)

시간복잡도 : O(n)



순환 함수의 특징 및 고려사항

순환 함수의 특징

어떤 문제를 해결하기 위하여 함수가 자기 자신을 호출할 때마다 문제가 작아지고 단순해져 문제의 해결점에 도달함

  • 프렉탈 모형 - 일부 작은 조각이 전체와 기하학적으로 비슷하게 무한대로 반복하면서 만들어내는 형태를 말함

설명하기 어렵고 복잡한 문제들을 간단히 정의할 수 있고, 표현법이 매우 간단함

  • 코딩이 단순하여 가독성이 좋으며 오류 수정이 용이함
  • 변수 사용이 줄어 듬

호출 시 매번 스택(기억공간) 사용으로 인한 수행시간 오버헤드 및 오버플로우가 발생할 수 있음


순환 함수의 고려사항

순환 호출을 끝낼 수 있는 종료조건을 확인해야 함

  • 순환함수 안에서의 초기화(종료조건)을 하지 않으면 시스템이 무한 반복으로 인해 메모리 오류를 범하게 됨

순환 호출로 프로그램이 간단해 질 수 있는지 확인이 필요함

각 순환 호출은 활성 레코드(activation record)에 관련된 정보(지역 변수와 인수, 반환 주소 등)을 스택에 저장해야 하므로 기억 공간이 충분한지 확인 후에 사용해야 함

순환 호출을 사용하여 특별한 이점이 없을 경우에는 비 순환 방법을 사용하는것이 좋음

  • 순환 호출은 문맥 변경(context switch)이 일어나기 때문에 재귀호출은 반복 호출(구조)에 비해 수행 시간이 더 느림
  • 효율적인 프로그램 디자인을 위해서는 권장되는 방법은 아님



백트래킹

백트래킹(퇴각 검색, 되추적, backtracking)

문제를 해결하는 과정에서 고려할 수 있는 모든 경우의 수를 모두 탐색해보는 일반적인 알고리즘 기법(a sort of recursion)을 말함

  • 탐색 과정에서 해를 찾는 도중 해가 아니면, 되돌아가서 다시 해를 찾아가는 기법
    • 한정 조건을 가진 문제(constraint satisfaction problem : 제약 충족 문제)
    • Car navigation system, decision problem, optimization problem, enumeration problem 등에 주로 사용

예를 들어 미로에서 길찾기를 할 때 갈림길에 표시를 해둔다면 가던길이 막힌 길이라도 다시 표시해둔 갈림길로 되돌아가서 다른 곳으로 갈 수 있다.


관련 용어

상태공간 트리(state space tree)

  • 백트래킹을 위해 고려해야 할 모든 경우의 수(상태)를 트리 구조를 이용하여 표현한 것
    • 해를 찾기 위해 탐색할 필요가 있는 모든 후보들을 포함하는 트리임
    • 트리의 모든 노드들을 방문하면 해를 찾을 수 있음
    • 근 노드에서 출발하여 체계적으로 모든 노드를 방문하는 절차를 기술함

노드의 유망성(promising) - 특정 제약(constraints) 또는 제한(limitations) 조건 검사

  • 문제를 풀면서 여러 가지 조건들을 고려한 다양한 상태(경우의 수)에 대해 그 상태가 찾는 답인지(해답이 나올 가능성)를 점진적으로 탐색해 나감
    • 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않음(non-promising) - 해당 노드의 서브 트리 탐색은 무의미함
    • 그렇지 않으면 유망함(promising)

그래프 탐색 방법 - 깊이우선탐색(depth first search, DFS)과 너비우선탐색(breadth first search, BFS), 최선 우선 탐색 등

가지치기(pruning) - DFS로 모든 정점을 탐색하는 과정에서 조건에 맞지 않는 가지(탐색 경로)를 자르고 다른 탐색 경로(그 노드의 부모)로 돌아가 탐색의 시간을 절약하기 위한 과정을 말함

  • break나 return등 으로 구현


깊이우선 탐색 방법

맹목적 탐색 방법의 하나로 시작점부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 말함

  • 탐색트리에서 근노드(root node)를 선택하여 방문하고, 그 노드의 모든 후손 노드(descendant)들을 차례로(보통 왼쪽에서 오른쪽으로) 방문(= preorder tree traversal)

DFS 알고리즘

void DFS(node v){
    node u;
    visit v;
    for(each child u of v) // from left to right
        DFS(u)
}


백트래킹 알고리즘

DFS를 통한 백트래킹 절차

1. 상태 공간 트리의 DFS를 실시한다.
2. 각 노드가 유망한지를 점검한다.
3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 탐색을 계속한다.

void checknode(node v){
    if(promising(v))
        if(there is a solution at V)
            write the solution;
        else
            for (each child u of v) checknode(u);
}


백트래킹과 DFS차이

DFS - 깊이 우선 탐색하여 모든 노드를 방문하는 것을 목표로 함

  • 완전 탐색으로 인해 유한 시간 내에 끝나지 않을 수도 있음(해가 없는 경로에 깊이 빠질 가능성이 있음)
  • 해를 구했을 때, 그것이 최적이 아닐 수도 있음

백트래킹 - 불필요한 탐색을 하지 않기 위해, 가지치기를 통해 유망하지 않은 경우의 수를 줄이는 것을 목표로 함

  • 일단 방문해보고 더 이상 진행이 되지 않으면 돌아옴


대표적인 백트래킹 문제 : N-queen

  • N x N 크기의 체스판에 N개의 queen을 서로 공격할 수 없도록 배치하는 문제
  • Queen은 다음과 같이 이동할 수 있으므로 서로 상대방을 위혐하지 않기 위해서는 같은 행이나 같은 열, 같은 대각선 상에 위치하지 않아야 함

무작정(brute force) 방법(4x4 board) - N의 크기가 커질 수록 연산량이 기하급수적으로 증가함

전제조건에 따라

  • 각 queen을 각각 다른 행에 할당한 후에, 어떤 열에 위치하면 해답은 얻을 수 있는지를 차례대로 점검
  • 각 queen은 4개의 열 중에서 한 열에 위치할 수 있기 때문에 해답을 얻기 위해서 점검해 보아야 하는 모든 경우의 수는 44 = 256가지 됨

상태공간 트리

  • (i,j) - i번째 queen이 j번째 열에 위치

유망성 검사 및 가지치기

  • DFS탐색을 통해 모든 branch를 최대 깊이까지 검색하지 않고, 요구사항에 맞게 해당 노드의 유망성 검사 및 가지치기를 통해 탐색 공간을 줄임



4 x 4 board에서의 queen 배치 문제

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int chess_board[20], count; // board에 놓여진 queen의 column 위치 값 저장

void nqueen_function(int row, int num){ // queen들의 제한조건 만족 체크
    int col;

    for(col = 1; col <= num; col++){
        if(placeholder(row, col)){ // queen이 위치할 곳을 체크하기 위해 함수 호출
            chess_board[row] = col;

            if(row == num){ // 모든 queen들이 board에 위치했는지 검사
                display(num); // 위치했으면 출력 함수 display()호출
            }
            else{
                nqueen_function(row + 1, num); // 남아있는 queen들을 배치하기 위해 함수 nqueen_function()호출
            }

        }
    }

}

int placeholder(int row, int col){

    int count;

    for(count = 1; count <= row; count++){
        if(chess_board[count] == col){ // 이전에 배치한 queen으로 부터
                                        // 위협받는 여부 체크
            return 0;
        }
        else{
            //대각충돌 체크
            if(abs(chess_board[count] - col) == abs(count - row)){
                return 0;
            }
        }
    }

    return 1; // 위헙이 없으면 queen을 board에 배치
}

int display(int num){

    int m, n;

    printf("\n\n\tPossible Solution %d:\n\n", ++count);

    for(m = 1; m <= num; m++){
        printf("\t[%d]", m);
    }

    for(m = 1; m <= num; m++){
        printf("\t[%d]",m);

        for(n = 1; n <= num; n++){
            if(chess_board[m] == n){
                printf("\tQ"); // (i, j)위치에 queen(Q)을 출력
            }
            else{
                printf("\t*"); // queen배치가 없는 슬롯에 *을 출력
            }
        }
    }

}

int main(){

    int num;

    printf("Enter Number of Queens:\t");
    scanf("%d", &num);

    if(num <= 3){
        printf("\nNumber shound be greater than 3 to from a Matrix\n");
    }
    else {
        nqueen_function(1, num); // nqueen_function()호출
    }

    printf("\n\n");
    return 0;
}

실행결과

Enter Number of Queens:4

    Possible Solution 1:
    [1] [2] [3] [4]
[1]  *   Q   *   *
[2]  *   *   *   Q
[3]  Q   *   *   *
[4]  *   *   Q   *

    Possible Solution 2:
    [1] [2] [3] [4]
[1]  *   *   Q   *
[2]  Q   *   *   *
[3]  *   *   *   Q
[4]  *   Q   *   *



정리

  • 프로그래밍 언어에서 함수는 특별한 목적의 작업을 수행하기 위해 독립적으로 설계된 코드들의 모임으로 하나의 프로그램 단위를 의미한다.

  • 순환 함수(재귀 함수)는 자기 자신을 반복적으로 호출하여 수행하는 방식을 통해 주어진 문제를 해결하는 함수(알고리즘)를 말한다.

  • Memoization 기법은 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행속도를 빠르게 하는 기술이다.

  • 백트래킹 알고리즘은 문제를 해결하는 과정에서 고려할 수 있는 모든 경우의 수를 모두 탐색해보는 일반적인 알고리즘 기법으로 탐색 과정에서 해를 찾는 도중 해가 아니면, 되돌아가서 다시 해를 찾아가는 기법이다.

You may also enjoy