# 분할정복

222개의 포스트
post-thumbnail

[백준 1992] - 쿼드트리(Silver I)

처음에 봤을 때 예제가 이해가 안 되서 고민했었던 문젠데, 예제를 이해하고 나선 그동안 풀었던 종이 자르는 재귀 문제와 거의 비슷해 쉽게 풀 수 있었던 문제이다. 역시 한 번이라도 스스로 풀어본 문제 유형은 기억에 잘 남는 것 같다.

2023년 1월 20일
·
0개의 댓글
·

BOJ_1992 C++

문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현

2023년 1월 11일
·
0개의 댓글
·
post-thumbnail

백준 2630 C++ 색종이 만들기

재귀로 분할정복하자

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

[1629] 곱셈

알고리즘 문제를 푸는 과정에서 결과 값이 매우 큰 경우에 결과값의 나머지를 구하라는 문제가 자주 등장하는데, 특히 파이썬의 경우에는 수가 커지면 곱셈에 거리는 시간도 그만큼 오래걸린다고 한다.

2023년 1월 5일
·
0개의 댓글
·

BOJ 1074 (Z)

쉽게 쉽게 가자고. 컴파일러가 불쌍하다.

2023년 1월 2일
·
0개의 댓글
·
post-thumbnail

[ 알고리즘 ] Sparse Table(희소 행렬)

- 모든 정점의 나가는 간선이 정확히 1개인 유향 그래프 이 그래프에서 어떤 정점에서 출발하여 '$K$'번 이동 후 도착하는 정점을 구하는데, $K$가 매우 클 경우 선형적으로 정점들을 하나 하나 따라가는 방법은 시간이 매우 크게 걸릴 수 있습니다. 행렬의 거듭 제곱에서 분할 정복으로 해를 구했듯이, 이 문제도 분할 정복을 사용하여 $O(logN)$의 ...

2023년 1월 2일
·
0개의 댓글
·
post-thumbnail

[백준 1629] 곱셈 - Rust로 알고리즘 풀기

썸네일 출처: https://ye-yo.github.io/thumbnail-maker/1629번: 곱셈분할정복을 이용해서 곱셈의 계산 횟수를 줄이는 문제10을 11번 곱하는 계산을 단순하게 하면 총 10번의 계산이 필요하다. 시간복잡도로 표현하면 O(n)이다.

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

Merge Sort

수 많은 종류의 정렬 알고리즘이 존재한다. 하지만 비교적 많이 사용되는 기법은 병합정렬(Merge Sort)과 퀵정렬(Quick Sort) 정도다. 정렬 알고리즘 시간 복잡도 비교 병합정렬은 Best, Average, Worst case 모두 O(nlogn)을 보장

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

[ 알고리즘 ] lower_bound, upper_bound

Lowerbound, upperbound 모두 이분탐색에서 파생된 것으로 역시 자료들이 정렬되어 있어야 합니다. > - Lower_bound : 원하는 값 target 이상의 값이 처음으로 나오는 위치를 찾는 알고리즘 > - Upper_bound : 원하는 값 target 을 초과하는 값이 처음으로 나오는 위치를 찾는 알고리즘 Upperbound의 ...

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

[백준] 1780번 - 종이의 개수 Python 파이썬

종이의 개수분할정복을 이용하면 된다.1\. 영역 내 모든 숫자가 -1, 0, 1로 동일하다면 해당 숫자의 count를 세는 변수를 +1 해준다.    \- count 변수는 global 선언하여 함수를 빠져나온 뒤에도 값이 유지되게 설정했다.    \- -1, 1이 포

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

[백준] 1992번 - 쿼드트리 Python 파이썬

쿼드트리분할정복을 이용하면 된다1\. 영역 내 모든 숫자가 0 또는 1로 동일하다면 해당 값을 출력해준다.2\. 동일하지 않다면 영역을 4분면으로 쪼개서 각 영역에 대해서 0 또는 1로 동일한지 확인한다.       \- 2번 작업의 결과물을 출력할 때는 앞 뒤에 괄호

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

[백준/java] 1992. 쿼드트리

문제 링크 - https://www.acmicpc.net/problem/1992 🌱 문제 🌱 풀이 🌱 코드

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

백준 1074번 Z

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.주석을 참고해주세요.

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

백준 1629번

자연수 A를 B번 곱한 수를 알고 싶다.단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.첫

2022년 11월 19일
·
0개의 댓글
·

알고리즘(algorithm)

9세기경 수학자 알콰리즈미(Al Khwarizmi)의 이름에서 유래문제의 복잡성에 따라 컴퓨터 프로그램을 통하여 문제를 해결할 수 있는 것알고리즘 컴퓨터 프로그램을 작성하는 바탕이 되는 것어떤 작업을 수행하기 위해 입력 받아 원하는 출력을 만들어내는 과정을 기술한 것작

2022년 11월 11일
·
0개의 댓글
·

[백준] 1992.쿼드트리

https://www.acmicpc.net/problem/1992흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이

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

[백준] 2630. 색종이 만들기

https://www.acmicpc.net/problem/2630전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서

2022년 11월 4일
·
0개의 댓글
·
post-thumbnail

분할 정복/병합 정렬

📚분할 정복과 병합 정렬

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

[c++/백준] 1629번: 곱셈

분할 정복을 이용하는 문제

2022년 10월 31일
·
0개의 댓글
·