개발뚱땅

7.1 도입

Divide & Conquer은 유명한 알고리즘 패러다임이다.

분할정복 알고리즘은 문제를 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다.

일반적인 재귀호출과 다른 점은 문제를 한조각과 나머지로 나누는 대신, 비슷한 크기의 부분문제로 나누는 것이다.

분할정복을 사용하는 알고리즘은 대개 세가지의 구성요소를 갖는다.

• 문제를 더 작은 문제로 분할하는 과정 (divide)
• 각 문제에 대해 구한 답을 원래 문제의 답으로 병합하는 과정 (merge)
• 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case)

분할정복으로 문제를 풀기 위해서는 문제에 몇가지 특성이 있어야 한다.

문제를 둘 이상의 부분 문제로 나누는 것이 자연스러워야하며, 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야한다.

분할정복의 장점은 같은 작업을 더 빠르게 처리하는 것이다.

7.2 문제: 쿼드 트리 뒤집기 (문제 ID: QUADTREE, 난이도: 하)

쿼드 트리는 대량의 좌표 데이터를 메모리안에 압축해 저장하기 위해 사용하는 기법이다.

주어진 공간을 4개로 분할해 재귀적으로 표현하기에 쿼드 트리라는 이름이 붙었다.

가장 대표적인 사용처는 흑백 이미지를 압축해서 표현하는 것이다.

쿼드 트리는 2ⁿ X 2ⁿ 크기의 흑백 이미지를 다음과 같이 문자열로 압축한다.

이미지의 모든 픽셀이 검은 색인 경우 쿼드 트리로 변환한 결과는 그림의 크기와 관계없이 b가 된다.

이미지의 모든 픽셀이 흰 색인 경우 쿼드 트리로 변환한 결과는 그림의 크기와 관계없이 w가 된다.

모든 픽셀이 같은 색이 아니라면, 쿼드 트리는 이 이미지를 가로 세로로 각각 2등분해 4개의 조각으로 쪼갠 뒤 각각을 쿼드 트리 압축한다. 압축 결과는 x(좌상단 압축결과)(우상단 압축결과)(좌하단 압축결과)(우하단 압축결과)가 된다.

쿼드트리로 압축된 흑백 이미지가 주어졌을 때, 이 이미지를 상하로 뒤집은 이미지를 쿼드트리 압축하여 출력하는 프로그램을 작성하시오.

시간 및 메모리 제한

프로그램은 1초안에 실행되어야 하며, 64MB이하의 메모리를 사용해야 한다.

입력

첫 줄에 테스트 케이스의 개수 C(C≤50)가 주어진다. 그 후 C줄에 하나씩 쿼드 트리로 압축된 텍스트가 주어진다. 문자열의 길이는 1000이하이고, 원본 이미지의 크기는 2^20 X 2^20을 넘지 않는다.

출력

상하로 뒤집은 쿼드트리 텍스트를 출력한다.

7.3 풀이: 쿼드 트리 뒤집기

문제를 푸는 가장 무식한 방법은 쿼드 트리로 실제 이미지를 얻고 상하반전한 뒤 다시 쿼드트리 압축하는 것이다.

그러나 제한에 걸려 이 방법을 사용할 수 없다.

이런경우 선택가능한 방법은 두가지이다.

• 큰 입력에 대해서도 동작하는 효율적인 알고리즘을 처음부터 새로 만들기
• 작은 입력에 대해서만 동작하는 단순한 알고리즘으로부터 시작해서 최적화해 나가기

시행착오와 경험이 중요하다.

쿼드 트리 압축 풀기

쿼드 트리가 재귀적으로 정의되어 있기 때문에 쿼드 트리를 압축하거나 해제하는 과정은 재귀 호출로 구현하는 것이 자연스럽다.

문자열 s의 압축을 해제해서 배열에 저장하는 함수 decompress()를 구현하자.

base case는 s의 첫 글자가 w나 b인 경우이다. 이 경우 배열에 저장 후 종료한다.

첫 글자가 x라면 s의 나머지 부분을 넷으로 쪼개 재귀 호출한다.

이 때 각 부분이 배열의 어느 부분에 저장되어야 하는지 지정하는 위치 오프셋도 전달해야한다.

char decompressed[MAX_SIZE][MAX_SIZE];

void decompress(const string& s, int y, int x, int size);

압축 문자열 분할하기

구현을 시작하면 s의 나머지 부분을 넷으로 쪼개기가 까다롭다는 사실을 깨닫게 된다.

각 부분의 길이가 일정하지 않기 때문이다.

이를 해결할 수 있는 첫 번째 방법은 주어진 위치에서 시작하는 압축결과의 길이를 반환하는 함수 getChunkLength()를 만드는 것이다.

s[0]이 x라고 하면 왼쪽 위 조각을 나타내는 부분은 항상 s[1]에서부터 시작한다.

이 때 getChunkLength(s, 1)이 해당 부분의 길이를 반환하도록 하는 것이다. 그 후 반환한 값에 이전 위치를 더해서 다음 부분을 구할 수 있다.

이 함수를 작성하는 것은 어렵지 않지만, 비슷한 일을 하는 함수를 나누어 작성하는 것이 마음에 들지 않을 것이다.

이럴 때 유용한 패턴은 s를 미리 쪼개는 것이 아니라 decompress()함수에서 '필요한 만큼 가져다 쓰도록' 하는 것 이다.

