Pair, Backtracking

재귀호출을 구현할 때는 그림을 그려서 해주는 것이 실수를 줄일 수 있다.

주사위의 모든 경우 출력의 경우 주사위의 갯수가 정해져있으면 그냥 중복 for문 하면 되지만, 갯수가 정해지지 않았다면 재귀를 써야 한다.

 

완전탐색의 경우 가지치기를 통해서 속도를 끌어올려야 한다.

* 작은 팁: max, min 알고리즘 헤더 안의 함수로 구할 수 있음

abs() 절댓값 함수

 

Pair

Pair : 변수 2개를 편하게 묶어서 사용할 수 있다.

그렇지만 2개 이상이 되면 가독성이 떨어져서 STL의 장점을 잃음.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    pair<int, int> t = {3, 4};
    t.first = 5;
    t.second = 17;
    cout << t.first << ' ' << t.second;
    return 0;
}

Backtracking

 

브루트포스 : 모든 경우의 수를 다 해보는 경우 

n이 정해져 있으면 for문 사용, 그렇지 않다면 재귀를 사용

 

Backtracking은 완전탐색에서 가지치기를 하는 것이다. 브루트포스안에 백트래킹이 포함되는 관계이다.

 

#include <iostream>
using namespace std;
int cnt;
void backtracking(int level, int sum)
{
    if(sum > 10) return;
    if(level == 4)
    {
        if(sum == 10)
            cnt++;
        return;
    }
    for(int i=1; i<5; i++)
    {
        backtracking(level+1, sum + i);
    }
}
int main()
{
    backtracking(0, 0);
    cout << cnt;
    return 0;
}

5개 숫자의 합이 10이 되는 모든 경우 출력

path 배열에 기록하기

#include <iostream>
using namespace std;
int cnt;
char path[5];
void backtracking(int level, int sum)
{
    if(sum > 10) return; // 가지치기
    if(level == 5)
    {
        if(sum == 10)
        {
            cout << path << '\n';
            cnt++;
        }
        return;
    }
    for(int i=1; i<5; i++)
    {
        path[level] = i + '0';
        backtracking(level+1, sum + i);
        path[level] = 0; // 없어도 되지만 디버깅을 용이하게 하기 위해서 사용
    }
}
int main()
{
    backtracking(0, 0);
    cout << cnt;
    return 0;
}

1~4까지 같은 수를 사용하지 않고 10 만들기 

가능한 경우가 없으므로 0이 나온다

#include <iostream>
using namespace std;
int cnt, used[4];
char path[5];
void backtracking(int level, int sum)
{
    if(sum > 10) return; // 가지치기
    if(level == 5)
    {
        if(sum == 10)
        {
            cout << path << '\n';
            cnt++;
        }
        return;
    }
    for(int i=1; i<5; i++)
    {
        if(used[i] == 1) continue;
        used[i] = 1;
        path[level] = i + '0';
        backtracking(level+1, sum + i);
        path[level] = 0; // 없어도 되지만 디버깅을 용이하게 하기 위해서 사용
        used[i] = 0;
    }
}
int main()
{
    backtracking(0, 0);
    cout << cnt;
    return 0;
}

최대 값 찾기

#include <iostream>
using namespace std;
int map[5][4] = {
    3, 2, 4, 1,
    0, 1, 0, 5,
    2, 0, 3, 0,
    5, 4, 0, 2,
    2, -5, 0, 3
}, maxNum = -21e8, direct[3][2] = {1, -1, 1, 0, 1, 1}, path[5];

void backtracking(int nowY, int nowX, int level, int sum)
{
    if(level == 5)
    {
        if(sum > maxNum)
            maxNum = sum;
        return;
    }
    for(int i=0; i<3; i++)
    {
        int dy = nowY + direct[i][0];
        int dx = nowX + direct[i][1];
        if(dy < 0 || dx < 0 || dy > 4 || dx > 3) continue;
        if(map[dy][dx] == 0) continue;
        path[level] = map[dy][dx];
        backtracking(dy, dx, level+1, sum+map[dy][dx]);
        path[level] = 0;
    }
}
int main()
{
    for(int i=0; i<4; i++)
    {
        path[0] = map[0][i];
        backtracking(0, i, 1, map[0][i]);
        path[0] = 0;
    }
    cout << maxNum;
    return 0;
}

또 다른 방식

