# Divide and conquer

55개의 포스트

leetcode: 215. Kth Largest Element in an Array

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

2022년 6월 22일
·
0개의 댓글
post-thumbnail

2. Divide and Conquer : Mergesort

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

2022년 6월 12일
·
0개의 댓글
post-thumbnail

2. Divide and Conquer : Multiplication

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

2022년 6월 12일
·
0개의 댓글

[백준] 1780번 파이썬

백준 1780번: 종이의 개수

2022년 6월 3일
·
0개의 댓글
post-thumbnail

Merge Sort (병합정렬)의 이해

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

2022년 6월 1일
·
0개의 댓글

[백준] 1992번 파이썬

백준 1992번: 쿼드트리

2022년 5월 31일
·
0개의 댓글
post-thumbnail

1802 - 종이 접기

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

2022년 5월 20일
·
0개의 댓글

2104. 부분배열 고르기

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

2022년 5월 16일
·
0개의 댓글
post-thumbnail

[BOJ] 2630 색종이 만들기

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

2022년 5월 8일
·
0개의 댓글

2263. 트리의 순회

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

2022년 4월 15일
·
0개의 댓글

[c++] 백준 10830, 행렬 제곱

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

2022년 3월 23일
·
0개의 댓글
post-thumbnail

[백준 5904 - Kotlin] Moo 게임

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

2022년 3월 22일
·
0개의 댓글

10830. 행렬 제곱

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

2022년 3월 20일
·
0개의 댓글

[c++] 백준 1992, 쿼드트리

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

2022년 3월 20일
·
0개의 댓글
post-thumbnail

2448 - 별 찍기 - 11

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

2022년 3월 18일
·
0개의 댓글
post-thumbnail

2447 - 별 찍기 - 10

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

2022년 3월 18일
·
0개의 댓글
post-thumbnail

1992 - 쿼드트리

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

2022년 3월 18일
·
0개의 댓글
post-thumbnail

11729 - 하노이 탑 이동 순서

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

2022년 3월 18일
·
0개의 댓글

2448. 별 찍기 - 11

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

2022년 3월 18일
·
0개의 댓글