s를 통째로 전달하는 것이 아니라, s의 한 글자를 가리키는 포인터를 전달한다.

함수 내에서는 한 글자를 검사할 때마다 포인터를 앞으로 옮긴다.

char decompressed[MAX_SIZE][MAX_SIZE]
void decompress(string::iterator& it, int y, iny x, int size){
    //한글자를 검사할 때마다 반복자를 한 칸 앞으로 옮긴다.
    char head = *(it++);
    //base case: 첫 글자가 b또는 w인경우
    if(head == 'b' || head == 'w'){
        for(int dy = 0; dy < size; ++dy)
            for(int dx = 0; dx < size; ++dx)
                decompressed[y+dy][x+dx] = head;
    }
    else{
        //네 부분을 순서대로 압축 해제한다.
        int half = size/2;
        decompress(it, y, x, half);
        decompress(it, y, x+half, half);
        decompress(it, y+half, x, half);
        decompress(it, y+half, x+half, half);
    }
}

압축 다 풀지 않고 뒤집기

string reverse(string::iterator& it){
    char head = *iter;
    ++iter;
    
    if(head == 'b'|| head == 'w')
        return string(1, head);
    string upperLeft = reverse(it);
    string upperRight = reverse(it);
    string lowerLeft = reverse(it);
    string lowerRight = reverse(it);
    //각각 위와 아래 조각들의 위치를 바꾼다.
    return string("x") + lowerLeft + lowerRight + upperLeft + upperRight;
}

카라츠바

개관

알고리즘을 고안하는 것은 까다롭다.

알고리즘을 고안하기 위해서는 문제의 특성을 이해하고, 동작 시간과 사용하는 공간 사이의 상충 관계를 이해해야 하며, 적절한 자료구조를 선택할 줄 알아야 한다.

알고리즘 설계 패러다임은 문제를 해결하기 위해 알고리즘이 채택한 전략이나 관점을 말한다.

06 무식하게 풀기

6.1 도입

가장 많이 하는 실수는 어렵게 푸는 것이다.

전삭학에서 무식하게 푼다는 말은 (부르트 포스) 가능한 모든 경우의 수를 나열해 답을 찾는 것을 말한다.

이런 알고리즘을 가리켜 완전탐색(exhaustive searce)라고 부른다.

컴퓨터의 경우 빠른 연산이 가능하기에 작은 입력에 경우 완전탐색이 빠르고 정확한 풀이일 수 있다.

6.2 재귀 호출과 완전 탐색

재귀 호출

재귀 함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다.

자연수 n이 주어졌을 때 1부터 n까지의 합을 반환하는 함수를 재귀함수로 구현해보자.

//기본 조건 n>=1
//결과 1부터 n까지의 합을 반환
int sum(int n){
    int ret = 0;
    for(int i=1; i<=n; ++i)
        ret += i;
    return ret;
}

int recursiveSum(int n){
    if(n==1) return 1;
    return n + recursiveSum(n-1);
}

n개의 숫자 합을 구하는 작업을 n개의 조각으로 쪼개, 더할 각 숫자가 하나의 조각이 되도록 한다.

모든 재귀함수는 더이상 쪼개지지 않는 최소한의 작업에 도달했을 때 답을 바로 반환하는 조건문을 포함해야한다.

쪼개지지 않는 가장 작은 작업들을 재귀함수의 기저 사례(base case)라고 한다.

재귀호출은 문제의 특성에 따라 코딩을 간편하게 해준다.

예제: 중첩 반복문 대체하기

0부터 n까지 번호의 카드 중에서 네 개를 고르는 모든 경우를 출력하는 코드를 작성해보자.

for(int i=0; i<n; ++i)
    for(int j=i+1; j<n; ++j)
        for(int k=j+1; k<n; ++k)
            for(int l=k+1; l<n; ++l)
                cout<<i<<" "<<j<<" "<<k<<" "<<l<<endl;

4중 포문을 써서 구현할 수 있다. 하지만 7개를 고르는 경우라면?..

이런경우 재귀 호출은 간결하고 유연한 코드를 작성할 수 있게 해준다.

위 문제의 경우 네개의 조각으로 나눌 수 있다.

각 조각에서 하나의 원소를 고른다. 원소를 고른 뒤, 남은 원소들을 고르는 작업을 재귀함수로 구현한다.

남은 원소를 고르는 작업을 다음과 같은 입력들의 집합으로 정의할 수 있다.

• 원소들의 총 개수
• 더 골라야 할 원소들의 개수
• 지금까지 고른 원소들의 번호

//n은 전체 원소의 수
//picked는 지금까지 고른 원소들의 번호
//toPick은 더 고를 원소의 수

void pick(int n, vector<int>& picked, int toPick){
    //base case:더 고를 원소가 없을 때 고른 원소들을 출력한다.
    if(toPick == 0){printPicked(picked);return;}
    
    //고를 수 잇는 가장 작은 번호를 계산한다.
    int smallest = picked.empty() ? 0 : picked.back()+1;
    //이 단계에서 원소 하나를 고른다.
    for(int next = smallest; next<n; ++next){
        picked.push_back(next);
        pick(n, picked, toPick - 1);
        picked.pop_back();
     }
 }

재귀 호출을 이용하면 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성할 수 있다.

