2-3. 재귀함수 사용하기

재귀 함수

• 함수 내에서 자기 자신을 다시 호출하는 함수이다. 이 함수를 잘 사용하면 N번의 반복문을 보다 보기 쉽게 작성할 수 있다. 단, 다중 루프문을 사용한 것보다 복잡도가 줄어들지는 않을 수 있다.

• 재귀 함수는 잘 짜는게 중요한데, 항상 다음의 경우를 고려해야 한다.

  • 조건에 맞지 않는 경우(불가능한 경우)
  • 정답을 찾은 경우
  • 재귀 호출을 하는 경우(다음의 경우를 실행하는 경우)

9095 1, 2, 3 더하기, 백준 온라인 저지

정수 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제. 주어진 N이 3일 경우, 1, 2, 3의 합으로 나타내는 방법은 아래의 표와 같다.

N=4
1+1+1+1
1+1+2
1+2+1
1+1+2
2+1+1
2+2
1+3
3+1

이 때, N<=10이기 때문에 총 경우의 수는 3^N이 된다. 따라서 함수를 go(sum, goal)와 같이 작성할 때, 함수 goal 내에서 합sum을 계산하기 위해 호출해야 하는 함수는 다음과 같다.

• 1을 사용하는 경우
  • go(sum+1, goal)
• 2를 사용하는 경우
  • go(sum+2, goal)
• 3을 사용하는 경우
  • go(sum+3, goal)

또한 고려해야하는 정답을 찾은 경우/불가능한 경우는 다음과 같다.

• 불가능한 경우: sum>goal, 즉 합산 결과가 goal을 넘게되면 더 이상 진행하지 않아도 불가능한 경우임을 알 수 있다.
• 정답을 찾은 경우: sum==goal. 합산 결과가 goal과 같을 경우, 원하는 결과를 찾았으므로 더 이상 진행할 필요가 없다.

1759 암호 만들기, 백준 온라인 저지

가능한 암호를 모두 구하는 문제이다.

• 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어 있다.
• 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되어 있어야 한다.
• 암호로 사용할 수 있는 문자의 종류는 C가지이다.
• 3<=L<=C<=15

L=4, C=6이라고 할 때, 사용가능한 알파벳은 최소 한 개의 모음과 최소 두 개의 자음으로 구성되어있으므로 atcisw가 주어진다고 가정하자. 이 때 6개의 문자 atcisw중 4개의 알파벳으로 만들 수 있는 암호는 다음과 같다.

만들 수 있는 암호
acis
acsw
aitw
citw

만들 수 있는 암호를 구하기 위한 함수 go(n, alpha, password, i)를 작성할 때, 고려해야 하는 경우는 다음과 같다. (n: 만들어야 하는 암호의 길이, alpha: 사용할 수 있는 알파벳의 배열, password: 현재까지 만든 암호, i: 알파벳의 인덱스)

• 불가능 한 경우: 알파벳의 인덱스가 i가 주어진 알파벳의 갯수보다 큰 경우 (i>=alpha.size())
• 정답을 찾은 경우: 암호의 길이가 만들어야하는 암호의 길이와 같을 경우 (n==password.length())
• 함수를 호출하는 경우
  • i번째 알파벳을 사용하는 경우: go(n, alpha, password+alpha[i], i+1)
  • i번째 알파벳을 사용하지 않는 경우: go(n, alpha, password, i+1)

6603 로또, 백준 온라인 저지

로또의 모든 조합을 출력해보는 문제. 이 문제를 풀기 위한 함수를 go(a, index, cnt)(a: 입력으로 주어진 수, index: 선택할지 말지 결정해야 하는 인덱스, cnt: 현재까지 포함한 수의 갯수)와 같이 작성할 때, 고려해야 하는 경우는 다음과 같다.

