화투의 개발 블로그

정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘이다.

예를 들어 n개의 숫자가 저장되어있는 배열을, 오름차순의 조건으로 작성하여 입력하면 오름차순으로 정렬된 배열을 출력으로 구할 수 있다.

정렬 알고리즘은 정말 다양한데, 이에 따라 각각의 수행시간도 천차 만별이다.

여기서는 우선 O(N^2), O(NlgN)인 알고리즘을 보려고 한다.

1. 선택 정렬(Selection Sort)

선택 정렬은 이름에 맞게 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 현재 위치에 저장 될 값의 크기가 작냐, 크냐에 따라 최소 선택 정렬(Min-Selection Sort)와 최대 선택 정렬(Max-Selection Sort)로 구분 할 수 있다.

최소 선택 정렬은 오름차순으로 정렬될 것이고, 최대 선택 정렬은 내림차순으로 정렬될 것이다.

기본 로직은 다음과 같다.

① 정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.

(정렬되지 않은 인덱스의 맨 앞은, 초기 입력에서는 배열의 시작위치일 것이다.)

② 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.

③ 다음 인덱스에서 위 과정을 반복해준다.

이 정렬 알고리즘은 n-1개,n-2개,..,1개씩 비교를 반복한다.

배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다.

공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.

<선택 정렬>

선택 정렬 C++ 소스코드

(이전에는 temporary 변수에 해당 키 값을 저장하지 않고 그냥 그때그때 스왑하도록 하였으나.

다른 분들의 피드백으로 수정하였습니다)

void selectionSort(vector<int> v){
    for(int i=0;i<v.size()-1;i++){
        int tmp = i;
        for(int j=i+1;j<v.size();j++){
            if(v[tmp]>=v[j]) tmp = j;
        }
        swap(v[i], v[tmp]);
    }
}

2. 삽입 정렬(Insertion Sort)

삽입 정렬은 현재 위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 배열 알고리즘이다.

기본 로직은 다음과 같다.

① 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.

② 별도로 저장해 둔 삽입을 위한 변수와, 비교 인덱스의 배열 값을 비교한다. 

③ 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.

④ 만약 삽입 변수가 더 크면, 비교 인덱스+1에 삽입 변수를 저장한다.

이 정렬 알고리즘 또한 최악의 경우(역으로 정렬되어있을 경우)엔 n-1개,n-2개,..,1개씩 비교를 반복하여 시간복잡도는 O(n^2)이지만.

공간복잡도는 단 하나의 배열에서만 진행하므로 O(n)이다.

<삽입 정렬>

삽입 정렬 C++ 소스코드

//삽입 정렬
void insertionSort(vector<int> v){
    for(int i=1;i<v.size();i++){
        int key = v[i], j = i-1;
            while(j>=0 && key <v[j]){
                swap(v[j], v[j+1]);
                j--;
            }
            v[j+1] = key;
        }   
}

위 코드는 위키피디아 이미지를 통해 좀 더 이해를 쉽게하고자 swap 함수를 이용하였으나, 사실 swap이 아닌 대입연산을 사용하는 것이 조금 더 적합하다.

swap(v[j], v[j+1]) => v[j+1] = v[j]

3. 버블 정렬(Bubble Sort)

버블 정렬은 매번 연속된 두개 인덱스를 비교하여, 정한 기준의 값을 뒤로 넘겨 정렬하는 방법이다. 

오름차순으로 정렬하고자 할 경우, 비교시마다 큰 값이 뒤로 이동하여, 1바퀴 돌 시 가장 큰 값이 맨 뒤에 저장된다.