때문에 재귀 호출은 완전 탐색을 구현할 때 아주 유용한 도구이다.

완전탐색 레시피

1. 완전탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다.

최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠한다.

만약 시간안에 계산할 수 없다면 다른 설계 패러다임을 적용해야한다.

2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다. 각 선택은 답의 후보를 만드는 과정의 한 조각이 된다.

3.그중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀호출을 통해 완성한다.

4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우에는 답을 생성했으므로, 이것을 기저 사례로 선택해 처리한다.

이론적 배경: 재귀 호출과 부분 문제

문제와 부분 문제의 정의를 알아야한다.

이 정의는 동적계획법, 분할정복 같은 디자인 패러다임을 설명하는데 사용된다.

쉽게 생각하는 직관과는 다르다.

문제를 여러 조각으로 나누었을 때 조각들을 부분문제라고 할 수 있다.

나의 정리

부분으로 조각내고 각 케이스 별로 만들어서 케이스의 끝인 경우 문제의 정답인지 확인 후 정답인 경우 반환하면 된다.

그 전에 나오면 안되는 예외의 경우 함수 내에서 더이상 진행되지 않도록 처리.

6.7 최적화 문제 (Optimization problem)

문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아내는 문제를 최적화 문제라고 한다.

n개의 사과 주에서 r개를 골라서 무게의 합을 최대화하는 문제, 가장 무거운 사과와 가장 가벼운 사과의 무게 차이를 최소화 하는 문제 등은 최적화 문제가 된다.

사과를 고르는 방법은 여러 가지인데, 이 중 특정 기준에의해 가장 좋은 답을 고르는 문제이기 때문이다.

최적화 문제는 우리 생활과 밀접하다. 세상에는 효율적인, 최대의, 최소의 값을 찾아야하는 경우가 많다.

때문에 최적화 문제는 중요한 주제 중 하나이다.

예제: 여행하는 외판원 문제

어떤 나라에 n(2≤n≤10)개의 큰 도시가 있다고 하자.

한 영업 사원이 한 도시에서 출발해 다른 도시들을 전부 한 번씩 방문한 뒤 시작 도시로 돌아오려고 한다.

문제를 간단히 하기 위해, 각 도시는 모두 직선 도로로 연결되어 있다고 한다.

이 때 이동 거리는 도시 방문 순서에 따라 달라진다.

무식하게 풀 수 있을까?

완전 탐색으로 문제를 풀기 위한 첫 번째 단계는 시간 안에 답을 구할 수 잇는지 확인하는 것이다.

시작한 도시로 돌아오는 경로를 찾기에 경로의 시작점은 신경쓰지 않아도 된다.

시작 도시를 정하고 나머지 도시의 경우의 수는 (n-1)!가 된다.

도시 10개의 경우 9!은 362,880개가 되어 1초안에 처리할 수 있다.

재귀 호출을 통한 답안 생성

int n;//도시의 수
double ist[MAX][MAX];//두 도시 간의 거리를 저장하는 배열
//path는 지금까지 만든 경로
//vidited는 각 도시의 방문여부
//currentLength는 지금까지 만든 경로의 길이

//나머지 도시들을 모두 방문하는 경로들 중 가장 짧은 것의 길이를 반환한다.
double shortestPath(vector<int>& ath, vector<bool>& visited, double currentLength)
{
    //base case - 모든 도시를 방문한 경우 시작 도시로 돌아가고 종료한다.
    if(path.size() == n)
        return currentLength + dist[path[0]][path.back()];
    
    double ret = INF;
    //다음 방문할 도시를 전부 시도해 본다.
    for(int next = 0; next < n; ++next)
    {
        //방문할 곳이 이미 방문한 곳이라면 통과
        if(visited[next]) continu;
        //방문한 곳이 아니라면 방문
        int here = push.back();
        path.push_back(next);
        visited[next] = true;
        
        //나머지 경로를 재귀 호출을 통해 완성하고 가장 짧은 경로의 길이를 얻는다.
        double cand = shortestpath(path, visited, currentLength + dist[here][next]);
        //나머지 경로를 반복해서 받아오면서 최소 길이를 찾는다.
        ret = min(ret, cand);
        
        //다른 경우의 수를 찾아야 하므로 경로에서 제거한다.
        visited[next] = false;
        path.pop_back();
    }
    return ret;
}

6.8 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)

그림과 같이 4X4개의 격자 형태로 배치된 열여섯 개의 시계가 있다.

이 시계들은 12, 3, 6, 9시를 가리키고 있다.

이 시계들이 모두 12시를 가리키도록 바꾸려한다.

시계의 시간을 조작하는 방법은 열개의 스위치들을 조작하는 것으로, 각 스위치는 누를 때 마다, 해당 스위치와 연결된 시계들의 시간은 3시간 후로 움직인다.

시계 순서는 위에서 아래로, 왼쪽에서 오른쪽으로 매겨진다.

모든 시계를 12시로 돌리기 위해 최소한 스위치를 몇 번 눌러야 할지 구하시오.

시간 및 메모리 제한

프로그램은 10초 안에 실행되어야 하며, 64MB 이하의 메모리를 사용해야한다.

입력

첫번째 줄에 테스트 케이스 개수 C가 주어진다. (C≤30)

각 테스트 케이스는 한줄에 16개의 정수로 주어진다. 각 정수는 시계를 의미하며 정수의 값은 3, 6, 9, 12중 하나로 표현한다.

