Algorithm
-
Python | 백준 11444 / 피보나치 수 6Algorithm 2023. 6. 19. 16:04
http://boj.kr/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net n 번째 피보나치 수를 구하는 문제이다. n은 100경까지 주어지는 문제이다. n이 크기 때문에 수를 1,000,000,007 ( 10억 7 ) 로 나눈 나머지를 출력하면 된다. 1. 문제를 풀고 나서 보니 대부분의 풀이가 행렬의 거듭제곱으로 풀어낸 문제였다. 원래 피보나치 수는 DP를 이용하여 구하지만, 이 문제는 100경번째 수까지 구해야 하기 때문에 기존의 O(n)의 풀이로는 풀 수 없다. 공간복잡도 또한 O(n), 줄이면 O(2) 까지 줄일 수 있을 것 같지만 시간 복잡도에서 걸린다. 행렬의 거듭제..
-
Python | 백준 9012 / 크레인 인형뽑기 게임Algorithm 2022. 8. 29. 17:29
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 접근 방식? 스택에 ( 모양이라면 넣고, ) 모양이라면 스택의 맨 위와 비교하여 ( 모양과 맞다면 넣지 않고 다음으로 넘어간다. VPS인지 아닌지는 스택이 비어있는지 확인하여 판단한다. > code 더보기 N = int(input()) for _ in range(N): stack = [] ps = input() for w in ps: if not stack: stac..