맨 마지막에는 비교하는 수들 중 가장 큰 값이 저장 되기 때문에, (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼만 반복해 주면 된다.

기본 로직은 다음과 같다.

① 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 이전의 인덱스 값을 비교한다.

② 만약 이전 인덱스가 더 크면, 현재 인덱스와 바꿔준다. 

③ 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교한다.

④ 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.

이 정렬 알고리즘은 1부터 비교를 시작하여, n-1개,n-2개,..,1개씩 비교를 반복하며,

선택 정렬과 같이 배열이 어떻게 되어있던지간에 전체 비교를 진행하므로 시간복잡도는 O(n^2)이다.

공간복잡도도 이 또한 단 하나의 배열에서만 진행하므로 O(n)이다.

<버블 정렬>

버블 정렬 C++ 소스코드

//버블 정렬 
void bubbleSort(vector<int> v){
    for(int i=0;i<v.size()-1;i++){
        for(int j=1; j<v.size()-i;j++)
            if(v[j-1] > v[j])
                swap(v[j-1],v[j]);
        
    }
}

4. 합병 정렬(Merge Sort)

합병 정렬은 분할 정복(Divide and conquer) 방식으로 설계된 알고리즘이다. 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식으로,

분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복한다.

입력으로 하나의 배열을 받고, 연산 중에 두개의 배열로 계속 쪼게 나간 뒤, 합치면서 정렬해 최후에는 하나의 정렬을 출력한다.

합병은 두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해 나간다.

오름차순의 경우 배열 A,배열 B를 비교하여 A에 있는 값이 더 작다면 새 배열에 저장해주고, A인덱스를 증가시킨 후 A,B의 반복을 진행한다.

이는 A나 B중 하나가 모든 배열값들을 새 배열에 저장할 때 까지 반복하며, 전부 다 저장하지 못한 배열의 값들은 모두 새 배열의 값에 저장해준다.

분할 과정의 기본 로직은 다음과 같다.

① 현재 배열을 반으로 쪼깬다. 배열의 시작 위치와, 종료 위치를 입력받아 둘을 더한 후 2를 나눠 그 위치를 기준으로 나눈다.

② 이를 쪼갠 배열의 크기가 0이거나 1일때 까지 반복한다.

합병 과정의 기본 로직은 다음과 같다.

① 두 배열 A,B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i,j로 가정하자.

② i에는 A배열의 시작 인덱스를 저장하고, j에는 B배열의 시작 주소를 저장한다.

③ A[i]와 B[j]를 비교한다. 오름차순의 경우 이중에 작은 값을 새 배열 C에 저장한다. 

    A[i]가 더 컸다면 A[i]의 값을 배열 C에 저장해주고, i의 값을 하나 증가시켜준다.

④ 이를 i나 j 둘중 하나가 각자 배열의 끝에 도달할 때 까지 반복한다.

⑤ 끝까지 저장을 못한 배열의 값을, 순서대로 전부 다 C에 저장한다.

⑥ C 배열을 원래의 배열에 저장해준다.

이 정렬 알고리즘은 분할 과정과 합병 과정이 나뉘어진다.

합병 과정은 두 배열 A,B를 정렬하기 때문에, A배열의 크기를 N1, B배열의 크기를 N2라고 할 경우

O(n1+n2)와 같다. 배열 A와 배열 B는 하나의 배열을 나눈 배열들이기 때문에 전체 배열의 길이가 N이라고 할 경우

N = N1 + N2이므로 O(N)이라고 할 수 있다.

분할 과정은 lgN만큼 일어나는데, 이 이유는 간단하다. 크기가 N인 배열을 분할하면, 한번 분할하면 N/2,N/2 2개, 그다음 분할하면 N/4,N/4,N/4,N/4 4개.

즉 분할 과정은 매번 반씩 감소하므로 lgN만큼 반복해야 크기가 1인 배열로 분할 할 수 있다.

각 분할별로 합병을 진행하므로, 합병정렬의 시간 복잡도는 O(NlgN) 이다.

사용하는 공간은 정렬을 위한 배열을 하나 더 생성하므로 2N개 사용한다. 

<합병 정렬>

합병 정렬 C++ 소스코드

//합병
void merge(vector<int>& v, int s, int e, int m) {
    vector<int> ret;
    int i = s, j = m + 1, copy = 0;
    
    //결과를 저장할 배열에 하나씩 비교하여 저장한다. 
    while (i <= m && j <= e) {
        if (v[i] < v[j])ret.push_back(v[i++]);
        else if (v[i] > v[j])ret.push_back(v[j++]);
    }

    //남은 값들을 뒤에 채워넣어준다. 
    while (i <= m)  ret.push_back(v[i++]);
    while (j <= e)  ret.push_back(v[j++]);
    
    //원래 배열에 복사해준다.
    for (int k = s; k <= e; k++) {
        v[k] = ret[copy++];
    }
}

//합병 정렬
void mergeSort(vector<int>& v, int s, int e){
    if(s<e){
        int m = (s+e)/2;
        /*divide, 분할*/
        mergeSort(v,s,m); //s부터 m까지
        mergeSort(v,m+1,e); //m+1부터 e까지 
        /*conquer, 합병*/
        merge(v,s,e,m);
    }
}

5. 퀵 정렬(Quick Sort)

퀵 정렬 또한 분할 정복(Divide and conquer)을 이용하여 정렬을 수행하는 알고리즘이다. 

pivot point라고 기준이 되는 값을 하나 설정 하는데, 이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행한다.

이를 반복하여 분할된 배열의 크기가 1이되면 배열이 모두 정렬 된 것이다.

기본 로직은 다음과 같다.

① pivot point로 잡을 배열의 값 하나를 정한다. 보통 맨 앞이나 맨 뒤, 혹은 전체 배열 값 중 중간값이나나 랜덤 값으로 정한다.

② 분할을 진행하기에 앞서, 비교를 진행하기 위해 가장 왼쪽 배열의 인덱스를 저장하는 left 변수, 가장 오른쪽 배열의 인덱스를 저장한 right변수를 생성한다. 

③ right부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며. 비교한 배열값이 pivot point보다 크면 right를 하나 감소시키고 비교를 반복한다.

    pivot point보다 작은 배열 값을 찾으면, 반복을 중지한다.

④ 그 다음 left부터 비교를 진행한다. 비교는 right가 left보다 클 때만 반복하며. 비교한 배열값이 pivot point보다 작으면 left를 하나 증가시키고 비교를 반복한다.

    pivot point보다 큰 배열 값을 찾으면, 반복을 중지한다.

⑤ left 인덱스의 값과 right 인덱스의 값을 바꿔준다.

⑥ 3,4,5 과정을 left<right가 만족 할 때 까지 반복한다.

⑦ 위 과정이 끝나면 left의 값과 pivot point를 바꿔준다.

⑧ 맨 왼쪽부터 left - 1까지, left+1부터 맨 오른쪽까지로 나눠 퀵 정렬을 반복한다.

퀵 정렬은 분할과 동시에 정렬을 진행하는 알고리즘이다.

각 정렬은 배열의 크기 N만큼 비교하며, 이를 총 분할 깊이인 lgN만큼 진행하므로 총 비교횟수는 NlgN, 즉 시간 복잡도는 O(NlgN)이다.

다만 퀵 정렬에는 최악의 경우가 존재하는데, 이는 배열이 이미 정렬이 되어있는 경우이다. 이 경우 분할이 N만큼 일어나므로 시간 복잡도는 O(N^2)이다.

이를 방지 하기 위해 앞서 언급했던 전체 배열 값 중 중간값이나나 랜덤 값으로 pivot point를 정하는 방법을 쓰기도 한다.

최악의 경우 때문에 합병 정렬보다 느린 알고리즘이라 생각하기 쉽지만, 발생하기 쉽지 않은 경우이고, 일반적으로 퀵 정렬이 합병정렬보다 20%이상 빠르다고 한다.

이는 바로 다음에 포스트할 정렬의 성능 측정 부분에서 보도록 하겠다.

<퀵 정렬>

퀵 정렬 C++ 소스코드

//퀵 정렬 
void qsort(vector<int>& v, int s, int e) {
    int pivot = v[s];
    int bs = s, be = e;
    while (s<e) {   
        while (pivot <= v[e]&&s<e) e--;
        if (s>e) break;
        while (pivot >= v[s]&&s<e) s++;
        if (s>e) break;
        std::swap(v[s], v[e]);
    }
    std::swap(v[bs], v[s]);
    if(bs<s)
        qsort(v,bs, s-1);
    if(be>e)
        qsort(v,s+1, be);

}

그 외 똑같이 NlgN에 작동하는 힙 정렬, 선형 시간에 작동하는 Count 정렬, Radix 정렬 등등이 있다. 이것 또한 나중에 정리해보도록 하겠다.

<이미지 출처 : 위키피디아>

[문제 링크 : 1725 히스토그램]

[문제 링크 : 6549 히스토그램에서 가장 큰 직사각형]

[문제 링크 : FENCE]

예전에 내가 풀었던 방식은 분할정복이었는데.

스택 문제 복습 겸 스택으로 풀도록 노력하였다.

스택을 통해 스위핑 알고리즘으로 푼다는데 이에 대한 설명은 구종만님의 책에도 있지만 개인적으로 너무 이해가 힘들었다.

스택을 이용해서 풀 때, 가장 왼쪽부터 차례대로 스택에 삽입하여 문제를 해결해간다.

스택에 막대를 삽입하는 조건은 '삽입하려고 하는 막대가, TOP에 있는 막대의 높이보다 클 때'이다.

만약 다음에 삽입하려는 막대가 현재 스택 TOP에 있는 막대보다 작으면, TOP에 있는 막대 높이로 만들 수 있는 직사각형의 오른쪽 끝이 된다.

그 경우 top을 pop하여 너비를 구한다. pop하기 전에 있던 top의 값을 tmp에 저장한다고 해보자. pop후의 스택의 top값은 tmp 왼쪽의 tmp보다 작은 막대이므로, 이 직사각형의 왼쪽 끝이 된다.

즉 tmp의 높이로 만들 수 있는 직사각형의 크기 = h[tmp] * (right - stack.top - 1)

위의 로직을 이해했으면 같을 경우에 굳이 스택에 인덱스를 삽입하지 않는 이유도 이해가 갈 것이다.

반복문을 다 돌았을 때 스택에 값이 남아있으면 이는 최대 직사각형에서 오른쪽 끝이, 전체의 오른쪽 끝인 직사각형들이다. 위에서 구한 공식대로 그 값들을 구해 최대값을 찾으면 된다. 

이를 구현한 코드는 다음과 같다.

#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
long long n, arr[100001];
long long histogram(){
    stack<long long> st;
    long long i,ret = 0;
    //스택에 왼쪽 끝 인덱스값을 미리 삽입해둔다. 
    st.push(-1);
    for(i=0; i<n;i++){
        //스택이 비어있지 않고,  
        while(!st.empty()&&arr[i]<arr[st.top()]){
            //right는 i 
            int tmp = st.top(); st.pop();
            if(!st.empty())
                //left는 st.top
                //left-right-1 너비, 높이 arr[tmp]의 직사각형 넓이 
                ret = max(ret, arr[tmp]*(i-st.top()-1));
        }
        //너비를 다 구하고 다음 판자를 스택에 삽입.
        st.push(i); 
    }
    //히스토그램을 끝까지 스택에 넣었는데도 안끝났다면
    //스택에 남아있는 판자들에서의 최대값을 구한다. 
    while(!st.empty()) {
        int tmp = st.top(); st.pop();
        if(!st.empty())
            ret = max(ret, arr[tmp]*(i-st.top()-1));
    }
    return ret;
}
int main(){
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&arr[i]);
    printf("%lld\n",histogram());
    
}   