출력

각 케이스당 정수 하나를 한줄에 출력한다. 정수 값은 스위치 누르는 횟수이다.

시계들을 12시로 만드는 것이 불가능 하다면, -1을 출력한다.

예제 입력

2

12 6 6 6 6 612 12 12 12 12 12 12 12 12 12

12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6

예제 출력

2

9

6.9 풀이: 시계 맞추기

문제 변형하기

문제 그대로 풀려고 하면 복잡하다.

문제의 특성을 이용해 단순화하면 완전탐색으로 해결할 수 있다.

이 문제에서 깨달아야 할 것은 스위치를 누르는 순서는 중요하지 않다는 것이다.

순서를 바꾼다고 결과가 달라지지 않는다.

구해야할 것은 각 스위치를 몇번 누를 것인가 이다.

이렇게 문제를 바꿔도 완전탐색으로 구할 수 없다.

완전 탐색 알고리즘을 사용하려면 스위치를 누르는 횟수의 모든 조합을 하나하나 열거할 수 있어야 하는데,

각 스위치를 몇번 누르는 지는 상관이 없기에 조합의 수가 무한하기 때문이다.

시계는 12시간이 지나면 제자리로 돌아온다는 점을 이용하면 무한한 조합의 수를 유한하게 바꿀 수 있다.

어떤 스위치를 네번 누르면 연결된 시계는 모두 12시간 앖으로 이동하니 하나도 누르지 않은 것과 같다.

따라서 어떤 스위치건 3번 이상 누를 일이 없다.

따라서 각 스위치를 누르는 횟수는 0에서 3사이의 정수이다.

10개의 스위치가 있으니 전체 경우의 수는 4^10이 된다.

완전탐색 구현하기

const int INF = 9999, SWITCHES = 10, CLOCKS = 16;
//linked[i][j]가 x인 경우는 i번 스위치와 j번 시계가 연결되어 있다는 의미
//linked[i][j]가 .인 경우는 연결되어 있지 않다는 의미
const char linked[SWITCHES][CLOCKS+1] = {
   //0123456789012345
    "xxx.............", 
    "...x...x.x.x....",
    "....x.....x...xx",
    "x...xxxx........",
    "......xxx.x.x...",
    "x.x...........xx",
    "...x..........xx",
    "....xx.x......xx",
    ".xxxxx..........",
    "...xxx...x...x.."
};

//모든 시계가 12시를 가리키는지 확인한다.
bool areAligned(const vector<int>& clocks);

//swtch번 스위치를 누른다.
void push(vector<int>& clocks, int swtch){
    for(int clock = 0; clock < CLOCKS; ++clock)
        if(linked[swtch][clock] == 'x'){
            clocks[clock] += 3;
            if(clocks[clock] == 15) clocks[clock] = 3;
        }
}

//clocks는 현재 시계들의 상태
//swtch는 이번에 누를 스위치의 번호
//남은 스위치를 눌러서 clocks를 12시로 맞출 수 있는 최소 횟수를 반환한다.
//불가능하다면 INF이상의 큰 수를 반환한다.
int solve(vector<int>& clocks, int swtch){
    //끝까지 탐색한 경우 시계들의 상태를 확인
    if(swtch == SWITCHES) return areAlingned(clocks) ? 0:INF;
    
    //이 스위치를 번 누르는 경우부터 세번 누르는 경우까지 모두 시도한다.
    int ret = INF;
    for(int cnt = 0; cnt < 4; ++cnt) {
        ret = min(ret, cnt + solve(clocks, swtch + 1));
        push(clocks, swtch);
    }
    
    //push()가 4번 호출되어 초기상태와 같아진다.
    return ret;
}

6.10 많이 등장하는 완전 탐색 유형

모든 순열 만들기

서로 다른 N개의 원소를 일렬로 줄 세운 것을 순열이라한다.

자주 볼 수 있는 유형이다.

가능한 순열의 수는 N!인데, N이 10을 넘어간다면 시간 안에 모든 순열을 생성하기 어려워져, 완전 탐색이 아닌 다른 방법을 찾아야한다.

C++ 사용시 유리하다.

STL에 포함된 next_permutation()함수에서 모든 순열을 순서대로 생성하는 작업을 해준다.

다른 언어에서는 직접 순열을 만들어야 한다.

모든 조합 만들기

서로 다른 N개의 원소 중에서 R개를 순서 없이 골라낸 것을 조합이라고 한다.

nCr의 경우의 수가 나온다.

위에서 6.2의 pick()함수처럼 구현하면 된다.

2ⁿ가지 경우의 수 만들기

n개의 질문에 대한 답이 예/아니오 중의 하나라고 할 때 존재할 수 있는 답의 경우의 수는 2ⁿ가지이다.

흔한 문제이며, 각 조합을 하나의 n비트 정수로 표현한다고 생각하면 1차원 for문으로 모두 시도할 수 있다.

이것은 뒤에서 기술한다.

복습

완전 탐색 레시피

1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수에 정확히 비례한다.

2. 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.

3. 그 중 하나의 조각을 선택해 답의 일부를 만들고 나머지 답을 재귀 호출을 통해 완성한다.

4. 조각이 하나밖에 남지 않은 경우, 혹은 하나도 남지 않은 경우 답을 생성 한 것이니, 기저 사례로 처리한다.

