본문 바로가기
C++/자료구조와 알고리듬

5. Dynamic Programming, Backtracking

by GameStudy 2022. 12. 1.

 

 

5.1 Dynamic Programming

 

5.1-1 Memoization

  Note) 기존의 피보나치 수열 코드

#pragma once

int fibo(int n)
{
    if (1 == n) { return 1; }
    if (2 == n) { return 1; }

    return fibo(n - 1) + fibo(n - 2);
}

 

  Note) 기존 피보나치 수열의 코드를 도식화하면 아래와 같음.

    이 경우, n의 크기가 커지면 커질수록 재귀함수의 호출 횟수가 비약적으로 늘어남.

    그래서 한 번 계산된 피보나치 값은 저장해둔다면, 꽤나 큰 효과를 얻을 수 있음.

    즉, 재귀함수만 사용하는 것이 아닌 저장을 위한 메모리를 적절하게 함께 사용함.

    이때 저장을 위한 메모리 사용 기법을 Memoization이라고 함.

    재귀함수 + Memoization은 결국 Dynamic programming의 기본.

 

  Note) 재귀함수 + Memoization 코드

<hide/>

#include <iostream>
#include <array>

using namespace std;

enum { MAX_SIZE = 1024 }; // 여기서 MAX_SIZE는 문제의 N 값과 동일하게 주면 됨.

array<int, MAX_SIZE> s_arriMemoization;

int Fibonacci(int _iIndex)
{
    if (1 == _iIndex) { return s_arriMemoization[_iIndex] = 1; };
    if (2 == _iIndex) { return s_arriMemoization[_iIndex] = 1; };
    if (0 != s_arriMemoization[_iIndex]) { return s_arriMemoization[_iIndex]; }
    return s_arriMemoization[_iIndex] = Fibonacci(_iIndex - 1) + Fibonacci(_iIndex - 2);
}

int main()
{
    s_arriMemoization.fill(0);

    int n;
    cin >> n;
    cout << Fibonacci(n);

    return 0;
}

 

  Note) 재귀함수 + Memoization 도식화

좌측에서 이미 구해진 f(4)와 f(3) 덕분에 빨간색 부분은 O(1) 처리

 

  Ex) 코드업 3704  

<hide/>

// main.cpp

#include <iostream>

#include "Template1_SimpleRecursion.h"
#include "Template2_TreeRecursion.h"
#include "Practice.h"

using namespace std;

long long int res[1001];

long long int f(int n)
{
    if (1 == n) { return res[1] = 1; }
    if (2 == n) { return res[2] = 2; }
    if (3 == n) { return res[3] = 4; }
    if (n <= 1000 && 0 != res[n]) { return res[n]; }

    return res[n] = f(n - 1) + f(n - 2) + f(n - 3);
}

int main()
{
    int n;
    cin >> n;
    cout << f(n);

    return 0;
}

 

 

 

5.2 Backtracking

 

5.2-1 순열과 조합

  Def) 백트레킹(Backtracking)

    순열과 조합에 관련된 문제들은 백트래킹으로 풀고,

    분할정복이 가능하지만, 재귀 횟수가 고민되는 경우엔 재귀+메모이제이션으로 푼다.     

 

  Def) 중복 순열(Permutation with repetition)

    n개 중에서 r개를 순서가 중요하며, 중복 가능하게 나열한 것을 의미함.

    1개를 뽑았다쳐도, 중복이 가능하기 때문에 다시 n개 중에 고르기 때문에 아래와 같은 공식.

 

  Ex) 1~5가 적혀 있는 숫자 카드가 있다. 이를 중복 허용해서 세 자리 수를 만들어라.

<hide/>

// main.cpp

#include <iostream>
#include <vector>

using namespace std;

void PermutationWithRepetition(int _iN, int _iCurrentR, int _iR, vector<int>& _viInput, vector<int>& _viResult)
{
    if (_iCurrentR == _iR)
    {
        for (int i = 0; i < _iR; ++i)
        {
            cout << _viResult[i] << ' ';
        }
        cout << endl;
        return;
    }
    else
    {
        for (int i = 0; i < _iN; ++i)
        {
            _viResult[_iCurrentR] = _viInput[i];
            PermutationWithRepetition(_iN, _iCurrentR + 1, _iR, _viInput, _viResult);
        }
    }
}

int main(void)
{
    int N, R;
    cin >> N >> R;

    vector<int> viInput;
    for (int i = 0; i < N; ++i)
    {
        viInput.push_back(i + 1);
    }

    vector<int> viResult;
    viResult.resize(R + 1);

    PermutationWithRepetition(N, 0, R, viInput, viResult);

    return 0;
}
<hide/>