참고 : https://www.acmicpc.net/blog/view/12

[문제 링크]

스택을 이용하면 쉽게 푸는 문제이다.

나는 입력 받으면서 스택에서 체크하여 값을 출력하는 방식으로 풀었다.

값을 입력받으면, 스택을 체크한다. 스택을 체크해서 스택이 비었으면 그 탑 왼쪽에는 탑이 없는 것이므로 0을 출력한다.

탑이 있을 경우, 현재 입력받은 탑의 높이와, 스택의 top에 있는 탑의 높이를 비교한다. 만약 값의 크기가 현재 탑보다 작으면, 스택을 pop하여 다음 값을 다시 비교한다.

top에 저장된 높이 값이 현재 입력받은 높이값보다 같거나 클경우, 혹은 스택이 비었을 경우까지 이를 반복한다. top의 값이 같거나 클 경우에는 top의 인덱스를 출력하고, 비었으면 0을 출력한다.

그 다음에 현재 입력받은 값을 탑의 인덱스와 함께 스택에 push한다.

문제에 제시된 예제를 통해 예를 들어보겠다.

5
6 9 5 7 4

현재 스택은 비어있는 상태이다.

1. 먼저 6을 입력 받는다. 스택을 체크한다. 현재 스택에 삽입된 값은 없다, 콘솔에 '0'을 출력하고, 스택에 탑의 인덱스와 크기를 pair로 묶어 삽입한다.

