[고급-4] 재귀함수의 확장

학습목표

-이진 문자엘에 대한 문자열 압축(혹은 암호화)에 대한 기법을 실제적인 문제를 통해 해결하는 과정을 재귀적인 관계로 설명할 수 있다.

-압축(암호화)된 이진 문자열을 압축이전의 문자열로 복원하는 방법을 압축하는 방법에 대한 역의과정으로 설명할 수 있다.

-재귀적인 관계 구성의 다양한 방법을 이해할 수 있다.

1. 재귀함수 활용

<이진 암호화>

이진 압축이란, {0,1}로 이루어진 길이가 2^k인 문자열에 대해서 모두 같은 문자가 될 때까지 크기가 2^(k-1)인 두 그룹으로 분할하여 모두 같은 문자가 되도록 하는 과정으로 암호화 한다.

1101

=>-1-01

-:분할, 1:왼쪽은 모두 1, -오른쪽 분할됨, 01:왼쪽0오른쪽1

ex)

00111101을 암호화 해보자.

분할하면 0011/1101

왼쪽 분할하면 00/11/1101

오른쪽 분할하면 00/11/11/01

00/11/11/01 = r1/r2/r3/r4

r1, r2, r3 : 분할 필요없음

r4 : 분할 필요.

=>00/11/11/0/1

f(a,n) = S[a]로부터 시작해서 길이가 n인 영역을 암호문자열로 치환한 결과.

{첫번째 방법. index와 길이를 사용}

f(a,n) = f(a,n/2), f(a+n/2,n/2)

char S[1<<19];
int n;
void f(int k, int s){
    int sum=0;
    if(s==1){
        printf("%c", S[k]);
        return 0;
    }
    for(int i=k; i<k+s; ++i){
        sun+= (S[i]-'0');
    }
    if(su==0 || sum==s){
        printf("%d", (bool)sum);
    }
    else{
        printf("-");
        f(k, s/2);
        f(k+s/2, s/2);
    }
}

(참고)[1번째 줄]1<<19==2^19

{두번째 방법. index와 index를 사용. f(a,b)=S[a]로부터 시작해서 S[b]까지 영역을 암호문자열로 치환한 결과}

char t[1<<20];
void f(int s, int e){
    for(int i=sl i<e; ++i){
        if(t[i]==t[i+1]) continue;
        else{
            printf("-");
            f(s, (s+e)/2);
            f((s+e)/2+1,e);
            return;
        }
    }
    printf("%c", t[e]);
}

2. 재귀함수 활용

<이진 복원>

{첫번째 방법. Queue를 이용}

f(k,n,v) = 암호문자 v

k=index , n=길이, v=0or1

#include <queue>
using namespace std;
/*
Q.empty() : 큐가 비어있나?
*/
void f(int k, int s, char v){
    if(Q.empty()) return;
    if(v=='-'){
        Q.pop();
        f(k, s/2, Q.front());//Q.front : 다음 V
        Q.pop();
        f(k+s/2, s/2, Q.front());
    }
    else{
        for(int i=k; i<k+s; ++i)
            S2[i]=v;
    }
}        

{두번째 방법. 일반적인 배열 이용}

void f(int k, int s){
    char val=s[p++];
    if(val==NULL)
        return;
    if(val=='-'){
        f(k, s/2);
        f(k+s/2, s/2);
    }
    else{
        for(int i=k; i<k+s; ++i){
            s2[i]=val;
        }
    }
}