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

자료구조알고리즘/이론

포시 2023. 4. 13. 14:32

재귀를 활용한 문제들

팰린드롬(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

1695번: 팰린드롬 만들기

앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열

www.acmicpc.net

문제 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)