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

백준 6549번: 히스토그램에서 가장 큰 직사각형 - 분할 정복 (Python)

접근 스택 방법에 이어 분할 정복 방법을 통해서도 문제를 풀어보았다. 2021.04.03 - [분류 전체보기] - 백준 6549번: 히스토그램에서 가장 큰 직사각형 - 스택 (Python) 백준 6549번: 히스토그램에서 가장 큰 직사각형 - 스택 (Python) 접근 문제 설명에서 스택과 분할정복 두가지 방법 모두로 풀 수 있다고 하여 먼저 스택 방법으로 시도해 보았다. 코드를 보면서 설명하는 것이 이해하기 쉬울듯 하여 코드에 주석으로 접근 방법 ca.ramel.be 분할 정복은 주어진 길이를 절반으로 나누어 작은 단위에 대해서 연산을 반복하여 최대치를 확인하는 방법이다. 히스토그램에서 가장 큰 직사각형을 구하는 문제에서도 분할 정복 방법을 사용할 수 있는데 주의해야할 점이 한가지 있다. 절반으로 나누..

2021. 4. 3. 18:00
코딩/백준 (Python)

백준 6549번: 히스토그램에서 가장 큰 직사각형 - 스택 (Python)

접근 문제 설명에서 스택과 분할정복 두가지 방법 모두로 풀 수 있다고 하여 먼저 스택 방법으로 시도해 보았다. 코드를 보면서 설명하는 것이 이해하기 쉬울듯 하여 코드에 주석으로 접근 방법을 표시하였다. 이 문제는 분할 정복 알고리즘으로도 해결할 수 있는데 이 방법은 아래의 글에 적어두었다. 2021.04.03 - [코딩/백준 (Python)] - 백준 6549번: 히스토그램에서 가장 큰 직사각형 - 분할 정복 (Python) 백준 6549번: 히스토그램에서 가장 큰 직사각형 - 분할 정복 (Python) 접근 스택 방법에 이어 분할 정복 방법을 통해서도 문제를 풀어보았다. 2021.04.03 - [분류 전체보기] - 백준 6549번: 히스토그램에서 가장 큰 직사각형 - 스택 (Python) 백준 6549..

2021. 4. 3. 17:43
코딩/백준 (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)

백준 11401번: 이항 계수 3 (Python)

접근 이 문제에 분할 정복 방법을 어떻게 적용해야 하나 고민하다가 결국 힌트를 찾아본 결과 '페르마의 소정리'를 이용한다는 것을 알게 되었다. 페르마의 소정리에 대해선 페르마의 소정리에서 개념 이해에 도움을 받았다. 이항 계수는 아래와 같은 식으로 구할 수 있는데, 분자와 분모를 모두 1,000,000,007로 나눌 경우 분모가 0이 되는 경우가 발생할 수 있기 때문에 페르마의 소정리 \( a^{p - 1} \equiv 1 (mod\ p) \) 를 이용하여 거듭제곱으로 표현하게 된다. $$ \binom{n}{k}= _{n}\textrm{C}_{k} = \frac{n!}{(n - k)!k!} $$ $$ \frac{1}{(n-k)!k!}\%p = ({(n-k)!k!})^{-1}\%p = ((n-k)!k!)^..

2021. 4. 2. 01:18
코딩/백준 (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
반응형