• 정답을 찾은 경우: 현재까지 포함한 수의 갯수가 6개가 되면, 즉 cnt==6이 되면 정답을 찾은 경우이다.
• 불가능한 경우: index값이 a의 크기를 벗어난 경우, 즉 index==a.size()이 되면 불가능하다.
• 다음 경우
  • index번째를 선택하는 경우: go(a, index+1, cnt+1)
  • index번째를 선택하지 않는 경우: go(a, index, cnt)

1182 부분집합의 합, 백준 온라인 저지

서로 다른 N개의 정수로 이루어진 집합이 있을 때, 이 집합의 공집합이 아닌 부분집합 중에서 그 집합의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제이다. (단, 1<=N<=20)

부분집합의 합을 구하기 위한 함수를 go(index, sum)(index:부분집합에 포함할지 말지 결정해야 하는 인덱스, sum: 현재까지 부분집합의 합)와 같이 작성할 때, 고려해야하는 경우의 수는 다음과 같다. (n은 입력받은 정수의 갯수, m은 부분집합 중에서 그 집합의 원소를 다 더한 값을 의미한다.)

• 정답을 찾은 경우: index==n&&sum==m
• 불가능한 경우: index==n&&sum!=m
• 함수를 호출하는 경우
  • index번째를 부분집합에 추가하는 경우: go(index+1, sum+a[i])
  • index번째를 부분집합에 추가하지 않는 경우: go(index+1, sum)

14501 퇴사, 백준 온라인 저지

N+1이 되는 날 퇴사를 하려고 하는데, 남은 N일동안 최대한 많은 상담을 하려고 한다. 하루에 하나의 상담을 할 수 있고, i일에 상담을 하면 T[i]일이 걸리고 P[i]원을 번다. 이 때의 최대 수익을 구해보자.(단, 1<=N<=15)

수익을 계산하는 함수를 go(day, sum)와 같이 작성할 때, 고려해야 하는 경우는 다음과 같다.

• 정답을 찾은 경우: day==n이 되면 퇴사일이기 때문에, 이 때까지의 얻은 수익을 합산한 sum이 정답 중 하나가 된다.
• 불가능한 경우: day>n이 되면 퇴사일을 넘겼기 때문에, 이 경우는 더 이상 고려하지 않아도 된다.
• 함수를 호출하는 경우
  • 상담을 하는 경우: go(day+t[day], sum+p[day])
  • 상담을 하지 않는 경우: go(day+1, sum)

14888 연산자 끼워넣기, 백준 온라인 저지

N개의 수로 이루어진 수열과 N-1개의 연산자가 있다.(2<=N<=11) 이 때, 수와 수 사이에 연산자를 하나씩 끼워넣어서 만들 수 있는 수식 결과의 최대값과 최소값을 구하는 문제이다. 단, 수식의 계산은 연산자 우선순위와 상관없이 앞에서부터 진행하며, 수의 순서를 바꿀 수 없다. 연산자는 여러개가 주어질 수 있으므로, 경우의 수를 구하는 함수를 go(a, index, cur, plus, minus, mul, div)와 같이 작성할 수 있다. (a: 입력으로 주어진 수열, index: 현재 계산해야 하는 인덱스, cur: index-1번째까지 계산한 결과, plus, minus, mul, div: 사용할 수 있는 연산자의 갯수) 이 때 고려해야하는 경우의 수는 다음과 같다.

• 정답을 찾은 경우: index==n
• 함수를 호출하는 경우
  • +를 사용하는 경우: go(a, index+1, cur+a[index], plus-1, minus, mul, div)
  • -를 사용하는 경우: go(a, index+1, cur+a[index], plus, minus-1, mul, div)
  • x를 사용하는 경우: go(a, index+1, cur+a[index], plus, minus, mul-1, div)
  • /를 사용하는 경우: go(a, index+1, cur+a[index], plus, minus, mul, div-1)

15658 연산자 끼워넣기2, 백준 온라인 저지

이 문제는 14888 연산자 끼워넣기, 백준 온라인 저지 문제와 동일한 방법으로 풀 수 있다.