[코드트리] Backtracking - 백트래킹 / 재귀 연습문제

 

백트래킹.

대충 알고있는건

백트래킹 == 완전탐색(모든 경우의 수를 무식하게 찾기)에서 가지치기로 효율 높임

이정도라서..ㅋㅋ 연습문제도 풀어봐야겠다

 

---

 

대부분의 알고리즘 문제들은 원하는 모든 조합을 만들어 그 중 문제에서 원하는 답을 고르는 식으로 해결이 가능합니다.

만약 n 제한이 작고, 모든 조합을 만드는 데 걸리는 시간이 문제에서 주어진 제한 시간보다 더 작다면, 항상 모든 조합을 다 만들어 보는 것이 가독성 측면에서나, 코드를 작성하는 입장에서 가장 좋다고 할 수 있을 것입니다. 다만, (1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 1, 3), (1, 1, 1, 2, 1), (1, 1, 1, 2, 2), .. 등 여러 가능한 순열과 조합을 만드는 것을 for문 만을 이용하여 표현하기에는 많은 어려움이 있습니다.

이런 경우에 재귀함수를 이용하면 원하는 모든 순열과 조합을 만들어 낼 수 있습니다.

 

재귀함수는 크게 종료 조건과 재귀 호출 부분으로 나뉩니다.

 

n크기의 배열에 0과 1을 하나씩 넣어가는 재귀함수가 있다고 칩시다.

만약 재귀에서 배열의 크기가 n에 이르면, 종료 조건을 만족하며 출력 후 return를 통해 퇴각하면 됩니다.

재귀함수에서는 퇴각을 진행할 때, 진입 직전에 arr에 적었던 숫자를 하나 빼줘야 합니다. 그래야 그 다음 숫자에 대해 공정하게 기회를 줄 수 있게 됩니다.

이러한 과정을 거쳐 재귀적으로 탐색을 진행하면 원하는 숫자들을 전부 만들어낼 수 있게 됩니다.

 

---

연습문제 : k개 중에 1개를 n번 뽑기

1이상 K이하의 숫자를 하나 고르는 행위를 N번 반복하여 나올 수 있는 모든 서로 다른 순서쌍을 구해주는 프로그램을 작성해보세요.

예를 들어 K이 3,N이 2인 경우 다음과 같이 9개의 조합이 가능합니다.

• 1 1
• 1 2
• 1 3
• 2 1
• 2 2
• 2 3
• 3 1
• 3 2
• 3 3

입력 형식

첫째 줄에 K와 N이 공백을 사이에 두고 주어집니다.

• 1≤K≤4
• 1≤N≤8

출력 형식

서로 다른 순서쌍의 개수 만큼의 줄에 걸쳐 한 줄에 하나씩 순서쌍의 상태를 공백을 사이에 두고 출력합니다. 이때 앞에서 부터 봤을 때 사전순으로 앞선 순서쌍부터 출력합니다.

---

나의 풀이

// 틀린 코드

int k; int n;
vector<int> nums;

void printNums(){
    for(int i=0; i<nums.size(); ++i){
        cout << nums[i] << " ";
    }
    cout << "\n";
}

int getNums(int cnt){
    if(cnt==n){
        printNums();
        return 0;
    }
    for(int i=1; i<=k; ++i){
        nums.push_back(i); // 첫 값을 넣고
        getNums(cnt+1); // 다음 값을 반복
    }
}

int main() {
    cin >> k >> n;

    getNums(0);

    return 0;
}

뭐야 왜이래

알고보니

getNums로 숫자를 받아온 뒤에 다음 턴을 위해서 다시 pop해줘야하는데 그걸 빼먹었다.

 

int getNums(int cnt){
    if(cnt==n){
        printNums();
        return 0;
    }
    for(int i=1; i<=k; ++i){
        nums.push_back(i); // 첫 값을 넣고
        getNums(cnt+1); // 다음 값을 반복
        nums.pop_back(); // 모두 받아온 후에 pop해주기
    }
}

 

이렇게 고쳐주니 성공! 함수는 한 기능만 하는게 best라서, 출력 함수는 따로 빼놓는게 좋다고 함

재귀 은근 어렵다.

연습 많이 해야겠음 😢