분할정복3 [알고리즘/Python] 분할 정복(Divide and Conquer) 1. 분할 정복(Divide and Conquer)이란? 큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결하여 전체 문제의 해답을 구하는 알고리즘 문제의 크기가 커서 직접적인 해결이 어려운 경우 유용하다. 대표적인 예로, 정렬 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있다. 2. 동작 방식 문제를 작은 부분 문제들로 분할한다. 분할된 부분 문제들을 각각 재귀적으로 해결한다. 부분 문제들의 해답을 결합하여 전체 문제의 해답을 얻는다. 3. 시간 복잡도 시간 복잡도는 일반적으로 부분 문제의 개수, 분할된 문제의 크기, 분할과정의 복잡도에 따라 결정된다. 대부분의 경우, 분할 정복 알고리즘은 재귀적인 방법으로 문제를 해결하므로, 재귀 호출의 깊이에 따라 .. 2023. 3. 24. [백준/파이썬] 6549 : 히스토그램에서 가장 큰 직사각형 https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 요약 : 히스토그램의 개수n과 높이를 나타내는 정수들이 주어졌다. n이 0이 나오기 전까지 히스토그램 내부에 가장 넓이가 큰 직사각형의 크기를 구해라. 히스토그램과 거의 똑같은 문제! 풀이 ) 풀이의 흐름 입력값 read를 받아 histogram함수에 넣어준다. read[0]은 직사각형의 개수 N read[1:]은 각 직사각형의 높이 .. 2023. 3. 24. [백준/파이썬] 1725 : 히스토그램 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 문제 요약 : 히스토그램의 높이가 주어졌다. 히스토그램 내부에 가장 넓이가 큰 직사각형의 크기를 구해라. 플래티넘인데 쉬워보이는데..? 했다가 며칠간 아주아주 치열하게 고민한 문제.. 맞은 코드는 아래 내리면 풀이에 작성해두었습니다! 시도 1 ) 스택문제인 만큼 스택의 특징을 잘 이용해야할 것이라 생각했다. 그치만 일단은 문제를 어떻게 풀어가야할 지 생각하기 위해 무식.. 2023. 3. 23. 이전 1 다음