즉, 답을 만드는 과정을 나누고 재귀로 답의 일부를 만들고 나머지를 재귀 호출로 완성한다.

결과가 나온 경우 처리.

기저 사례

나누어서 처리

재귀

처리된 것과 처리안된 것을 나누어서 관리.

개관

어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법을 알고리즘이라 한다.

알고리즘은 알고리즘이 사용하는 시간과 공간으로 평가할 수 있다.

04 알고리즘의 시간 복잡도 분석

시간복잡도란 가장 널리 사용되는 알고리즘의 수행 시간 기준으로, 알고리즘이 실행되는 동안 수행하는 기본적인 연산의 수를 입력의 크기에 대한 함수로 표현한 것.

보통 빅오 표기법을 이용해 표현한다.

주먹구구 수행시간 짐작

입력의 크기를 시간 복잡도에 대입해서 얻은 반복문 수행 횟수에 대해, 1초당 반복문 수행 횟수가 1억(10^8)을 넘어가면 시간 제한을 초과할 가능성이 있다.

주먹구구는 주먹구구이다.

실제 내부 반복문은 더 높을 수 있다. 

파일 입출력, 실수 연산이 많다면 더 오래걸린다.

메모리 사용 패턴이 복잡한경우 더 빨라질 수 있다. 캐시 사용.

언어와 컴파일러 차이로 속도가 달라진다.

하드웨어 차이.

실제 적용

1차원 배열에서 연속된 부분 구간 중 그 합이 최대인 구간을 찾는 문제.

예를 들어 [-7, 4, -3, 6, 3, -8, 3, 4]에서 최대 합을 갖는 부분 구간은 [4, -3, 6, 3]으로 그 합은 10이다.

첫번째, 주어진 배열의 모든 부분 구간을 순회하면서 그 합을 계산하는 알고리즘.

가장 무식한 방법

//numeric_limits는 해당 자료형의 표현 한계치를 구할 때 사용한다.
//아래 경우에는 int의 최소 표현 값을 반환한다.
const int MIN = numeric_limits<int>::min();

//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도O(N³)
//비효율적인 최대합 구하는 알고리즘
//모든 경우의 수를 다 계산해서 구한다.
int inefficientMaxSum(const vector<int>& A){
    int N = A.size(), ret = MIN;
    for(int i=0; i<N;++i)
        for(int j=i; j<N; ++j)
        {
            //구간 A[i..j]의 합을 구한다.
            int sum = 0;
            for(int k=i; k<=j; ++k)
                sum += A[k];
            ret = max(ret, sum);
        }
    
    return ret;
}

sum을 구할 때, 처음부터 더해주는 부분이 중복된다.

sum을 구할 때 처음부터 다시 구하지 않도록 수정한다.

//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간복잡도:O(N²)
int betterMaxSum(const vector<int>& A)
{
    int  = A.size(), ret = MIN;
    for(int i=0; i<N; ++i)
    {
        int sum = 0;
        for(int j = i; j <N; ++j)
        {
            sum += A[j];
            ret = max(ret, sum);
        }
    }
    return ret;
}

 순차적으로 더 하면서 for문이 하나 사라졌다.

분할 정복 기법을 이용하면 더욱 빠른 시간에 동작하는 알고리즘을 설계할 수 있다.

입력받은 배열을 우선 절반으로 잘라 왼쪽 배열과 오른쪽 배열로 나눈다.

정답은 왼쪽 배열에 있을 수도, 오른쪽에 있을 수도, 두배열 사이에 걸쳐있을 수도 있다.

각 경우의 답을 재귀함수와 탐욕법을 이용해서 계산하면, 분할 정복 알고리즘이 된다.

//A[lo..hi]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도 O(N*logN)
int fastMaxSum(const vector<int> &A, int lo, int hi)
{
    //기저 사례: 구간의 길이가 1인 경우. 하나짜리.
    if(lo == hi) return A[lo];
    
    //배열을 A[lo..mid], A[mid+1..hi]로 나눈다.
    int mid = (lo+hi)/2;
    
    //두 부분에 걸쳐있는 경우와 하나에만 속한 경우를 나눠 계산
    
    //두 부분에 모두 걸쳐있는 최대 합 구간을 찾는다.
    //이 구간은 A[i..mid]와 A[mid+1..j] 형태를 갖는 구간의 합으로 이루어진다.
    //중앙은 붙어있어야 하므로 양쪽으로 늘어나면서 최대 값을 구한다.
    
    //A[i..mid] 형태를 갖는 최대 구간을 찾는다.
    int left = MIN, right = MIN, sum=0;
    for(int i = mid; i>=lo; --i)
    {
        sum += A[i];
        left = max(left, sum);
    }
    
    //A[mid+1..j] 형태를 갖는 최대 구간을 찾는다.
    sum = 0;
    for(int j=mid+1; j<=hi; ++j)
    {
        sum += A[j];
        right = max(right, sum);
    }
    
    //최대 구간이 두 조각 중 하나에만 속해 있는 경우의 답을 재귀 호출로 찾는다.
    int single = max(fastMaxSum(A, lo, mid), fastMaxSum(A, mid+1, hi));
    
    //두 경우 중 최대 치를 반환한다.
    return max(left + right, single);
}

이 문제를 선형시간에 푸는 방법은 동적계획법 사용이다.

