출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/12900
코딩테스트 연습 - 2 x n 타일링
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는
programmers.co.kr
더보기
첫 번째 풀이 : 시간초과
def solution(n):
dp = [1 for _ in range(n+1)]
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n] % 1000000007
풀어본 문제라고 생각하고 아무 생각없이 풀었는데 바로 시간초과 나왔다. 세상에
두 번째 풀이
def solution(n):
prepre = 1
pre = 2
for _ in range(3, n+1):
pre, prepre = prepre + pre, pre
return pre % 1000000007
시간복잡도 상으로는 O(N)이라서 더 이상 줄이는건 불가능하다고 보고
dp 배열을 선언하는 과정에서 O(N)이 O(2N)이 되는 데서 시간이 오래걸리는게 아닐까 생각해
배열 선언을 없애버렸더니 풀렸다.
시간 복잡도
O(N)
알게 된 점
자료의 개수가 엄청날 경우 O(2N)조차도 오래 걸릴 수 있다.
배열 선언에도 시간이 걸리니 주의할 것!
고찰
-
'알고리즘 > Python' 카테고리의 다른 글
[python] 프로그래머스 - 단어 변환 (0) | 2022.06.29 |
---|---|
[python] 프로그래머스 - 네트워크 (0) | 2022.06.28 |
[python] 프로그래머스 - N-Queens (0) | 2022.06.01 |
[python] 백준 16926 - 배열 돌리기 1 (0) | 2022.05.16 |
[python] 프로그래머스 - 행렬 테두리 회전하기 (0) | 2022.05.16 |