목록분할 정복(Divide and Conquer) (6)

Always Be Wise

분할 정복 : 가장 가까운 두점(백준 2261번)

▶ 문제 : https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net ##### 문제 ##### # 2차원 평면상에 n개의 점이 주어졌을 때, # 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. # 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. # 각각의 좌표는 절댓값이 10,000을 넘지 않는 정..
알고리즘/백준 2021. 11. 17. 23:21
분할 정복 : 행렬 제곱(백준 10830번)

▶ 문제 : https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net ##### 문제 ##### # 크기가 N*N인 행렬 A가 주어진다. # 이때, A의 B제곱을 구하는 프로그램을 작성하시오. # 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. ##### 입력 ##### # 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) # 둘째 줄부터 N개의 줄에 행렬의 각 원소가..
알고리즘/백준 2021. 11. 17. 23:18
분할 정복 : 히스토그램에서 가장 큰 직사각형(백준 6549번)

▶ 문제 : https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net ##### 문제 ##### # 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. # 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. # 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. ##### 입력 ##### # 직사각형의 수 n이 가장 처음으로 주어진다. (1..
알고리즘/백준 2021. 11. 17. 23:16
분할 정복 : 곱셈(백준 1629번)

▶ 문제 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net ##### 문제 ##### # 자연수 A를 B번 곱한 수를 알고 싶다. # 단, 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. # A, B, C는 모두 2,147,483,647 이하의 자연수이다. ##### 출력 ##### # 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. ▶ 접근 방법 ▶ ..
알고리즘/백준 2021. 11. 17. 23:14
분할 정복 : 색종이 만들기(백준 2630번)

▶ 문제 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net ##### 문제 ##### # 입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 # 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. # N은 2, 4, 8, 16, 32, 64, 128 중 하나이..
알고리즘/백준 2021. 11. 17. 23:11
분할 정복(Divide and Conquer)이란?

분할 정복법은 주어진 문제를 부분 문제로 나누고(Divide), 각각의 부분 문제들을 해결/정복(Conquer)하여 본래의 문제를 해결하는 알고리즘을 의미한다. # 분할정복을 이용하여 1부터 N까지의 합 구하기 def consecutive_sum(start, end) if start == end: return start mid = (start + end) // 2 return consecutive_sum(start, mid) + consecutive_sum(mid+1, end) ▶ 관련 링크
알고리즘/개념 2021. 11. 17. 23:08
Prev 1 Next