모름

 

재귀 알고리즘의 속성

 

ko.khanacademy.org

앞서 팩토리얼 함수를 통해 재귀 함수를 구현해봤습니다. 이제 기본 개념을 정리해보겠습니다.

 

어떤 문제를 해결하기 위해, 문제의 범위보다 약간 좁은 하위 문제를 해결합니다. 그 다음에 하위 문제에 대한 해답을 이용하여 원래 문제를 해결합니다.

 

n!의 경우 n!을 바로 계산안하고 더 작은 하위 문제인 (n-1)!을 계산했습니다. 그리고 하위 문제의 해답을 이용하여 n!의 값을 계산했습니다.

 

재귀 알고리즘의 조건

재귀 알고리즘이 실제로 작동하려면 더 좁은 하위 문제가 base case(탈출 조건)에 도달하여 재귀 함수가 끝날 수 있어야합니다. n!을 계산할 때 n은 계속 작아져 0!에 도달하게됩니다. 재귀 알고리즘에는 이러한 base case가 반드시 필요합니다!

 

예를 들어 음수에 대한 계승을 재귀를 통해 계산한다치면 (-1)!은 (-2)!을 재귀 조건으로 가집니다. 이렇게 계속 -3!, -4! 값이 작아지지만 결코 base case인 0에는 도달 할 수 없습니다. 절대로 답이 구해지지 않는 것입니다.

 

이러한 조건을 두 개의 간단한 규칙으로 간추려보겠습니다.

 

1. 재귀의 호출은 같은 문제 내에서 더 범위가 작은 값, 즉, 하위 문제에 대하여 이루어져야 합니다.
2. 재귀함수 호출은 더 이상 반복되지 않는 base case에 도달해야합니다.

 

러시아 인형 예시도 마찬가지로 더 쪼개질수없는 작은 인형이 남는 base case가 존재합니다!

 

 

재귀를 활용하여 회문 여부 판단하기

회문(palindrome)은 앞에서 읽는 철자와 뒤에서 읽는 철자가 똑같은 단어입니다. 예를 들면 ROTOR가 있겠죠. 하지만 MOTOR은 회문이 아닙니다. 우리나라로 치면 토마토가 회문이 될 수 있겠네요.

 

어떤 단어가 회문인지 아닌지 재귀법을 어떻게 활용할 수 있을까요. 제일 먼저 탈출 조건이 무엇인지 생각해보겠습니다. 문자열의 앞쪽이든 뒷쪽이든 어느 쪽으로 읽든 똑같은 연속된 문자가 있어야합니다. 글자가 하나만 있어도 앞 뒤가 똑같기에 회문입니다. 그리고 빈 문자열이라도 앞 뒤가 똑같기 때문에 회문입니다.

 

그러므로 최대 하나의 글자를 포함하는 문자열을 회문이라고 하겠습니다. 따라서 빈 문자열이나 글자가 하나인 문자열도 회문이라는 것이 여기서의 탈출 조건(base case)입니다.

 

 

문자열이 두 자 이상인 경우에 재귀적인 경우를 찾을 수 있습니다. 첫번째와 마지막 글자가 같은 것은 어느 회문에서의 공통적인 속성입니다. 따라서 어떤 문자열이 회문이 아닐 경우를 판단할 방법을 찾았습니다. 바로 첫 번째와 마지막 글자가 다른 경우입니다. 이 경우 답이 즉각적으로 나오기 때문에 탈출 조건(base case)로 간주할 수 있습니다.

 

그럼 첫 번째와 마지막 글자가 같은 경우는 어떨까요. 회문일수도 있고 아닐수도 있습니다. 만약 RATER라는 글자가 있는데 처음에는 첫 번째와 마지막 글자가 같습니다. 하지만 첫 번째와 마지막 글자를 제외하면 문자열에는 ATE가 남고 첫 번째와 마지막 글자가 다른 경우이므로 RATER은 회문이 아니게됩니다.

 

