[YYBASIC0210,11/얌얌코딩] 재귀 함수 가지치기 1,2

 

• a,b,c 세 개의 문자가 주어졌고 이 중 세 개를 중복 허용하여 선택하면 'aaa', 'bbb', 'ccc'와 같은 경우의 수가 발생합니다. 이는 중복 순열로 분류됩니다.
• 중복이 허락되지 않을 경우, 가능한 경우의 수는 abc, acb, bac, bca, cab, cba 여섯 가지로, 이는 순열입니다.
• 재귀 함수에서 중복을 제거하려면 이전 레벨에 현재 레벨에 삽입할 데이터와 같은 요소가 존재하는지 확인하는 조건문이 필요합니다.

 

// YYBASIC02_10_11
#include <iostream>
using namespace std;

char path[5] = "";

/* 중복 순열 */
#pragma region Permutation with repetition
void test1(int level)
{
    // 무한정 호출되는 함수를 방지하는 게 급선무
    if (level == 3)
    {
        cout << path << endl;
        return;
    }

    for (size_t i = 0; i < 3; i++)
    {
        path[level] = 'A' + i;
        test1(level + 1);
        path[level] = 0;
    }
}
#pragma endregion

/* 순열 */
#pragma region Permutation
void test2(int level)
{
    // 종료 조건
    if (level == 3)
    {
        cout << path << endl;
        return;
    }

    for (size_t i = 0; i < 3; i++)
    {  
        // 중복 방지
        bool isOverlap = false;     // 중복이 발생했는지 체크

        // path[0] 부터 path[level-1]까지의 값 비교
        for (size_t j = level; j > 0 ; j--)
        {
            // path[level]에 채우려는 값(== 'A' + i)을 이전 노드들 중에 하나라도 갖고 있다면
            if (path[level - j] == 'A' + i)
            {
                isOverlap = true;   // 중복되었음을 확인하고
                break;              // 반복문을 빠져나온다
            }
        }
        if (isOverlap)              // 중복이 발생했음이 확인되었다면
            continue;               // 뒷 코드를 실행하지 않는다

        path[level] = 'A' + i;
        test2(level + 1);
        path[level] = 0;
    }
}
#pragma endregion

void main()
{
    cout << "< test1() - Permutation with repetition >" << endl;
    test1(0);

    memset(path, '\0', size(path));

    cout << "\n< test2() - Permutation with repetition >" << endl;
    test2(0);
}

 

• `test2(int level)` 는 직접 구현해 본 순열을 생성하는 함수입니다.
  • 중복 여부를 감지하는 bool 형 변수 `isOverlap`과 for loop를 이용하여 현재 level에 삽입하려는 값이 이전 level들에 이미 포함되어 있는지 체크합니다.
  • 만약 중복 발생한 경우 continue문에 의해 하위 코드를 실행하지 않고 다음 흐름으로 넘어감으로써 순열을 생성하도록 코드를 작성하였습니다.

 

LV08 재귀함수 가지치기 _1

 

LV08 재귀함수 가지치기_2