회문

회문(回文)은 앞에서 읽어도 뒤에서 읽어도 똑같은 이나 를 말한다. 영어로는 팰린드롬(palindrome)이라고 한다.

1 예시[편집]

1.1 단어[편집]

1.2 문장[편집]

  • 소주 만 병만 주소
  • 여보게 저기 저게 보여
  • 여보 안경 안 보여
  • Was it a cat I saw?

2 판별 알고리즘?[편집]

컴퓨터공학자 그루엔버거가 제시한 알고리즘은 회문이 되는 수에 관한 흥미로운 추측을 제시한다. 그 알고리즘은 다음과 같다.

  1. 임의의 자연수를 입력받는다.
  2. 해당되는 수가 회문인지를 판단한다.
  3. 회문이 아니면, 해당되는 수를 앞뒤로 뒤집는다. 그리고 그 수를 원래 수와 더한다. 그 다음 2번으로 돌아간다.

예를 들어, 8293라는 수가 주어졌다고 하자. 이 수는 회문이 아니기 때문에 이 수를 앞뒤로 뒤집어 원래의 수와 더한다. 즉, 8293 + 3928 = 12221을 구하는 것이다. 그리고 이 수는 회문이므로 알고리즘이 종료된다.

모든 자연수 입력에 대하여 이 알고리즘이 종료하는지, 아니면 이 알고리즘이 무한히 루프되도록 하는 자연수가 있는지는 아직 밝혀지지 않았다.

3 트리비아[편집]

  • 슈퍼주니어의 《로꾸거!!!》는 회문을 아주 적극적으로 활용한 노래다.

4 각주