출력 : 0

스택 : (1,6)

2. 그 다음 9를 입력받는다. 스택을 체크한다. top에 있는 값의 크기는 6이다. 현재 입력받는 9보다 작으므로 스택을 pop한다. 

출력 : 0

스택 :

그리고 다시 스택을 체크한다. 스택이 비어있다. 콘솔에 '0'을 출력하고, 입력받은 값을 삽입한다.

출력 : 0  0

스택 : (2,9)

3. 다음은 5이다. 스택을 체크한다. top에 있는 값은 9이고 현재 입력값보다 크다. top에 있는 인덱스를 출력하고 스택에 입력값을 push한다.

출력 : 0  0  2

스택 : (2,9)  (3,5)

4. 다음은 7이다. 스택을 체크한다. top에 있는 값은 5이고 현재 입력값보다 작다. 스택을 pop한다.

출력 : 0  0  2

스택 : (2,9)

그리고 다시 스택을 체크한다. top에 있는 높이 값은 9이다. 입력값인 7보다 크므로 top의 인덱스를 출력하고 스택에 push한다.

출력 : 0  0  2  2

스택 : (2,9)  (4,7)

5. 마지막으로 4이다. 스택 top을 체크하는데 top의 값은 7이고 입력값보다 크다. 인덱스를 출력하고 스택에 push한다.

