[알고리즘 문제해결전략] 분할 정복
분할 정복(Divide & Conquer)이란? 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 내는 방법 일반적인 재귀 호출과 분할 정복의 차이 분할 정복이 일반...
Recent posts
[백준 BOJ_6549] 히스토그램에서 가장 큰 직사각형 Python 풀이
출처: 백준 온라인 저지 문제 풀이 문제를 분할하기 위해 아래의 그림과 같이 히스토그램을 반으로 나눈 뒤 가장 큰 직사각형이 왼쪽에 있는 경우와 오른쪽에 있는 경우, 그리고 나눈 중간에 걸쳐있는 경우 세가지로 분할해주었습니다. 왼쪽과 오른쪽의 경우 중 큰 값으로 저...
[백준 BOJ_11444] 피보나치 수 6 Python 풀이
출처: 백준 온라인 저지 문제 풀이 이 문제는 행렬의 거듭제곱을 이용하여 풀 수 있습니다. 아래의 행렬을 거듭제곱했을 때의 결과를 지켜보면 피보나치 수를 발견할 수 있습니다. [\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}...
[백준 BOJ_10830] 행렬 제곱 Python 풀이
출처: 백준 온라인 저지 문제 풀이 우선 아래의 행렬의 곱셈을 구하는 선행문제에서 multiply함수를 가져옵니다. [백준 BOJ_2740] 행렬 곱셈 Python 풀이 거듭제곱을 연속하였을 때 수가 커지는 것을 미연에 방지하기위해, 곱해줄 때마다 1000으로 ...
[백준 BOJ_2740] 행렬 곱셈 Python 풀이
출처: 백준 온라인 저지 문제 풀이 이 문제는 분할정복으로 해결이 가능하지만 N과 M의 크기가 100으로 제한되어 있기 때문에 슈트라센 알고리즘보다 3중 for loop를 쓰는 것이 더 효율적이게 됩니다. 행렬의 거듭제곱 문제를 위해 푸는 선행문제라고 봐도 되기 때문에 ...