정올 고급 강의 1~6차시 정리

1차시 관계기반 알고리즘 설계

정보/과학 분야의 수학적 귀납법은 문제 증명이 아닌, 문제 해결의 방법으로 쓰이고 있다.

수학의 수학적 귀납법-

1. P(1)이 성립함을 보인다.

2. P(k)가 성립한다고 가정하고 P(k+1)이 성립함을 보인다.

정보/과학 분야의 수학적 귀납법-

1. 입력값이 n인 문제의 해를 f(n)으로 정의한다. (이 부분이 다르다)

2. f(1)을 직접 구하여 출력한다.

3. f(k)를 이미 구해두었다고 가정하고 f(k)를 통해 f(n)을 구하여 출력한다.

2차시 재귀함수의 설계

[숫자 뒤집기]

방법1. solve(n)을 이용한 재귀호출을 이용

1. n을 입력받고

2. n%10 출력, solve(n/10) 호출

3. n이 0이 아니면 반복

int solve(int n){
    if(n==0) return 0;
    printf("%d", n%10);
    solve(n/10);
}

방법2. f(n)을 직접 값으로 정의

1. n의 1의 자릿수와 몫으로 분리한다. (n/10=12, n%10=3)

2. n/10을 거꾸로 만들고 f(n/10)을 호출한다. (21)

3. n%10의 값에 10을 곱한다. (300)

4. 2, 3에서 구한 값을 더한다. (21+300=321)

int solve(int n){
    if(n<10) return n; //1자리 숫자면 뒤집어도 똑같아서 n이 됨
    return f(n/10)+(n%10)*powf(10.0, (int)log10((double)n)); //2자리 숫자면 뒤집음
}

powf-실수의 거듭제곱을 위한 함수, math.h에 있음

방법3. f(n)을 직접 값으로 정의하며 수를 3개로 분할

1. n의 일의 자릿수를 분리한다. (123%10=3)

2. 가장 큰 자릿수를 분리한다. (123/100=1)

3. 일의 자릿수와 가장 큰 자릿수를 제외한 중간수 f(m)을 구한다. (2)

4. 일의 자릿수*10^[log n]+f(m)*10+가장 큰 자릿수

int solve(int n){
    if(n<10) return n;
    int T=(int)powf(10.0,((int)log10(n)));
    return (n%10)*T+f((n%T)/10*10+n/T;
}

[별 그리기]

방법1. 그냥 푼다

f(n-1)까지 있다고 가정하고 f(n) 만큼의 별을 추가로 그려줌

void f(int n){
    if(n==1) printf("*\n");
    else{ //n이 1보다 큰 경우
        f(n-1);
        for(int i=0; i<n; i++) printf("*");
        printf("\n");
    }
}

방법2. 수행 시간을 줄인거

1. 빈 문자열을 준비

2. 한 줄에 출력할 때마다 문자열 마지막에 "*"을 추가하고 문자열을 출력

3. 모든 줄을 출력하지 않았으면 반복

char star[MAXN+1]
 
void f(int n){
    if(n>0){
        f(n-1);
        star[n]="*"; //수행시간 n
        puts(star+1);
    }
}

[조합]

nCk는 n개 중에서 k개를 고르는 방법의 수이다.

일반식: n!/k!(n-k)! ← n!을 이용하기 때문에 n이 커지면 오버플로우 발생

방법1. f(n,k) = n개에서 k개를 고르는 경우의 수

f(n,k) = 마지막 물건을 고른 경우의 수[f(n-1,k-1)]+ 마지막 물건을 고르지 않은 경우의 수[f(n-1,k)]

int f(int n, int k){
    if(k==n) return 1;
    else if(k==1) return n;
    else return f(n-1, k-1)+f(n-1, k); //2^k 수행시간이라 너무 큼
}

방법2. 효율적인 방법

f(n, k-1) = n!/(k-1)!(n-k+1)!

f(n, k) = f(n, k-1) * (n-1k+1)/k ←식을 이렇게 변형

int f(int n, int k){
    if(k==n) return 1;
    else if(k==1) return n;
    else return f(n, k-1) * (n-1k+1)/k
}

3차시 재귀함수의 활용

[노드 간의 거리 구하기 Distance of node]

정리1. 트리의 두 노드 간의 경로는 오직 한 개만 존재한다.

정리2. 완전 이진 트리의 형태를 가지기 때문에 배열의 저장되는 노드 간의 관계를 다음과 같이 계산할 수 있다.

int f(int a, int b){
    if(a==b) return 0;
    if(b>a) return f(a, b/2)+1;
    if(a<b) return f(a/2, b)+1;
}

4차시 재귀함수의 확장

[이진 암호화]

방법1. f(a, n) = S[a]으로부터 시작하여 길이가 n인 영역을 암호문자열로 치환

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

방법2. f(a, b) = S[a]부터 시작해서 S[b]까지 영역을 암호문자열로 치환

[이진 복원]

방법1. 큐 사용

#include <queue>
using namespace std;
 
void f(int k, int s, char v){
    if(Q.empty()) return;
    if(v=='-'){
        Q.pop();
        f(k, s/2, Q.front());
        Q.pop();
        f(k+s/2, s/2, Q.front());
    }
    else{
        for(int i=k; i<k+s; i++){
        S2[i]=v;
    }
}

방법2. 배열 사용

void(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=0; i<k+s; i++)
            S2[i]=val;
    }
}