// test-case
3 2
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

 

  Def) 순열(Permutation)

    n개 중에서 r개를 순서가 중요하며, 중복 불가능하게 나열한 것을 의미함.

 

  Ex) 1~5번 후보가 있다. 이 중에서 3명의 대표를 뽑는 경우의 수는?

<hide/>

// main.cpp

#include <iostream>
#include <vector>

using namespace std;

void Permutation(int _iN, int _iCurrentR, int _iR, vector<int>& _viInput, vector<int>& _viResult, vector<bool>& _vbVisit)
{
    if (_iCurrentR == _iR)
    {
        for (int i = 0; i < _iR; ++i)
        {
            cout << _viResult[i] << ' ';
        }
        cout << endl;
        return;
    }
    else
    {
        for (int i = 0; i < _iN; ++i)
        {
            if (true == _vbVisit[i])
            {
                continue;
            }
            _viResult[_iCurrentR] = _viInput[i];
            _vbVisit[i] = true;
            Permutation(_iN, _iCurrentR + 1, _iR, _viInput, _viResult, _vbVisit);
            _vbVisit[i] = false;
        }
    }
}

int main(void)
{
    int N, R;
    cin >> N >> R;

    vector<int> viInput;
    for (int i = 0; i < N; ++i)
    {
        viInput.push_back(i + 1);
    }

    vector<int> viResult;
    viResult.resize(R + 1);

    vector<bool> vbVisit;
    vbVisit.resize(N + 1, false);

    Permutation(N, 0, R, viInput, viResult, vbVisit);

    return 0;
}
<hide/>

// test-case
3 2
1 2
1 3
2 1
2 3
3 1
3 2

 

  Ex) 프로그래머스 Level 0 - 외계어 사전  

<hide/>

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void Permutation(int _iN, int _iCurrentR, int _iR, vector<string>& _vstrSpell, vector<string>& _vstrDic, string& _strResult, int& _iAnswer, vector<bool>& _vbVisit)
{
    if (_iCurrentR == _iR)
    {
        if (_vstrDic.end() != find(_vstrDic.begin(), _vstrDic.end(), _strResult))
        {
            _iAnswer = 1;
        }
        return;
    }
    else
    {
        for (int i = 0; i < _iN; ++i)
        {
            if (true == _vbVisit[i])
            {
                continue;
            }
            _vbVisit[i] = true;
            _strResult.replace(_iCurrentR, 1, _vstrSpell[i]);
            Permutation(_iN, _iCurrentR + 1, _iR, _vstrSpell, _vstrDic, _strResult, _iAnswer, _vbVisit);
            _vbVisit[i] = false;
                
        }
    }
}

int solution(vector<string> spell, vector<string> dic) {
    int answer = 2;
    
    int iN = static_cast<int>(spell.size());
    int iR = iN;
    string strResult = "";
    vector<bool> vbVisit;
    vbVisit.resize(iN + 1, false);
    Permutation(iN, 0, iR, spell, dic, strResult, answer, vbVisit);
    
    return answer;
}

 

  Ex) 프로그래머스 Level 0 - 옹알이(1)  

<hide/>

#include <string>
#include <vector>

using namespace std;

void Permutation(int _iN, int _iCurrentR, int _iR, vector<string>& _vstrInput, vector<bool> _vbVisit, string& _strResult, string& _strBabbling, int& _iAnswer)
{
    if (_iCurrentR == _iR)
    {
        if (_strResult == _strBabbling)
        {
            ++_iAnswer;
        }
        return;
    }
    else
    {
        for (int i = 0; i < _iN; ++i)
        {
            if (true == _vbVisit[i])
            {
                continue;
            }
            _vbVisit[i] = true;
            string temp = _strResult + _vstrInput[i];
            Permutation(_iN, _iCurrentR + 1, _iR, _vstrInput, _vbVisit, temp, _strBabbling, _iAnswer);
        
            _vbVisit[i] = false;
        }
    }
}

int solution(vector<string> babbling) {
    int answer = 0;
    
    vector<string> vstrInput = { "aya", "ye", "woo", "ma" };
    vector<bool> vbVisit;
    vbVisit.resize(5, false);
    
    size_t uSizeOfBabbling = babbling.size();
    string strResult = "";
    for (size_t i = 0; i < uSizeOfBabbling; ++i)
    {
        string strBabbling = babbling[i];
        for (size_t j = 1; j <= 4; ++j)
        {
            Permutation(4, 0, j, vstrInput, vbVisit, strResult, strBabbling, answer);    
        }        
    }
    
    return answer;
}

 

  Ex) 프로그래머스 Level1 - 삼총사

<hide/>

#include <iostream>
#include <string>
#include <vector>

using namespace std;

enum { FRIENDS = 3 };