출력 : 0  0  2  2  4

스택 : (2,9)  (4,7)  (5,4)

5번 반복했으므로 반복문이 끝나고 프로그램을 종료한다.

즉 스택에는 이전값중의 가장 큰 값과, 현재 값 사이에 있는 값들은 전부 없앤다고 보면 된다.

이를 구현한 코드는 다음과 같다.

#include <cstdio>
#include <stack>
#include <utility>
using namespace std;
int n, k;
stack<pair<int, int> > st;
int main() {
    scanf("%d", &n);
    for (int i = 1; i<=n; i++) {
        scanf("%d", &k);
        while (!st.empty()) {
            //스택의 top이 현재 입력값보다 크다면 신호 수신 가능이므로 
            if (st.top().second > k){
                //top의 위치를 출력하고 반복문을 탈출한다. 
                printf("%d ", st.top().first);
                break;
            }
            st.pop();
        }
        //스택이 비었으면 0을 출력한다. 
        if(st.empty()) printf("0 ");
        //그리고 현재 탑을 스택에 push 
        st.push(make_pair(i, k));
    }
}

[문제 링크]

문제 의도는 스택으로 푸는 문제이지만, 굳이 스택으로 풀지 않아도 되는 문제이다.

그냥 레이저를 만났을 때, 여는 괄호의 갯수 만큼 더해줘도 되지만, 여기서는 스택을 이용해서 풀어보겠다.

이 문제를 풀기 위해선, 닫는 괄호가 나타났을 때, 이 것이 레이저인지, 아니면 파이프의 끝을 나타내는 것인지 구별해야 된다.

구별하는 방법은 정말 쉽다, 닫는 괄호가 나타났을 때, 바로 전 문자를 체크해서 이게 여는 괄호인지 아닌지만 확인하면 된다.

즉 여는 괄호를 만나면 전부 스택에 push하다가, 닫는 괄호를 만나면 스택에서 pop하고 괄호가 레이저면 스택 사이즈만큼 더해주거나, 파이프 끝이면 1만 더해주면 된다.

위 사진으로 예를 들어보자. 

처음에 '('를 만나서 스택에 push한다, 그리고 두번째에 ')'를 만난다. 스택에서 '('를 pop한다. 이전 문자는 '('이므로 레이저이다. 결과값에 스택 사이즈(0)만큼 더해준다.

result += 0

그다음 '('를 4개 만난다. 스택에 '('가 4개 들어가고 스택 사이즈는 4이다. ')'를 만나서 스택을 pop한다. 바로 전이 '('이므로 이는 레이저이다. 결과값에 스택 사이즈(3)만큼 더해준다.

result += 3

바로 다음에 괄호를 다시 여닫고 스택을 그에따라 push,pop해준다. 레이저이므로 스택 사이즈(3)을 다시 더해준다.

result += 3

닫는 괄호를 만난다. 바로 전 문자는 ')'이므로 레이저가 아닌 파이프의 끝이다. 파이프 꼭다리가 남으므로 1을 더해준다.

result +=1

위의 방법을 계속 반복하면 된다. 나머지는 직접 해보자.

