02. 2차시 교육

01.cpp - 선택구역 뒤집기 ( https://www.acmicpc.net/problem/10804 )

#include <stdio.h>
int arr[22];
int arr2[22];
int main(){
    for(int i=1; i<=20; ++i){
        arr[i]=i;
    }
 
    int a, b;
    for(int k=0; k<10; ++k){
        for(int i=1; i<=20; ++i){
            arr2[i]=0;
        }
        scanf("%d %d", &a, &b);
        for(int i=a; i<=b; ++i){
            arr2[i-a]=arr[i];
        }
        for(int i=b; i>=a; --i){
            arr[i]=arr2[b-i];
        }
    }
    for(int i=1; i<=20; ++i){
        printf("%d ", arr[i]);
    }
}

일반적으로 02.cpp 처럼 스왑을 이용해서 바꾸는게 정석이지만 배열 한개를 더 선언해서 다시 역으로 집어넣는 식으로 한번 해봤습니다.

02.cpp - 선택구역 뒤집기(스왑)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
void reverse(int arr[], const int a, const int b){
    for(int i=a; i<=b/2+1; ++i){
        swap(arr[a+i], arr[b-i]);
    }
}
 
int main(){
    int arr[11]={0, 1,2,3,4,5,6,7,8,9,10};
    int a, b;
    scanf("%d %d", &a, &b);
    reverse(arr, a, b);
    for(int i=1; i<=10; ++i){
        printf("%d ", arr[i]);
    }
}

algorithm.h에 있는 swap함수를 사용해서 쉽게 풀어봤습니다.

03.cpp - 정수부분 소수부분 나누기

#include <stdio.h>
 
void decompose(double x, long* int_part, double *frac_part){
    long a;
    double b;
    a=(int)x;
    b=x-(int)x;
    *int_part=a;
    *frac_part=b;
}
 
int main(){
    double x=5.66;
    long i;
    double f;
 
    decompose(x, &i, &f);
    printf("%ld %lf", i, f);
}

형변환을 이용하고 call by reference 를 이용한 인자 전달을 활용합니다.

04.cpp - 포인터를 이용하여 카드 역배치

#include <stdio.h>
#include <algorithm>
using namespace std;
 
void reverse(int *arr, int a, int b){
    for(int i=a; i<=b/2+1; ++i){
        swap(*(arr+a+i-1), *(arr+b-i+1));
    }
}
 
int main(){
    int arr[11]={0, 1,2,3,4,5,6,7,8,9,10};
    int a, b;
    scanf("%d %d", &a, &b);
    reverse(arr, a, b);
    for(int i=1; i<=10; ++i){
        printf("%d ", *(arr+i));
    }
}

배열에서 인덱스를 사용하지 않고 포인터로 카드 역배치를 구현해본 것입니다.

05.cpp - Maximam Sub-Array 와 Kadane Algorithm

#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)
int dp[10];
int arr[10];
int ans;
 
int k(int n){
    if(dp[n]) return dp[n];
    if(n==0) return arr[0];
    else{
        dp[n]=max(arr[n], k(n-1)+arr[n]);
        if(ans<dp[n]){
            ans=dp[n];
        }
        return dp[n];
    }
 
}
 
int main(){
    for(int i=0; i<10; ++i){
        scanf("%d", &arr[i]);
    }
    dp[0]=arr[0];
    ans = arr[0];
    k(9);
    printf("%d", ans);
 
}

*Maximum Sub-Array (최대 구간 합 문제)

주어진 배열에서 합이 가장 큰 영역을 찾는 문제입니다. 전체탐색으로 풀면 O(n^3)의 시간이 걸립니다. (첫 반복문 : 시작부분, 두번째 반복문 : 끝부분, 세번째 반복문 : 합 구하기)

하지만 이걸 단숨에 해결할 수 있는 알고리즘이 있습니다.

*Kadane Algorithm (카데인 알고리즘)

1. Sub-Array의 맨 앞에서부터 차례대로 더한다. (Sum에 저장)

2. Sum이 음수가 되는 지점에서는 0으로 초기화한다.

3. Sum들은 항상 최대값을 유지한다.

이 세가지 순서로 하면 된다고 위키에 써져있습니다.

수업시간에 배운 내용은 : 

이 식이었죠.

설명을 해보자면, 우선 i는 0부터 n까지 커지는 수 입니다. 가장 앞에 보이는  는 i번째 숫자를 제일 마지막으로 한 연속된 숫자들의 집합의 합 중 가장 큰 것입니다.

Max는 첫번째 인자와 두번째 인자 중 큰 수를 반환하는 함수죠. 

에는 i-1번째 숫자를 제일 마지막으로 한 연속된 숫자들의 집합의 합 중 가장 큰 수가 이미 들어가 있습니다.

여기서, 지금 구하는 에선, 에서 현재 arr[i]의 숫자를 더한 값 혹은 그냥 arr[i]의 숫자 둘 중에 더 큰수를 넣어야 합니다.

그림으로 그려보면, (맨 앞이 arr[0] = -1 , 맨 끝이 arr[9] = -2)

이 그림을 자세히 보시면 어떻게 되는 것인지 쉽게 파악이 가능합니다.

이것을 그대로 for문으로 구현해보자면,

int _for(int n){
    int K[10];
    K[0]=arr[0];
    for(int i=1; i<=n; ++i){
        K[i]=max(K[i-1]+arr[i], arr[i]);
    }
    int biggest=K[0];
    for(int i=0; i<=n; ++i){
        printf(" %d ", K[i]);
        if(K[i]>biggest) biggest=K[i];
    }
 
    return biggest;
}

이렇게 됩니다. 위의 예제는 n이 9입니다. 

맨 위에 올린 코드는 이것을 dp, Dynamic Programming(동적계획법, 메모이제이션 기술)을 이용해서 재귀함수의 시간을 단축시켰습니다.

05.cpp

04.cpp

03.cpp

02.cpp

01.cpp