A[i]를 오른쪽 끝으로 갖는 구간의 최대 합을 반환하는 함수  maxAt(i)를 정의해보자.

A[i]에서 끝나는 최대 합 부분 구간은 항상 A[i] 하나만으로 구성되어 있거나, A[i-1]을 오른쪽 끝으로 갖는 최대 합 부분 구간의 오른쪽에 A[i]를 붙인 형태로 구성되어 있습니다.

A[i]를 오른쪽 끝으로 가져야 하기에.. A[i]혼자거나, A[i] + maxAt(i-1)이다.

따라서 점화식으로 표현하면 다음과 같다.

maxAt(i) = max(A[i], maxAt(i-1) + A[i]) = max(0, maxAt(i-1)) + A[i]

//A[]의 연속된 부분 구간의 최대 합을 구한다. 시간 복잡도:O(N)
int fastestMaxSum(const vector<int>& A)
{
    int N = A.size(), ret = MIN, psum = 0;
    for(int i = 0; i<N; ++i)
    {
        //이전 까지 계산한 값에 현재 요소를 더한 것과 현재 요소를 비교하여 큰 것을 psum이 할당.
        //이전까지 계산한 값+현재 요소가 현재 요소보다 작다면 잘리는 효과.
        psum = max(psum, 0) + A[i];
        //기존 계산 값과, 새로 계산한 값 중 큰 것을 ret에 할당.
        ret = max(psum, ret);
    }
    return ret;
}

4.7 계산 복잡도 클래스: P, NP, NP-완비

계산 복잡도 이론에서는 다항 시간 알고리즘이 존재하는 문제들의 집합을 P 문제라고 한다.

다항시간 알고리즘이 존재하지 않으면 NP.

NP문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미한다.

임의의 NP문제를 다항식 시간 내에 'A' 문제로 환원(reduction 또는 transformation)할 수 있는 경우, 이 'A'문제를 'NP-난해(NP-hard) 문제'라고 부른다. NP-난해 문제 중에는 NP 문제가 아닌 것도 있다.

NP 문제들 중에서 NP-난해 문제인 것을 가리켜 'NP-완전(NP-complete) 문제'라고 부른다. NP-완전 문제를 풀 수 있으면 모든 NP 문제를 풀 수 있게 되는 셈이므로 NP 문제들 중에서는 가장 핵심이 되는 문제들인 셈이다.

05 알고리즘의 정당성 증명

수학적 귀납법과 반복문 불변식

수학적 귀납볍은 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법입니다.

단계 나누기: 증명하고 싶은 사실을 여러 단계로 나눈다.

첫단계 증명: 그 중 첫 단계에서 증명하고 싶은 내용이 성립함을 보입니다.

귀납 증명: 한 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보인다.

반복문 불변식

귀납법은 알고리즘의 정당성을 증명할 때 유용하게 사용되는 기법이다.

반복문 불변식이란 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지 명시하는 조건이다.

1.반복문 진입시에 불변식이 성립함을 보인다.

2.반복문 내용이 불변식을 깨뜨리지 않음을 보인다. 다르게 말하면, 반복문 내용이 시작할 때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다.

3. 반복문 종료 시에 불변식이 성립하면 항상 우리가 정답을 구했음을 보인다.

//(*)불변식은 여기에서 성립해야 한다.
while(조건){
    ..
    //(**)불변식은 여기에서도 성립해야한다.
}

반복문 안에서 변하면 안되는 조건을 어기지 않는지 확인하는 과정이다.

단정문을 통해서 반복문 불변식을 강제할 수 있다.

비둘기집의 원리

비둘기집 원리는 간단하게 말해서 n+1개의 물건을 n개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이기 때문에, 비둘기 집의 원리라고 불린다.

시작 이유

알고리즘 테스트에 대한 공부의 필요성을 느낌.

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략이라는 책으로 시작.

구종만씨가 지음.

개관

개발자의 실력에 따른 생산성의 차이가 크다.

그 이유는 교육과정이 프로그래밍 기술과 지식만 가르치고, 응용할 수 있는 능력을 기르지 못하고 있다.

알고리즘이 생겨난 배경과 설계 시 필요한 통찰을 얻어야한다.

알고리즘의 원칙을 이해하고 변형할 수 있어야 프로그래밍 문제를 풀 수 있다.

이 책은 프로그래밍 대회 문제를 풀며 알고리즘 설계 기법과 자료구조를 직관적으로 이해하고, 알고리즘 문제 해결 능력을 키울 수 있도록 구성되어 있다.

문제를 풀어가면서 개념과 구조를 경험적으로 이해하는 것이 이 책의 목표이다.

요약: 문제를 풀어 알고리즘의 개념을 이해하고 변형할 수 있는 능력을 기르자.

01 문제 해결과 프로그래밍 대회

1.1 도입

프로그래머는 다양하다. 분야간 차이를 뛰어넘는 좋은 개발자의 기준이 있을까?

프로그래밍은 문제해결이다.

프로그래밍을 할 때 여러가지 지식이 사용된다.

언어의 특성

작동 환경에 대한 특성(프로그램이 동작할 하드웨어와 운영체제에 관한 지식)

라이브러리 관련 지식(사용하고 있는 라이브러리들에 대한 유의사항)

가용 메모리

동작 시간 제한

재사용성이 좋은 코드 작성법