이를 구현한 코드는 다음과 같다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;
string str;
int pipe(const string& str){
    stack<char> st;
    int result=0;
    for(int i =0; i<str.length();i++){
        //여는 괄호면 스택에 넣는다. 
        if(str[i]=='(') st.push(str[i]);
        //닫는 괄호면 이 괄호가 레이저인지, 파이프 끝인지 알아본다.
        else{
            st.pop();
            //레이저면 
            if(str[i-1]=='(') 
                result += st.size(); //잘린 갯수 추가. 
            //파이프의 끝이면 
            else result++; //닫혀서 잘려진 갯수 추가. 
        }
    }
    return result;
}
int main(){ 
    cin >> str;
    cout<<pipe(str);
}

[문제 링크]

DP문제이다. 경로 모든 경로의 수를 구하는 미로 찾기와 같은 문제랑 다를게 없는데, 거기서 내리막으로만 갈 수 있다는 조건만 주면 되는 문제이다.

맵의 끝에 도달하면 1을 반환하고, 아닐 경우 0을 반환하여 경로의 갯수를 구한다.

밑은 이를 구현한 코드이다.

#include <cstdio>
#include <cstring>
int m,n,arr[501][501];
int relPos[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int cache[501][501]; 
int dp(int y,int x){
    //기저사례 : 끝에 도달했으면 탈출 
    if(y==m && x==n) return 1;  
    int& ret = cache[y][x];
    if(ret!=-1) return ret;
    ret = 0;
    for(int c = 0; c<4; c++){
        int px = x + relPos[c][0];
        int py = y + relPos[c][1];
        //맵을 안넘어서고 내리막이면 
        if(px <=n && py<=m && px>=1 && py>=1&&arr[py][px] < arr[y][x])
            ret +=dp(py,px);
    }
    return ret;
} 
int main(){
    memset(cache,-1,sizeof(cache));
    scanf("%d %d",&m,&n);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&arr[i][j]);
        }
    }
    printf("%d",dp(1,1));
} 

경로 문제를 자주 보다보니 경로 문제는 이제 다 비슷비슷하다는 생각이 든다.

[문제 링크]

DP문제이다. 어려운 문제는 아니고, 다음으로 선택할 수 있는 경로의 경우만 알면 쉽게 풀리는 문제인 것 같다.

자신을 기준으로 상하좌우는 접근할 수 없기 때문에, 대각선에 위치한 스티커나, 대각선에서 오른쪽으로 한칸 옆에 있는 스티커를 다음 경로로 선택하면 된다.

이렇게 모든 점수들을 더한 값 중 최대값을 구하면 되었다.

밑은 이를 구현한 코드이다.

#include <cstdio>
#include <cstring>
#include <algorithm>
int t,n,arr[2][100000],cache[2][100000];
int relPos[4][2] = {{1,1},{1,-1},{2,-1},{2,1}};
int dp(int y, int x){
    //기저사례 : y 끝에 도달했을 때 
    if(x==n-1) return arr[y][x];
    int& ret = cache[y][x];
    if(ret!=-1) return ret;
    ret = 0;    
    for(int i=0;i<4;i++){
        int px = x + relPos[i][0];
        int py = y + relPos[i][1];
        //스티커 범위를 초과하지 않으면 
        if(px<n&&px>=0&&py<2&&py>=0){
            //최대값 구하기, 기존 ret와, 이 값+ 현재 좌표값 
            ret = std::max(ret,dp(py,px)+arr[y][x]);
        }
    }
    return ret;
}
int main(){
    scanf("%d",&t);
    while(t--){
        memset(cache,-1,sizeof(cache));
        scanf("%d",&n);
        for(int y=0;y<2;y++){
            for(int x=0;x<n;x++){
                scanf("%d",&arr[y][x]);
            }
        }
        //(0,0)으로 시작할 때랑, (1,0)으로 시작할때 중 최댓값을 구하여 출력한다.              
        printf("%d\n",std::max(dp(0,0),dp(1,0)));
    
    }   
}

이전에 풀었던 문제인데, 재채점으로 인해 틀렸다하여 다시 풀었던 문제이다.(자료형만 바꿔주니 다시 맞게 나왔다.)

이분법으로 푸는 문제인데 이분 탐색에서 upper bound 방식으로 풀어야 한다.

왜냐하면 필요한 랜선의 길이인 N을 만드는 경우는 엄청 다양하기 때문이다. 그 다양한 길이 중 가장 긴 랜선의 길이를 찾아야한다.

