주요 내용
재귀를 활용하여 회문인지 판단하기
회문(palindrome)은 앞에서 읽는 철자와 뒤에서 읽는 철자가 똑같은 단어입니다. 예를 들어 rotor 는 회문이지만 motor 는 회문이 아닙니다.
어떤 단어가 회문인지 아닌지를 판단하기 위해 재귀법을 어떻게 활용할 수 있을까요? 먼저 탈출 조건이 무엇인지 알아보는 것부터 시작합시다. 단어 a 를 생각해 봅시다. 이는 회문입니다. 사실 회문을 영어로 된(또는 여러분이 생각하는 어떤 언어이든) 실제 단어로 생각해야 할 필요는 없습니다. 회문을 그냥 xyzyzyx 처럼 앞쪽이든 뒤쪽이든 어느 쪽으로 읽든 똑같은 연속된 문자로 생각할 수 있습니다. 연속된 문자를 문자열이라고 합니다. 그러므로 글자 하나만으로 된 문자열은 기본적으로 회문이라고 할 수 있습니다. 문자열에 아무 글자가 없을 수도 있습니다. 0개의 글자로 된 문자열을 빈 문자열(empty string)이라고 합니다. 빈 문자열 역시 회문입니다. 왜냐하면 앞뒤로 똑같이 읽히기 때문이죠. 그러므로 최대 하나의 글자를 포함하는 문자열은 회문이라고 합시다. 따라서 빈 문자열이나 글자가 하나인 문자열도 회문이라는 것이 여기에서의 탈출 조건입니다.
문자열이 두 자 이상으로 이루어진 경우는 어떨까요? 이런 상황이 바로 재귀적인 경우가 됩니다. 회문 rotor 를 생각해 봅시다. 첫 번째와 마지막 글자가 같은 특성은 어느 회문에서나 마찬가지입니다. 반대로 motor 와 같이 첫 번째와 마지막 글자가 같지 않다면 그 문자열은 회문일 수가 없습니다. 따라서 이제 어떤 문자열이 반드시 회문이 아닐 경우를 판단할 방법을 하나 찾았습니다. 바로 첫 번째와 마지막 글자가 다를 경우입니다. 이런 상황에서는 답이 즉각적으로 나오기 때문에 또다른 탈출 조건으로 간주할 수 있습니다. 첫 번째와 마지막 글자가 같을 경우로 돌아갑시다. 두 글자가 같으면 이는 무엇을 의미할까요? 문자열이 회문일 수도 있고, 아닐 수도 있다는 것입니다. 문자열 rater 는 첫 번째와 마지막 글자는 같지만 회문은 아닙니다. 첫 번째와 마지막 글자를 제외하면 문자열 ate 가 남습니다. 남은 문자열의 첫 번째와 마지막 글자가 같지 않으므로 rater 는 회문이 아님을 알 수 있죠.
이제 어떤 문자열의 회문 여부를 재귀적으로 알아낼 수 있게 되었습니다. 첫 번째와 마지막 글자가 다르면 그 문자열은 회문이 아닙니다. 그러면 첫 번째와 마지막 글자를 제외하고 남은 문자열—하위 문제—가 회문인지 알아봅니다. 짧아진 문자열의 해답이 원래 문자열의 해답이 되도록 합니다. 더 이상 비교할 글자가 없거나 하나만 남게 되면 그 문자열은 회문입니다. 이것이 위에서 다뤘던 두 단어를 해결하는 과정입니다.
이를 의사 코드(Psudocode)로 어떻게 작성할 수 있을까요?
- 문자열에 글자가 없거나 하나의 글자만 있다면 회문입니다.
- 그 밖의 경우에는, 문자열의 첫 번째 글자와 마지막 글자를 비교합니다.
- 첫 번째 글자와 마지막 글자가 서로 다르다면 이 문자열은 회문이 아닙니다.
- 그렇지 않다면, 첫 번째 글자와 마지막 글자는 서로 같습니다. 그 두 글자를 문자열에서 삭제한 후, 남은 문자열이 회문인지 확인합니다. 이 작은 문자열의 회문 여부 결과를 원래 문자열의 회문 여부 결과로 반환합니다.
위 자료는 다트머스 대학교 컴퓨터공학과의 토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.