문제
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.
N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)
출력
각 테스트 케이스마다 P(N)을 출력한다.
접근
처음에는 재귀로 접근하면 되겠다 싶었다. 규칙을 찾아내서 점화식만 써주면 되는 구조라 굉장히 쉽다고 생각했다. 점화식도 그냥 순서를 쭉 보다보면 쉽게 찾아낼 수 있다. P(n) = P(n - 2) + P(n -3) (단, n >= 4) 다.
그래서 작성한 코드는 다음과 같다.
//
// main.swift
// ProblemSolving_9461
//
// Created by YOUJIM on 2023/07/04.
//
//import Foundation
func padoban(_ idx: Int) -> Int {
if idx == 1 || idx == 2 || idx == 3 { return 1 }
return padoban(idx - 2) + padoban(idx - 3)
}
for _ in 0..<Int(readLine()!)! { print(padoban(Int(readLine()!)!)) }알아보니 재귀의 경우 중복 호출 때문에 숫자가 70 정도로만 올라가도 시간초과가 난다고 한다 🫠 난 이렇게 살아왔는데 ... 마음이 아팠다. 그래서 질문 게시판을 하염없이 돌다가 메모이제이션(Memoization) 으로 풀어보라는 답변을 발견했다.
메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)
메모이제이션은 동적 계획법에서 사용되는 기술인데, 그때 그때 값을 다 호출해서 리턴하는 재귀와는 다르게 값을 계산해서 저장해둘 수 있다. 그래서 다음 계산에서 값이 저장되어 있을 경우 가져와서 사용할 수 있기 때문에 실행 시간이 줄어든다!
재귀의 시간 복잡도는 O(2^n)인 반면에, 메모이제이션의 시간 복잡도는 O(n)밖에 되지 않는다고 한다.
그래서 이 메모이제이션을 이용해서 푼 코드는 다음과 같다.
코드
//
// main.swift
// ProblemSolving_9461
//
// Created by YOUJIM on 2023/07/04.
//
//import Foundation
var memo = [Int](repeating: -1, count: 101)
memo[1] = 1
memo[2] = 1
memo[3] = 1
func padoban(_ idx: Int) -> Int {
if memo[idx] != -1 { return memo[idx] }
memo[idx] = padoban(idx - 2) + padoban(idx - 3)
return memo[idx]
}
for _ in 0..<Int(readLine()!)! { print(padoban(Int(readLine()!)!)) }입력 값의 최대가 100이었기 때문에 memo 배열의 길이를 101로 맞춰준 뒤 일단 전부 -1로 초기화해줬다. 이후 1, 2, 3번째 인덱스 값을 전부 1로 맞춰주고 padoban() 에서는 만약 찾는 배열 인덱스에 값이 저장되어있지 않다면 계산한 뒤 저장해주고, 아니면 저장되어 있는 값을 리턴했다.
느낀 점
메모이제이션 분명 배웠던 것 같은데 ㅜㅜ 다 까먹었다
그냥 알고리즘 배운 적 없는 사람처럼 처음이라는 마음가짐으로 문제 푸는 것도 나쁘지 않다. 오히려 좋아
