# Divide and conquer

sung-ik-je

어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라 한다코드의 간결화 및 변수 사용 최소화 장점자기 자신을 사용하여 정의ex) n! = n \* (n-1)! 메서드를 계속해서 맞물려 호출하는 경우직접 재귀자기 자신의 메

kldaji

https://leetcode.com/problems/kth-largest-element-in-an-array/

babypotatotang

본 게시물은 교재 “Algorithms,” Sanjoy Dasgupta(2008)를 참고하여 구현한 알고리즘을 공유하는 게시물입니다.

babypotatotang

본 게시물은 교재 “Algorithms,” Sanjoy Dasgupta(2008)를 참고하여 구현한 알고리즘을 공유하는 게시물입니다.

skydreamer21

  여러분들은 방금 MergeSort의 Merge 과정을 직접 해보셨습니다👏이미 각각의 카드팩이 정렬이 되어있으니 단지 각각의 카드팩의 맨앞에서부터 하나씩 뽑아 서로 비교하며 순서대로 나열만 해주면 정렬이 완료되겠죠!위의 카드 정렬이 간단한 예시였지만 사실 Merge

chang626

종이 접기 이분 탐색 문제이다.항상 종이를 절반씩 접는다고 할 때, 제시된 문자열로 종이를 접을 수 있는지 확인하는 문제이다.종이를 절반씩 접게 되면, 항상 접은 부분을 중심으로 양쪽에는 반대로 접힌 흔적이 남게 된다.종이의 길이가 홀수이다.1 : OUT, 종이가 시계

smsh0722

시간 제한: 2초메모리 제한: 128MB가능한 양 끝 i,j의 모든 경우는 n(n+1)/2 가지이다. 대신에, Divide and Conquer로, 좌우로 분할하여 각 구간에서 최대를 찾고, 구간을 합칠 때 경계선에서 만들어지는 경우만 조사하면, 시간 복잡도를 개선할

ssoyeong

https://www.acmicpc.net/problem/2630아이디어재귀 함수 사용하여 divide and conquer 방식으로 풀었다.

smsh0722

시간 제한: 5초메모리 제한: 128MBpostidx는 sub-tree의 root이다. 따라서, post를 거꾸로 순회하면, sub-tree의 root부터시작 해서 자손을 채울 수 있다. 그러나, 각 child의 좌우를 구분할 수 없고, 어디가 sub-tree의 끝인지

ssssujini99

1. 분할정복(Divide and Conquer) > - 대표적인 알고리즘 설계 기법 중 하나 > - 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시

landlala

백준 10830알고리즘 분류 : divide and conquer (분할 정복)크기가 N\*N인 행렬 A가 주어졌을 때, A의 B제곱을 구하는 문제다.B가 1이 될 때까지, 2로 반복해서 나누어 행렬 ans를 구한다.B%2=1인 경우, solve(ans,A)B%2=0인

kldaji

문제링크n의 위치가 S(i)에 존재한다고 가정해봅시다.S(i)는 S(i - 1) + mooo... + S(i - 1) 을 의미하고, n의 위치가 S(i)에 존재한다는 것은 S(i - 1)에는 존재하지 않다는 것을 의미합니다.따라서 S(i)에 존재한다는 것을 알게되었을

kldaji

문제링크

smsh0722

시간 제한: 1초메모리 제한: 256MBNaive하게 B번 곱하면, 시간 복잡도는 O(B)이다. 대신에, A^B 는 A^(B/2)인 것을 이용하면, 시간을 줄일 수 있을 것이다.A^x를 구하기 위해, A^(x/2)를 구한다.A^(x/2)를 제곱하여 A^x를 구한다.x가

landlala

백준 1992알고리즘 분류 : divide and conquer (분할 정복)쿼드트리의 방법을 이용하여 4개의 영역을 압축한 결과를, 차례대로 괄호 안에 묶어서 표현하는 문제다. 재귀를 통해 해결한다.살펴보는 영역 안에 check와 다른 문자가 존재하는 경우, 다음과

chang626

별 찍기 - 11 위 별의 모양이 반복해서 출력된 것을 확인할 수 있다.문제에 나와있는 공식에 따르면 (N = 3 x 2^k)라고 한다.k가 1일 때는 위 별의 모양이 2개가 추가 되는 것이고k가 2일 때는 k가 1일 때 모양을 2개 추가한 것을 알 수 있다.이와 같이

chang626

별 찍기 - 10 재귀적인 패턴으로 별을 찍는다.평소에는 반복문 위주로 사용하여, 이번 문제는 재귀를 이용하여 풀었다.설명 잘되어 있는 블로그현재 n = 3^i일 때, 가운데를 제외한 나머지는 n = 3^(i-1)이다.n이 3^i일 때➡️ \* : 3^(i - 1)이다

chang626

쿼드트리 왼쪽 위 : 1번오른쪽 위 : 2번왼쪽 아래 : 3번오른쪽 아래 : 4번(0, 0) 좌표부터 시작한다.전체 4등분을 해서 1번부터 확인한다.그 구간 전체가 모두 1로만 되어 있으면 압축 결과 1 을 출력그 구간 전체가 모두 0로만 되어 있으면 압축 결과 0을

chang626

하노이 탑 이동 순서 ✔️ 하노이탑 규칙1, 2, 3 탑이 있고 탑의 개수만큼 원판이 있을 때(1) 작은 원반 n - 1개를 A에서 B로 이동한다.(2) 큰 원반 1개를 A에서 C로 이동한다.(3) 작은 원반 n - 1개를 B에서 C로 이동한다.이와 같이 진행된다. 

smsh0722

시간 제한: 1초메모리 제한: 256MB예제를 보니, 기본 삼각형(N=3)으로 패턴이 이루어져 있다. 거꾸로 보면, 삼각형 전체를 출력하기 위해서, 파트를 세 개로 쪼개서 출력하면 된다. DAC로 풀 수 있을 것 같다.NxW char Array를 ' '로 초기화 한다.