void Combination(int _iCurrentN, int _iN, int _iCurrentR, int _iR, vector<int>& _viInput, vector<int>& _viResult, int& _iAnswer, vector<bool>& _vbVisit)
{
    if (_iCurrentR == _iR)
    {
        int iSum = 0;
        for (int i = 0; i < _iR; ++i)
        {
            iSum += _viResult[i];
        }
        if (0 == iSum)
        {
            ++_iAnswer;
        }
    }
    else
    {
        for (int i = _iCurrentN; i < _iN; ++i)
        {
            if (true == _vbVisit[i])
            {
                continue;
            }
            _vbVisit[i] = true;
            _viResult[_iCurrentR] = _viInput[i];
            Combination(i, _iN, _iCurrentR + 1, _iR, _viInput, _viResult, _iAnswer, _vbVisit);
            
            _vbVisit[i] = false;
        }
    }
}

int solution(vector<int> number) {
    int answer = 0;
    int iN = static_cast<int>(number.size());
    
    vector<int> viResult;
    viResult.resize(iN + 1, 0);
    vector<bool> vbVisit;
    vbVisit.resize(iN + 1, false);
    Combination(0, iN, 0, FRIENDS, number, viResult, answer, vbVisit);
    
    return answer;
}

 

백준2529)

<hide/>

#pragma once

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<char> InputVector;
vector<string> ResultVector;
vector<bool> VisitVector;

int N;
int R;

bool IsValid(char InX, char InOperator, char InY)
{
    if (InX < InY && InOperator == '<')
    {
        return true;
    }
    if (InY < InX && InOperator == '>')
    {
        return true;
    }
    return false;
}

void SimulatePermutation(const size_t CurrentR, string NumberString)
{
    if (R == CurrentR)
    {
        ResultVector.push_back(NumberString);
    }
    else
    {
        for (size_t i = 0; i < N; ++i)
        {
            if (true == VisitVector[i])
            {
                continue;
            }

            if (CurrentR == 0 || IsValid(NumberString[CurrentR - 1], InputVector[CurrentR - 1], i + '0') == true)
            {
                VisitVector[i] = true;
                SimulatePermutation(CurrentR + 1, NumberString + to_string(i + '0'));
                VisitVector[i] = false;
            }
        }
    }
}

void Solve(int InK, const vector<char>& InInequalities)
{
    if (InK <= 1)
    {
        cout << 1 << endl;
        return;
    }

    N = 10;
    R = InK + 1;

    InputVector.assign(R, 0);
    VisitVector.assign(R, false);

    ResultVector.assign(R, "");

    InputVector = InInequalities;

    SimulatePermutation(0, "");

    sort(ResultVector.begin(), ResultVector.end());

    cout << ResultVector[ResultVector.size() - 1u] << endl;
    cout << ResultVector[0u] << endl;

    return;
}

int main() {
    int K;
    cin >> K;
    vector<char> Inequalities(K);

    for (int i = 0; i < K; ++i) {
        cin >> Inequalities[i];
    }

    Solve(K, Inequalities);

    return 0;
}

 

 

  Def) 중복 조합(Combination with repetition)

    n개 중에서 r개를 순서 상관없이, 중복 가능하게 나열한 것을 의미함.

 

  Ex) 1~3번 후보가 있다. 3명 대표를 뽑는다면 각 후보자들이 득표수를 경우의 수로 나타낸다면?

<hide/>

// main.cpp

#include <iostream>
#include <vector>

using namespace std;

void CombinationWithRepetition(int _iCurrentN, int _iN, int _iCurrentR, int _iR, vector<int>& _viInput, vector<int>& _viResult)
{
    if (_iCurrentR == _iR)
    {
        for (int i = 0; i < _iR; ++i)
        {
            cout << _viResult[i] << ' ';
        }
        cout << endl;
        return;
    }
    else
    {
        for (int i = _iCurrentN; i < _iN; ++i)
        {
            _viResult[_iCurrentR] = _viInput[i];
            CombinationWithRepetition(i, _iN, _iCurrentR + 1, _iR, _viInput, _viResult);
        }
    }
}

int main(void)
{
    int N, R;
    cin >> N >> R;

    vector<int> viInput;
    for (int i = 0; i < N; ++i)
    {
        viInput.push_back(i + 1);
    }

    vector<int> viResult;
    viResult.resize(R + 1);

    CombinationWithRepetition(0, N, 0, R, viInput, viResult);

    return 0;
}
<hide/>

//test-cast
3 2
1 1
1 2
1 3
2 2
2 3
3 3

 

  Def) 조합(Combination)

    n개 중에서 r개를 순서 상관없이, 중복 불가능하게 나열한것을 의미함. 

 

  Ex) 1~3번 후보가 있다. 2명의 대표를 뽑는다면? 