많은 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력은 좋은 프로그래머가 되기 위해 필수적이다.

이 책에서는 이런 능력을 문제해결 능력이라고 한다.

사용 언어나 라이브러리, 알고리즘에 대한 지식을 이용해 시스템을 만들어 내는 것이 문제해결능력이다.

1.2 프로그래밍 대회

프로그래밍 대회에 참가하는 것은 문제 해결 기술을 연마하기에 좋은 방법이다.

프로그래밍 대회에서 배울 수 있는 것들

1. 문자열 데이터를 입력하고, 문자열 데이터를 출력한다. 문제해결에만 집중할 수 있다.
2. 시간제한과 메모리 제한이 있다. 알고리즘 설계기법과 자료구조를 사용하는 계기가 된다.
3. 정답과 오답 여부가 명확하다. 정확한 프로그램을 짜는 훈련이 된다.
4. 제출한 코드의 실행 시간이나 메모리 사용량 관련 정보가 제공되어 효율성을 확인할 수 있다.
5. 개발의 작은 부분에 집중해, 좋은 코드 작성에 도움이 된다.
6. 다른 개발자와의 공유로 성장의 계기가 된다.

1.3 책 읽는 방법

7부로 이루어져있다.

1~2부는 기초 지식.

나머지 부분은 알고리즘 설계 기법과 자료구조등 문제 해결에 필요한 기술을 소개한다.

책의 문제는 알고 스팟에서 실제 대회와 비슷한 환경에서 채점 가능.

https://algospot.com/

컴퓨터 공학과 학부생을 타겟.

C++과 STL사용

02 문제 해결 개관

2.1 도입

무작정 풀면 안된다.

2.2 문제 해결 과정

문제 해결 연구의 고전 '어떻게 풀 것인가'에서의 네 단계 문제해결 과정

1. 문제를 이해한다.
2. 어떻게 풀지 계획을 세운다.
3. 계획대로 수행하여 문제를 해결한다.
4. 어떻게 풀었는지 돌아보고, 개선방법을 찾는다.

프로그래밍 대회를 위한 여섯단계 문제 해결 알고리즘

1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할지 계획을 세운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

1단계: 문제를 읽고 이해하기

문제의 요구사항과 제약조건을 정확히 파악해야한다.

2단계: 재정의와 추상화

자신이 다루기 쉬운 개념으로, 문제를 자신의 언어로 풀어 쓰는 것.

문제의 요구를 직관적으로 이해하기 위해 필요하다.

3단계: 계획 세우기

문제를 어떻게 해결할지 결정하고, 사용할 알고리즘과 자료구조를 선택한다.

4단계: 계획 검증하기

바로 구현하는 것이 아니라, 계획 검증이 필요하다.

설계한 알고리즘이 요구조건을 만족시키는지 확인해야한다.

5단계: 계획 수행하기

프로그램을 작성한다.

6단계: 회고하기

장기적인 성장에 영향을 미치는 단계다.

문제를 해결한 과정을 돌아보고 개선하는 과정이다.

문제 해결의 더 좋은 방법을 발견하는 기회이다.

문제를 풀 때마다 코드와 경험을 기록으로 남겨라.

어떻게 접근했는지, 어떻게 풀었는지, 어떤 깨달음이 문제 푸는데 도움을 주었는지 기록하자.

풀지 못한 경우 오답 원인도 작성하자.

오답 기록을 작성하면서 틀리는 부분과 원인을 파악할 수 있다.

그리고 다른 사람의 풀이도 참고, 분석하라.

문제를 풀지 못할 때

초보 수준의 경우 한 문제에 너무 매달려 있지 말라.

단, 다른 사람의 풀이를 참조하는 경우 반드시 복기를 동반해야 한다.

왜 내가 풀지 못 했는가를 살펴봐야한다.

2.3 문제 해결 전략

직관과 체계적인 접근

문제와 답의 구조에 대한 직관의 중요성.

직관은 문제 해결의 알고리즘이 어떤 형태를 가질지 예측할 수 있게 한다.

막막한 문제를 해결하며 경험을 쌓아가야 한다.

막막한 문제는 어떻게 해결해야할 것인가.

체계적으로 백지에서 시작해 해결을 위한 기반을 차근차근 쌓아 올리면서 전진하는 것.

비슷한 문제를 풀어본 적이 있던가?
이전 경험을 활용해 문제를 풀 수 있다.

그러기 위해서 원리를 이해하고 변형할 수 있어야 한다.

문제에 맞는 알고리즘을 적용하기 위해서는 알고리즘의 동작 과정과 원리를 완전히 이해해야 한다.

단순한 방법에서 시작할 수 있을까?

가장 단순히 문제를 해결할 수 잇는 방법을 만들어 본다.

이 방법을 개선하고 참고해서 문제를 풀 수 있다.

위 알고리즘으로 문제를 풀 수 없다 하더라도, 효율성을 파악하는 기준선이 될 수 있다.

예) 완전 탐색->너비우선 탐색->요소 중복 제거 -> 순서 중복 제거 를 통해 경우의 수를 구하는 알고리즘이 개선 될 수 있다.

문제 푸는 과정을 수식화할 수 있을 까?

새로운 방향에서 접근해야 풀리는 문제도 만나게 된다.

손으로 간단한 입력을 직접 해결해 보며 방법을 찾을 수 있음.

