본문 바로가기
반응형

분할정복10

04.02. 부분배열 고르기[Divide and conquer][백준 2104] https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net Algorithm classification : Divide and conquer, Strack, Data structure, Segment tree 04.02.1. Problem One-dimensional array A[1], … of size N (1 ≤ N ≤ 100,000). , A[N]. The .. 2021. 11. 21.
04.01. 곱셈[Divide and conquer][백준 1629] https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net Algorithm classification : Divide and conquer, Math 04.01.1. Problem I want to know the number of times a natural number A multiplied by B times. However, since the number to be found can be very large, write a program to find the remainder after dividing it b.. 2021. 11. 21.
08. Divide and Conquer(2) Decrease-and-Conquer 01. Decrease-and-conquer technique is based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance such a relationship is established, it can be exploited either top down or bottom up Top down > implemented recursively (ultimate implementation may well be nonrecursive) Bottom up > implemented iteratively (Sta.. 2021. 11. 21.
07. Divide and Conquer(1) 안녕하세요. 오늘은 Divide and Conquer. 한국어로는 분할정복이라고 불리는 알고리즘을 소개할까 합니다. 정말 유명한 알고리즘입니다. 다만, Search, DP, Greedy에 비해는 등장빈도가 조금 낮다고 할 수 있습니다. 분할하고 정복하기 분할 : 주어진 문제를 여러개의 부분 문제로 나눈다 정복 : 분할된 문제를 푼다. 이때 문제의 크기가 작아지면 풀기 쉽다는 것을 이용한다. 분할정복 문제 자체는 등장빈도가 조금 낮을 수 있다고 말씀드렸지만, 분할이라는 접근은 매우 유용하기 때문에 다른 자료구조나 알고리즘의 basic이 되는 경우가 많습니다. 정복을 설명하면서 문제의 크기가 작아지면 풀기 쉽다는 것을 이용한다고 말씀드렸는데요. Resursive function의 base case처럼 바로 .. 2021. 11. 18.
반응형