# Divide and conquer

kldaji

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

babypotatotang

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

babypotatotang

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

heejun32

백준 1780번: 종이의 개수

skydreamer21

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

heejun32

백준 1992번: 쿼드트리

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의 끝인지

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를 ' '로 초기화 한다.