문제를 단순화할 수 없을까?

제약조건을 없애거나, 계산해야할 변수를 줄이거나, 차원 수를 낮추거나 하는 방법으로 접근할 수 있음.

그림으로 그려볼 수 있을까?

문제에 관련된 그림을 그려 직관적으로 받아들일 수 있다.

수식으로 표현할 수 있을까?

수식으로 표현하는 하는 것이 도움이 되는 경우도 있음.

문제를 분해할 수 있을까?

더 다루기 쉬운 형태로 문제를 변형.

뒤에서부터 생각해 문제를 풀 수 있을까?

거꾸로 하면 해결이 쉬운 경우가 있음.

순서를 강제할 수 있을까?

순서를 특정지어 중복이 사라진다면 강제할 수 있다.

특정 형태의 답만을 고려할 수 있을까?

순서 강제 기법의 연장선으로 정규화 기법이 있습니다.

정규화란 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것을 그룹으로 묶은 뒤, 각 그룹의 대표들만 고려하는 방법이다.

2.4 더 읽을거리

어떻게 문제를 풀 것인가 (How to solve it)은 문제해결의 고전으로 문제 해결에 있어 다양한 전략들을 나열합니다.

시간나면 읽기.

03 코딩과 디버깅에 관하여

3.1 도입:코딩의 중요성을 간과하지 말라

읽기 쉬운 코드를 작성하라.

가독성이 좋아야 디버깅도 쉽고, 정확하게 작성할 수 있다.

자신의 코드 스타일을 간결하고 일관되게 다듬으려 노력하라.

간결하고 효율적인 프로그램을 작성하는 능력이 중요

3.2 좋은 코드를 짜기 위한 원칙

간결한 코드를 작성하기

코드가 짧을 수록 오타나 버그가 생길 가능성이 줄고, 디버깅도 쉬워진다.

일반적인 프로그래밍과 다르게 테스트에서는 전역변수를 사용하는 경우가 많다.

C/C++ 매크로를 사용해 간결한 코드를 작성하기도 한다.

적극적으로 코드 재사용하기

간결한 코드를 위한 직접적인 방법은 코드를 모듈화 하는 것이다.

반복되는 코드를 함수나 클래스로 분리해 재사용.

이상적인 세계에서는 한 함수가 두 가지 이상의 일을 해서는 안된다고 한다.

입력을 읽어들이는 함수, 입력을 처리하기 쉬운 형태로 바꾸는 함수, 실제 문제를 푸는 함수가 분리되어야 한다는 말이다.

그러나 프로그래밍 대회에서는 엄격히 원칙을 따르지 못한다.

표준 라이브러리 공부하기

기초적인 자료구조를 직접 작성하는 것은 시간낭비이다.

문자열, 동적배열, 스택, 큐, 리스트, 딕셔너리 등의 자료구조와 정렬 등의 표준 라이브러리 사용법을 익히자.

항상 같은 형태로 프로그램을 작성하기

검증된 코드는 같은 형식대로 작성한다.

도구가 아닌 문제에 집중.

일관되고 명료한 명명법 사용하기

네이밍 컨벤션.

함수 이름도 기능을 의미하도록 작성.

모든 자료를 정규화해서 저장하기

같은 자료를 다른 형태로 저장하지 말아야한다.

자료를 표현하는 클래스 생성자나 데이터를 입력받자마자 정규화를 수행하라.

3.3 자주 하는 실수

산술 오버플로우

변수의 표현 범위를 넘어서는 경우

버퍼 오버플로우

배열 범위 밖 원소에 접근하는 오류

일관되지 않은 범위 표현 방식 사용하기

대부분의 프로그래밍 언어는 반열린 구간을 사용한다.

첫번째 값은 집합에 포함하고, 다른하나는 포함하지 않는다.

Off-by-one 오류

계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 코드의 오류를 말한다.

오류를 방지하는 방법은 최소 입력이 주어졌을 때 이 코드가 어떻게 동작할 지를 되새겨 보는 것이다.

컴파일러가 잡아주지 못하는 상수 오타

값 자체를 잘못 써서 생기는 문제.

스택 오버플로우

재귀 호출의 깊이가 너무 깊어지는 경우 생긴다.

지역변수로 선언한 배열이나 클래스 인스턴스가 너무 큰경우 발생할 수도 있다.

때문에 자동으로 힙에 메모리를 할당하는 STL컨테이너를 쓰거나 전역변수를 사용한다.

다차열 배열 인덱스 순서 바꿔 쓰기

평소에는 잘 사용하지 않는 다차원 배열을 사용하면서 순서를 헷갈리는 경우가 있음.

가능한 배열에 접근하는 위치를 통일하는 것이 좋음.

3.4 디버깅과 테스트

디버깅에 관하여

대회에서는 디버거보다 직접 검증하는 것이 더 빠르다.

-작은 입력에 대해 잘 작동되는지 확인하기

-assertion을 쓴다. 주어진 조건이 거짓인 경우 오류를 내고 프로그램이 종료된다.

-프로그램의 계산 중간 결과를 출력한다.

테스트에 관하여

가장 작은 입력, 가장 큰 입력, 예제 입력의 변형 등을 통해 테스트 해보는 것이 좋다.

스캐폴딩 기법.

코드를 개발할 때 뼈대를 잡기 위해 임시로 사용하는 코드.