백준 검색 결과
248 개의 검색 결과가 있습니다.
코딩/백준 (Python)

백준 11444번: 피보나치 수 6 (Python)

접근 피보나치 수열을 행렬의 곱셈 및 분할 정복을 통해 어떻게 풀까 생각을 해봐도 나오지 않아 그 방법을 찾아보았다. 결과적으로는 혼자 생각해서는 쉽게 그 결과를 도출해내지 못했을 것 같다.. n번째 피보나치 수를 다음과 같은 식을 통해서도 구할 수 있다. $$ \begin{pmatrix} F_{n + 1} & F_{n}\\ F_{n} & F_{n - 1} \end{pmatrix} = \begin{pmatrix} 1 & 1\\ 1 & 0 \end{pmatrix}^{n} $$ 이전 10830번 행렬 제곱에서 사용했던 함수를 그대로 사용하여 문제를 해결할 수 있다. 코드 import sys c = 1000000007 def multiply(matrix1, matrix2): # 행렬의 곱셈 함수 ans = [..

2021. 4. 3. 03:50
코딩/백준 (Python)

백준 1780번: 종이의 개수 (Python)

접근 이전 2630번 색종이 만들기와 동일한 문제이지만, 2 * 2가 아닌 3 * 3으로 나눈다는 것만 수정해 주면 되겠다. 2021.04.01 - [코딩/백준 (Python)] - 백준 2630번: 색종이 만들기 (Python) 백준 2630번: 색종이 만들기 (Python) 접근 분할 정복은 재귀적으로 자신을 호출하면서 연산의 단위를 줄여가는 방식이다. 이 문제에서는 전체를 확인하고, 해결되지 않았을 경우(색이 모든 칸에서 동일하지 않을 경우) 기존의 영역 ca.ramel.be 코드 import sys n = int(sys.stdin.readline()) board = [] for _ in range(n): board.append(list(map(int, sys.stdin.readline().spli..

2021. 4. 1. 23:38
코딩/백준 (Python)

백준 1992번: 쿼드트리 (Python)

접근 바로 이전 2063번 색종이 만들기 문제와 매우 비슷하고, 그 표현 방법만 바꿔서 넣어주면 되겠다. 2021.04.01 - [코딩/백준 (Python)] - 백준 2630번: 색종이 만들기 (Python) 백준 2630번: 색종이 만들기 (Python) 접근 분할 정복은 재귀적으로 자신을 호출하면서 연산의 단위를 줄여가는 방식이다. 이 문제에서는 전체를 확인하고, 해결되지 않았을 경우(색이 모든 칸에서 동일하지 않을 경우) 기존의 영역 ca.ramel.be 코드 import sys n = int(sys.stdin.readline()) board = [] for _ in range(n): board.append(list(sys.stdin.readline().rstrip())) compression =..

2021. 4. 1. 23:31
코딩/백준 (Python)

백준 5430번: AC (Python)

접근 R 문자가 나왔을 때, 주어진 배열을 실제로 뒤집으면 시간 초과가 뜨게 된다. 따라서 실제로 배열을 뒤집지 않고 문제를 해결할 방법을 찾아야 한다. 나 같은 경우에는 left라는 변수를 만들어 left의 상태에 따라 D 문자가 나왔을 때, 왼쪽 요소를 제거할지, 오른쪽 요소를 제거할지를 결정할 수 있게 해두고, R 문자가 나오면 left 의 상태를 True와 False 사이에 왔다갔다 할 수 있게 해둠으로써 해결했다. (더 좋은 방법이 있으면 제안 부탁드립니다!) 코드 import sys from collections import deque n = int(sys.stdin.readline()) for _ in range(n): iserror = False # 빈 배열에서 D 작업을 했을 때 erro..

2021. 4. 1. 12:25
코딩/백준 (Python)

백준 19298번: 오큰수 (Python)

접근 당연하게도 for문을 돌려서 더 큰 수가 나올 때까지 탐색하면 시간 초과되게 된다. 스택 문제 답게 스택을 써서 풀어보았다. 처음에 빈 stack 리스트를 만들고 주어진 수 배열의 첫 숫자부터 탐색하게 된다. stack에는 주어진 수 배열의 index를 저장하게 되는데, 탐색 중에 stack이 비어있거나, stack의 top에 해당하는 숫자가 탐색중인 숫자보다 작으면 해당 숫자를 ans라는 새로운 리스트에 저장하게 된다. for문을 통해 탐색하게 되는데 예시 입력1에서 i = 0 일 때부터 확인해보면 다음과 같다. # i = 0 일 때, stack이 비어있으므로 0을 push 해준다. stack = [0] # i = 1 일 때, stack의 top에 해당하는 수 m[0] = 3 이고 m[i] = 5..

2021. 4. 1. 08:11
코딩/백준 (Python)

백준 1874번: 스택 수열 (Python)

접근 코드가 어렵다기 보다는 이 문제가 의미하는 것이 무엇인지를 몰라 헤메다가 다른 글의 도움을 받았다.. 예제 입력 코드를 예시로 들어 어떤 과정으로 스택 수열이 표시가 될 수 있는지 확인해 보려고 한다. push를 하면 1부터 오름차순의 순서대로 숫자를 stack에 쌓는다는 점을 유의하면서 아래 과정을 확인해보자. 먼저 첫번째 입력은 정수의 수를 입력받고 두번째 입력받는 수는 4이다. 그럼 stack의 top (stack[-1]) 이 입력받은 4가 될 때까지 push 해준다. push 해줄 때마다 별도의 list에 '+' 문자를 저장해준다. # push stack = [1] op = ['+'] # push stack = [1, 2] op = ['+', &#3..

2021. 4. 1. 07:28
반응형