#include <iostream>
using namespace std;
int map[5][4] = {
    3, 2, 4, 1,
    0, 1, 0, 5,
    2, 0, 3, 0,
    5, 4, 0, 2,
    2, -5, 0, 3
}, maxNum = -21e8, direct[3] = {-1, 0, 1};

void back(int now, int level, int sum)
{
    if(level == 5)
    {
        if(maxNum < sum)
            maxNum = sum;
        return;
    }
    for(int i=0; i<3; i++)
    {
        int dx = now + direct[i];
        int dy = level;
        if(dx < 0 || dx > 3) continue;
        if(map[dy][dx] == 0) continue;
        back(dx, dy + 1, sum+map[dy][dx]);
    }
}
int main()
{
    back(0, 0, 0);
    back(1, 0, 0);
    back(2, 0, 0);
    back(3, 0, 0);
    
    cout << maxNum;
    return 0;
}

 

DP가 아니라 백트래킹으로 돌다리 건너기 풀기

경로와 최대점수 출력

#include <iostream>
#include <cstring>
using namespace std;
int vect[20] = {1, 3, -1, 6, -3, -1, 5, 100, 3, 2, 5, 1}, direct[3] = {2, 3, 5}, maxNum = -21e8, path[11], maxPath[11];

void back(int sum, int now, int level)
{
    if(now > 11)
    {
        if(sum > maxNum)
        {
            memcpy(maxPath, path, 11 * 4);
            maxNum = sum;
        }
        return;
    }
    for(int i=0; i<3; i++)
    {
        path[level] = vect[now+direct[i]];
        back(sum + vect[now+direct[i]], now + direct[i], level + 1);
        path[level] = 0;
    }
}

int main()
{
    int k = 0;
    back(1, 0, 0);
    cout << maxNum << '\n';
    while(1)
    {
        cout << maxPath[k++] << ' ';
        if(maxPath[k] == 0) break;
    }
    return 0;
}

 

동전 최소 갯수 구하기

#include <iostream>
using namespace std;
int target = 80;
int minCnt = 21e8, num[3] = {10, 40, 50};

void back(int level, int sum)
{
    if(sum > 80 || level >= minCnt)
        return;
    if(sum == target)
    {
        if(minCnt > level)
            minCnt = level;
        return;
    }
    for(int i=0; i<3; i++)
    {
        back(level+1, sum + num[i]);
    }
}
int main()
{
    back(0, 0);
    cout << minCnt;
    return 0;
}

 

순열과 조합

순열은 used배열만 사용하면 쉽게 할 수 있다. 

 

조합은 자신 이전 것을 선택하지 않도록 하여 중복을 제거한다.

#include <iostream>
using namespace std;
char name[6] = "ATKBS", used[5], path[3];

void run(int level, int now)
{
    if(level == 3)
    {
        cout << path << '\n';
        return;
    }
    for(int i=now; i<5; i++)
    {
        if(used[i] == 1) continue;
        
        path[level] = name[i];
        run(level+1, i+1);
        path[level] = 0;
        
    }
}
int main()
{
    
    run(0, 0);
    
    return 0;
}

주사위 3개 있을 때 모든 경우의 수 출력

#include <iostream>
using namespace std;
char name[3];
void back(int level)
{
    if(level == 3)
    {
        cout << name << '\n';
        return;
    }
    for(int i=1; i<7; i++)
    {
        name[level] = i + '0';
        back(level+1);
    }
}
int main()
{
    back(0);
    return 0;
}

주사위 3개로 순열 만들기

#include <iostream>
using namespace std;
char name[3], used[6];
void back(int level)
{
    if(level == 3)
    {
        cout << name << '\n';
        return;
    }
    for(int i=1; i<7; i++)
    {
        if(used[i] == 1) continue;
        used[i] = 1;
        name[level] = i + '0';
        back(level+1);
        used[i] = 0;
    }
}
int main()
{
    back(0);
    return 0;
}

 

주사위 중복 조합

#include <iostream>
using namespace std;
char name[3], used[6];
void back(int level, int now)
{
    if(level == 3)
    {
        cout << name << '\n';
        return;
    }
    for(int i=now; i<7; i++)
    {
        
        
        name[level] = i + '0';
        back(level+1, i);
    }
}
int main()
{
    back(0, 1);
    return 0;
}

조합은 중복조합에서 used배열로 중복만 제거해주면 된다.