주제

#divide-and-conquer

10편의 기록

백준 2104번 부분배열 고르기

2021년 12월 6일 #divide-and-conquer #segment-tree #cpp #ps

백준 2104번 부분배열 고르기 풀이. 구간 최솟값의 인덱스를 기준으로 분할 정복하며 부분배열 합과 최솟값의 곱을 최대화한다.
백준 6549번 히스토그램에서 가장 큰 직사각형

2021년 11월 29일 #divide-and-conquer #segment-tree #cpp #ps

백준 6549번 히스토그램에서 가장 큰 직사각형 풀이. 최소 높이 막대를 기준으로 구간을 나누고 세그먼트 트리로 최솟값 인덱스를 찾는다.
백준 11049번 행렬 곱셈 순서

2021년 11월 20일 #divide-and-conquer #dp #cpp #ps

백준 11049번 행렬 곱셈 순서 풀이. 시작과 끝 행렬 범위를 상태로 두고 분할 지점별 곱셈 비용의 최솟값을 메모이제이션한다.
백준 2263번 트리의 순회

2021년 11월 1일 #divide-and-conquer #cpp #ps #tree

백준 2263번 트리의 순회 풀이. inorder와 postorder의 인덱스 범위만 넘기며 루트와 서브트리 크기를 찾아 preorder를 출력한다.
백준 1629번 곱셈

2021년 9월 18일 #divide-and-conquer #ps #python

백준 1629번 곱셈 풀이. 거듭제곱을 반으로 나눠 재사용하는 분할 정복과 모듈러 연산으로 O(log N)에 값을 계산한다.
백준 9663번 N-Queen

2021년 7월 15일 #backtracking #ps #python #divide-and-conquer

백준 9663번 N-Queen 풀이. 1차원 배열로 퀸의 위치를 표현하고 열과 대각선 충돌을 검사하는 백트래킹 방법을 설명한다.
백준 15649번 N과 M

2021년 7월 12일 #backtracking #ps #python #divide-and-conquer

백준 N과 M 시리즈 풀이. 방문 여부, 오름차순 조건, 중복 제거 조건을 조합해 여러 백트래킹 문제를 한 흐름으로 정리한다.
백준 1074번 Z

2021년 7월 11일 #divide-and-conquer #ps #python

백준 1074번 Z 풀이. 전체 배열을 실제로 만들지 않고, 목표 좌표가 속한 사분면만 따라가며 방문 순서를 누적한다.
백준 2630번 색종이 만들기

2021년 5월 24일 #divide-and-conquer #ps #python

백준 2630번 색종이 만들기 풀이. 종이를 네 조각으로 재귀 분할하며 한 색으로만 이루어진 영역의 개수를 센다.
백준 1992번 쿼드트리

2021년 5월 23일 #divide-and-conquer #ps #python

백준 1992번 쿼드트리 풀이. 이미지를 네 영역으로 나누고 같은 값으로 압축 가능한지 확인하는 재귀 분할 방식을 설명한다.