<hide/>

// main.cpp

#include <iostream>
#include <vector>

using namespace std;

void Combination(int _iCurrentN, int _iN, int _iCurrentR, int _iR, vector<int>& _viInput, vector<int>& _viResult, vector<bool>& _vbVisit)
{
    if (_iCurrentR == _iR)
    {
        for (int i = 0; i < _iR; ++i)
        {
            cout << _viResult[i] << ' ';
        }
        cout << endl;
        return;
    }
    else
    {
        for (int i = _iCurrentN; i < _iN; ++i)
        {
            if (true == _vbVisit[i])
            {
                continue;
            }
            _viResult[_iCurrentR] = _viInput[i];
            _vbVisit[i] = true;
            Combination(i, _iN, _iCurrentR + 1, _iR, _viInput, _viResult, _vbVisit);
            _vbVisit[i] = false;
        }
    }
}

int main(void)
{
    int N, R;
    cin >> N >> R;

    vector<int> viInput;
    for (int i = 0; i < N; ++i)
    {
        viInput.push_back(i + 1);
    }

    vector<int> viResult;
    viResult.resize(R + 1);

    vector<bool> vbVisit;
    vbVisit.resize(N + 1, false);

    Combination(0, N, 0, R, viInput, viResult, vbVisit);

    return 0;
}
<hide/>

//test-case
3 2
1 2
1 3
2 3

 

Ex) 프로그래머스 Level 0 - 구슬을 나누는 경우의 수 

<hide/>

#include <string>
#include <vector>

using namespace std;

void Combination(int _iCurrentN, int _iN, int _iCurrentR, int _iR, int& _iAnswer, vector<bool>& _vbVisit)
{
    if (_iCurrentR == _iR)
    {
        ++_iAnswer;
        return;
    }
    else
    {
        for (int i = _iCurrentN; i < _iN; ++i)
        {
            if (true == _vbVisit[i])
            {
                continue;
            }
            _vbVisit[i] = true;
            Combination(i, _iN, _iCurrentR + 1, _iR, _iAnswer, _vbVisit);
            _vbVisit[i] = false;
            
        }
    }
}

int solution(int balls, int share) {
    int answer = 0;
    
    vector<bool> vbVisit;
    vbVisit.resize(balls + 1, false);
    
    Combination(0, balls, 0, share, answer, vbVisit);
    
    return answer;
}

 

Ex) 프로그래머스 Level 1 - 두 개 뽑아서 더하기  

<hide/>

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void Combination(int CurrentN, int N, int CurrentR, int R, vector<int>& Input, vector<int>& Result, vector<bool>& Visit, vector<int>& answer)
{
    if (CurrentR == R)
    {
        int Summation = 0;
        for (int i = 0; i < R; ++i)
        {
            Summation += Result[i];
            cout << Result[i] << ' ';
        }
        cout << endl;
        
        if (answer.end() == find(answer.begin(), answer.end(), Summation))
        {
            answer.push_back(Summation);    
        }
        
    }
    else
    {
        for (int i = CurrentN; i < N; ++i)
        {
            if (true == Visit[i])
            {
                continue;
            }
            Visit[i] = true;
            Result[CurrentR] = Input[i];
            Combination(i, N, CurrentR + 1, R, Input, Result, Visit, answer);
            Visit[i] = false;            
        }
    }
}

long long CalculatePermutation(long long N, long long R)
{
    long long Factorial = 1;
    for (long long i = N; i > (N - R); --i)
    {
        Factorial *= i;
    }
    return Factorial;
}

long long CalculateCombination(long long N, long long R)
{
    long long Factorial = 1;
    for (long long i = R; i >= 1; --i)
    {
        Factorial *= i;
    }
    return CalculatePermutation(N, R) / Factorial;
}

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    size_t N = numbers.size();
    answer.reserve(CalculateCombination(static_cast<long long>(N), 2) + 1);
    
    vector<int> Result;
    Result.resize(N + 1, 0);
    vector<bool> Visit;
    Visit.resize(N + 1, false);
    Combination(0, static_cast<int>(numbers.size()), 0, 2, numbers, Result, Visit, answer);
    
    sort(answer.begin(), answer.end());
    
    return answer;
}

 

 

 

 

 

저작자표시 비영리 변경금지

'C++ > 자료구조와 알고리듬' 카테고리의 다른 글

7. Implementation  (0) 2023.02.07
6. Linked list, Hash table  (0) 2022.12.30
4. Graph, DFS, BFS  (0) 2022.11.22
3. Tree, Binary Search Tree  (0) 2022.11.04
2. Sort, Search, Stack, Queue  (0) 2022.10.23

관련글

댓글

티스토리툴바