5차시 동적표와 상/하향식 설계

[동적표]

방법1. 수학적인 식을 이용해서 채우기

n(n+1)/2로 채우는데 편리하지가 않다.

방법2. 동적으로 표를 채우기

피보나치: f(n-1)+f(n-2) ← 편하긴 한데 입력값이 100이 넘어가면 실행에 대략 26,241년이 걸린다.

실행 시간을 줄이기 위해 메모이제이션 사용

int DT[100001]; //전역 배열은 0으로 초기화 됨
 
int f(int n){
    if(n<=2) return 1;
    if(!DT[n]) DT[n] = f(n-1)+f(n-2);
    return DT[n];
}

실행시간

입력값 100 → 0.000초

50,000 → 0.002초 ㄷㄷ

[상향식, 하향식]

상향식: 

for(int i=0; i<n; i++)

하향식: 

for(int i=n; i>0; i--)

재귀함수의 상향식

void f(int k){
    if(k==n) return;
    f(k+1);
}

재귀함수의 하향식

void f(int k){
    if(k==1) return;
    f(k-1);
}

=> 주로 반복문은 상향식, 재귀함수는 하향식으로 접근하는 것이 일반적

=> 재귀함수의 상향식은 또 다른 의미로 문제를 해결할 좋은 방법이 될 수 있음

6차시 동적테이블의 응용1

[광석수집]

GT혹성에 광석을 수집하는 SCV는 항상 오른쪽이나 아래쪽으로만 진행된다. 이때 SCV가 수집하는 최대 광석의 개수를 출력하라.

최대 n*m으로 이루어진 광석을 캐는 지역이 입력되고 항상 시작(s)은 1,1에서 시작하여 도착지점(d)은 n,m에서 종료된다.

(1,1)에서 출발하여  n행 m열까지 오른쪽 혹은 아래쪽으로만 진행하면서 얻을 수 있는 최대 광석의 수를 구하는 프로그램을 작성하시오.

방법1. 전체탐색법(백트래킹)=깊이우선탐색

int n, m, A[210][210], DT[210][210];
 
int solve(int a, int b){
    if(a==n && b==m) return A[n][m]; //목적지에 도착했으면 종료, 이 때 얻을 수 있는 광석의 수는 (n, m)에 쓰여진 값=마지막 광석의 값
    if(a>n || b>m) return 0;  //a나 b가 맵에서 빠지면 더이상 광석을 얻을 수 없음
    return max(solve(a+1, b), solve(a, b+1)) + A[a][b]; //더 많이 얻는 쪽으로 이동+현재 칸에 있는 광석을 더함
}
 
int main(){
    scanf("%d%d" &n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &A[i][j]);
        }
    }
    printf("%d\n", solve(1,1));
}

=>경우의 수가 O(2^n+m)이 돼서 계산량이 너무 큼

=> DP를 쓰자

방법2. 동적 프로그래밍

int n, m, A[210][210], DT[210][210];
 
int solve(int a, int b){
    if(DT[a][b] == 0){
        if(a==n && b==m) return A[n][m]; //목적지에 도착했으면 종료, 이 때 얻을 수 있는 광석의 수는 (n, m)에 쓰여진 값=마지막 광석의 값
        else if(a>n || b>m) return 0;  //a나 b가 맵에서 빠지면 더이상 광석을 얻을 수 없음
        else return DT[a][b] = max(solve(a+1, b), solve(a, b+1)) + A[a][b]; //더 많이 얻는 쪽으로 이동+현재 칸에 있는 광석을 더함
    }
    return DT[a][b];
}
 
int main(){
    scanf("%d%d" &n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &A[i][j]);
        }
    }
    printf("%d\n", solve(1,1));
}

방법3. 반복문

int n, m, A[210][210], DT[210][210];
int max(int a, int b) {return a>b ? a:b; }
 
int main(){
    scanf("%d%d" &n, &m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%d", &A[i][j]);
        }
    }
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(i==1 && j==1)
                DT[i][j] = A[i][j];
            else
                DT[i][j]=max(DT[i-1][j], DT[i][j-1]) + A[i][j];
        }    
    }            
    printf("%d\n", DT[n][m]);
}