1. 재귀함수 in Swift
이번에 코테공부를 하면서 이것저것 구글링을하다가 재귀함수에 관한 내용을 봤는데 정리해두면 도움이 될까해서 적어본다.
재귀함수는 한마디로 내 함수안에서 내 함수를 호출하는 형태를 말한다.
뭔말인지 알아보려면 예시를 들어야하는데 대부분의 예시를 팩토리얼함수를 구현하는걸로 하길래 나도 하나 만들었다.
팩토리얼은 다들 알겠지만 4! = 4x3x2x1을 뜻하고 5!은 당연히 5x4x3x2x1을 의미한다.
재귀함수로 구현을 안한다고 치면 아마도 아래와 같이 구현을 할거다
func factorial(_ input: Int) -> Int {
var result = 1
for n in 2..<input+1 {
result *= n
}
return result
}숫자의 범위를 for문으로 돌리고 각각의 요소를 저장해둔 변수에다가 곱해서 최종 결과를 반환하는 형태일거다
하지만 팩토리얼을 유심히 보면 특정 패턴이 반복되는걸 알 수 있다
예를들어서 4!같은 경우 4x3x2x1인데 이는 4x3!이라는걸 알수있고 3!은 3x2!라는걸알 수 있다
즉, 팩토리얼이라는 계산 방법은 계속해서 반복된다는거다
즉 N!를 구하기 위해서는 Nx(N-1)!를 구하면 되는거다
즉 팩토리얼을 구하기위해서 팩토리얼함수를 실행하면된다. 다시말해서 함수안에 같은함수를 실행시키면되는구조이기때문에 재귀함수로도 구현이가능하다
func factorial(_ num: Int) -> Int {
if num <= 1 {
return 1
}
return (num * factorial(num - 1))
}이런식으로 구현을 하는데 중요한건
1. 입력값
2. 탈출조건
이렇게 두가지가 가장 중요하다 우선 input의 입력값이 return의 입력값보다 커야한다
input이 num이라는 Int이고 return에 함수 input은 num-1이기때문에 만족한다
두번째 탈출조건은 무한재귀에 빠지지 않게 하기위함이다 결국 재귀"함수"이기 때문에 함수를 종료시키려면 return을 해주면된다 따라서 조건문을 통해 탈출조건을 명시해줘야한다
2. DP(동적계획법)기초
기초적인 알고리즘 문제를 다 풀고 이제는 본격적인 알고리즘 공부를 시작했는데 처음 마주한 알고리즘이 DP(Dynamic programing) 동적계획법이다.
이걸 대체 어떻게 공부해야하나 고민을 하면서 이런저런 영상도 보고 하면서 알게된 정보를 알아보려한다
우선 DP를 배운다는건 언젠가 문제를 보고 이문제는 DP로 풀어야겠다라는 생각이 들어야한다
그러면 우리는 언제 DP로 풀어야겠다고 결정해야할까에 관한 내용이다
1번은 경우의 수가 엄청 많은경우이다
유튭에서는 "DFS나 BFS로도 풀수있지만"이라는 가정이 있지만 이건 뭐 아직 뭔지도 모르니까 넘어가자 대충 찾아보니 경우의 수가 500만개이하일때는 DP로 푸는것보다 더 좋은 방법이 있다고 한다.
보통 문제를 보면 input의 범위가 주어진다 대충 case 몇개를 써보고 규칙을 찾아서(점화식을 찾을 수 있으면 더 좋다) input의 범위에서 가장 큰 수를 넣었을때 500만번이 넘으면 DP로 풀어볼까? 라는 생각을 가져도 된다는 뜻이다
대충 계산을 해봤는데 500만이면 5곱하기 10의 6제곱이고 이걸 2의 지수로 나타내면 대충 2의 23제곱이상이면 DP로 풀생각을 하면된다
2번의 경우는중복되는 게산이 많은 경우인데 이건 1번과 함께 예시를 통해서 보면 이해가 쉽다
피보나치수열이라는게 있다
현재숫자는 내 앞에숫자와 앞에앞에숫자의 함으로 이루어진 수열이다
1 1 2 3 5 8 13 . . . .
보면 2 는 1과 1의 합이고 8은 3과 5의 합이다 이런식으로 쭉쭉 나가는걸 알 수있다.
이 피보나치수열의 경우 계산횟수가 2의 n-1인데 문제에서 input의 범위가 두자리수라고 해도 2의 99제곱만큼의 계산을 해야한다 아까 말한 2의 23제곱에 비해서 어머어머하게 큰수다. 이런경우에 DP를 쓰면되겠구나 라고생각하면된다
그리고 반복계산에 대한 내용인데 피보나치(2)를 구할때는 피보나치(1)을 한번만 계산하면되지만 피보나치(3)을 구할때는 2번 피보나치(4)를 할때는 3번 이런식으로 반복되는 계산이 많아진다 이런경우에 DP를 쓰면된다
DP의 종류에는 두가지가있다
1.탑다운(하향식)
2.바텀업(상향식)
이렇게 두가지가 있는데 주로 상향식방법을 사용한다 상향식 방법의 특징은 for문을 사용하고 메모리를 만들어서(array) 값을 저장해서 사용한다는 것이다 탑다운형식은 재귀함수를 사용한다고 한다
func solution(_ n:Int) -> Int {
var fibo = [0, 1]
for i in 2...n {
fibo.append((fibo[i-2] + fibo[i-1]))
}
return fibo[n]
}보통 피보나치수열을 DP로 구현한경우 위와같이 구현할 수 있다. 아얘 처음부터 값을 저장해서 특정 값을 사용할때 그 값을 얻기위해 또다른 반복계산을 안할 수 있다.
3. 백준(DP)문제풀이
[Bronze II] 피보나치 수 - 2747
문제 링크
성능 요약
메모리: 69100 KB, 시간: 8 ms
분류
구현(implementation), 수학(math)
문제 설명
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.
이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
n=17일때 까지 피보나치 수를 써보면 다음과 같다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.
출력
첫째 줄에 n번째 피보나치 수를 출력한다.풀이
var input = Int(readLine()!)!
var dp = [0, 1]
for i in 2...input+1 {
dp.append(dp[i-2]+dp[i-1])
}
print(dp[input])[Silver III] 1로 만들기 - 1463
문제 링크
성능 요약
메모리: 87324 KB, 시간: 56 ms
분류
다이나믹 프로그래밍(dp)
문제 설명
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.풀이
import Foundation
var input = Int(readLine()!)!
var dp: [Int] = [Int](repeating: 0, count: input+1)
// MARK: - 만약 input이 1일때 2...input(2...1)은 오류가 발생하지만 2..<input+1(2..<2)는 오류가 발생하지 않는다
for i in 2..<input+1 {
dp[i] = dp[i-1]+1
if i%2 == 0 {
dp[i] = min(dp[i], dp[i/2]+1)
}
if i%3 == 0 {
dp[i] = min(dp[i], dp[i/3]+1)
}
}
print(dp[input])