지금까지의 분석을 통해 어떤 문자열의 회문 여부를 재귀적으로 알아낼수있습니다. 첫 번째와 마지막 글자가 다르면 회문이 아닙니다. (base case) 그리고 첫 번째와 마지막 글자를 제외하고 남은 문자열의 하위 문제 가 회문인지 판단합니다. 그리고 최종적으로 비교할 문자가 하나도 없거나 문자가 하나 남을 경우 이 문자열은 회문으로 판정됩니다.

 

회문 판단의 의사 코드

1. 문자열에 글자가 없거나 하나의 글자만 있다면 회문입니다.
2. 그 밖의 경우에는 문자열의 첫 번째 글자와 마지막 글자를 비교합니다.
3. 첫 번째 글자와 마지막 글자가 서로 다르다면 이 문자열은 회문이 아닙니다.
4. 그렇지 않다면, 첫 번째 글자와 마지막 글자가 서로 같습니다. 그 두 글자를 문자열에서 삭제 한 후 남은 문자열이 회문인지 판단합니다. 이 작은 문자열의 회문 여부 결과를 가지고 원래 문자열의 회문 여부 결과로 반환합니다.

 

회문여부를 판단하는 함수의 구현

먼저 탈출 조건부터 작성해보겠습니다.

 

첫 번째 base case

    // base case #1
    if(str.length <= 1)
    {
        return true;
    }

문자열에 글자가 한 개 혹은 비어있다면 이는 무조건 회문입니다.

 

두 번째 base case

    // base case #2
    if(firstCharacter(str) !== lastCharacter(str))
    {
        return false;
    }

첫글자와 마지막 글자가 같지 않다면 이는 무조건 회문이 아닙니다. 여기서 firstCharacter(), lastCharacter()은 문자열의 첫 글자와 마지막 글자를 리턴합니다.

 

마지막으로 재귀 조건을 작성합니다.

return isPalindrome(middleCharacters(str));

middleCharacters()는 앞글자와 마지막 글자를 제거하고의 문자열을 반환합니다.

 

// Returns the first character of the string str
var firstCharacter = function(str) {
    return str.slice(0, 1);
};

// Returns the last character of a string str
var lastCharacter = function(str) {
    return str.slice(-1);
};

// Returns the string that results from removing the first
//  and last characters from str
var middleCharacters = function(str) {
    return str.slice(1, -1);
};

var isPalindrome = function(str) {
    // base case #1
    if(str.length <= 1)
    {
        return true;
    }

    // base case #2
    if(firstCharacter(str) !== lastCharacter(str))
    {
        return false;
    }
    
    
    // recursive case
    return isPalindrome(middleCharacters(str));
};

var checkPalindrome = function(str) {
    println("Is this word a palindrome? " + str);
    println(isPalindrome(str));
};

checkPalindrome("a");
Program.assertEqual(isPalindrome("a"), true);
checkPalindrome("motor");
Program.assertEqual(isPalindrome("motor"), false);

자바스크립트 코드 전문입니다. C#으로도 한 번 짜보겠습니다.

 

static bool isPalindrome(string str)
{   
    //탈출 조건 #1 (base case)
    if(str.Length <= 1)
    {
        return true;
    }

    //탈출 조건 #2
    if(str.Substring(0,1) != str.Substring(str.Length-1))
    {
        return false;
    }

    //재귀 조건 (recursive case)
    return isPalindrome(str.Substring(1, str.Length - 2));
}

정상적으로 작동됩니다! 하지만 알아보기가 어렵기 때문에 함수로 정리를 해주겠습니다.

 

static void Main(string[] args)
{
    Console.WriteLine(isPalindrome("mozim"));
}

static bool isPalindrome(string str)
{   
    //탈출 조건 #1 (base case)
    if(str.Length <= 1)
    {
        return true;
    }

    //탈출 조건 #2
    if(firstCharacter(str) != lastCharacter(str))
    {
        return false;
    }

    //재귀 조건 (recursive case)
    return isPalindrome(middleString(str));
}

static string middleString(string str)
{

    return str.Substring(1, str.Length-2);
}

static string firstCharacter(string str)
{
    return str.Substring(0,1);
}

static string lastCharacter(string str)
{
    return str.Substring(str.Length-1);
}

깔끔합니다. 이상입니다.

저작자표시
모름 블로그의 첫 페이지로 이동

티스토리툴바