밑은 이 문제의 코드이다.

#include <cstdio>
#include <algorithm>
long long k,n,l[10010], mi=0,m; 
long long bs(long long s, long long e) {
    //이분 탐색을 시작한다.
    while (s<=e) {
        m = (s + e) / 2;
        long long v = 0;
        // 각 종류의 랜선들을 현재의 길로 나눠 갯수를 구한다. 
        for (int i = 0; i < k; i++)
            v += l[i] / m;
            
        //갯수가 '같거나' 크면 m의 값을 1 증가시켜주고 이분탐색을 진행한다. 
        if (v >= n) s = m + 1;
        else if (v < n) e = m - 1;
    }
    return e;   
}
int main() {
    scanf("%lld %lld", &k, &n);
    for (int i = 0; i<k; i++) {
        scanf("%lld", &l[i]);
        mi = std::max(mi, l[i]);
    }
    printf("%lld",(n==1)?mi:bs(1, mi));
}

[문제 링크]

최대 연속합을 구하는 문제이다. 숫자 배열과, 최대 연속합을 저장하는 배열이 따로 더 필요하다.

구하고자 하는 숫자 배열의 가장 끝부터 차례로 내려가며, 최대연속합을 찾고자하는 배열값과, 바로 뒤 배열을 기점으로 하는 최대 연속합과의 합을 비교하여 그 최대값이 최대 연속 합이다.

밑은 예제를 돌렸을 경우의 CACHE 배열의 값이다. 맨 마지막의 CACHE값은 자기 뒤의 값이 없으므로 -1이 된다. 그 다음부터 재귀를 탈출해나가며 최대연속합을 구해나간다.

예를 들면 ARR이 21인 값은, 자신의 값 21과, 바로 뒤를 기점으로하는 최대 연속합과의 합인 21-1=20을 비교해서 큰 값이 그 위치를 기점으로하는 최대 연속합이다.

21인 경우에는 12와, 12+21=33 을 비교해서 큰 값이 그 위치를 기점으로하는 최대 연속합이다. 

즉 이 문제의 점화식은 다음과 같다.

DP(i) = MAX(arr[i], arr[i] + DP(i+1))

위 로직에 전체의 최대연속합을 저장하는 변수를 따로 만들어 답을 구하였다. 밑은 이를 구현한 코드이다.

#include <cstdio>
#include <algorithm>
int n,arr[100001],cache[100001];
int dp(int num){
    //기저 사례  :  마지막에 도달했을 때, 마지막 값을 시작으로 하는 최대 연속합은 자기 자신이므로. 
    if(num==n){
        cache[n] = arr[n];
        return arr[n];  
    } 
    int& ret = cache[num];
    //뒤의 값을 기준으로 하는 최대 연속값을 구하는 재귀 실행. 
    int mx = dp(num+1); 
    //점화식 : 자기 자신과, 바로 뒤의 값을 시작으로하는  최대 연속합과의 합중 최대값을 구한다. 
    ret = std::max(arr[num],arr[num]+cache[num+1]);
    //지금까지 구한 연속합중 최대값을 구한다. 
    mx = std::max(mx,ret);
    return mx;   
}
int main(){
    //초기화 
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    //구한 최대 연속합중 최대값을 찾는다. 
    printf("%d",dp(1));
}

막상 풀고 보니 재귀로 푸는 것 보다 반복문이 훨씬 깔끔하게 나올 것 같았다. 밑은 재귀를 쓰지 않고 for문으로만 구한 코드이다.

#include <cstdio>
#include <algorithm>
int n,arr[100001],cache[100001];
int dp(){
    //가장 마지막 값은 그 자체가 최대연속합이므로 배열값을 넣어준다. 
    cache[n] = arr[n]; 
    int mx = arr[n];
    for(int i = n-1;i>0;i--){
        //점화식 : 자기 자신과, 바로 뒤의 값을 시작으로하는  최대 연속값과의 합중 최대값을 구한다.
        cache[i] = std::max(arr[i],arr[i]+cache[i+1]);
        //지금까지 구한 연속합중 최대값을 구한다.
        mx = std::max(mx,cache[i]);
    } 
    return mx;
}
int main(){
    //초기화 
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    //구한 최대 연속합중 최대값을 찾는다. 
    printf("%d",dp());
}