재귀 활용 - 회문(팰린드롬), 더하기 조합

재귀를 활용한 문제들

 

팰린드롬(Palindrome)

앞뒤 구성이 같은 문자열 

ex) 기러기, 토마토, 우영우

 

재귀 함수를 통해 간단히 구현할 수 있다.

 

코드

def palindrome(str):
  if len(str) <= 1:
    return True
    
  if str[0] == str[-1]:
    return palindrome(str[1:-1])
  else:
    return False

 

문제 1

https://www.acmicpc.net/problem/1695

1695번: 팰린드롬 만들기

 

 

문제 2

정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있다.

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
1 + 3
3 + 1

정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오

 

정수 1, 2, 3, 4, 5에 대해 위 문제에서 제시되는 방법을 사용하면 한가지 패턴을 찾을 수 있는데

3 이후로는 

n의 방법의 수에 대해

fn(n) = fn(n-1) + fn(n-2) + fn(n-3)

을 성립한다는 걸 알 수 있다.

 

이걸 코드로 나타내면 다음과 같다.

def fn(n):
  if n == 1:
    return 1
  elif n == 2:
    return 2
  elif n == 3:
    return 4
  
  return fn(n-1) + fn(n-2) + fn(n-3)