양방향 정렬 문제 해결: Chtholly Tree 활용
Chtholly Tree를 사용할 수 있는데 와선 세그먼트 트리를 쓰겠는가?
:::align{right}
——저우 슈겐
:::
평균 \(O((n + m) \log m)\) 시간 복잡도를 가지는 Chtholly Tree 기반 해결 방안을 제시합니다.
문제 개요
초기 수열 \([1 \dots n]\)이 주어지며, m번의 정렬 연산을 수행합니다:
\(p = 0\): 앞 \(q\)개를 내림차순 정렬
\(p = 1\): \(q\)부터 \(n\)까지를 오름 ...
8월 6일 17:10에 게시됨
USACO 2022년 12월 실버 대회 - Bronze Division 풀이
1. Cow College - 최대 수익 구하기
Farmer John이 소들을 위한 대학을 세우려고 한다. N마리의 소(1 ≤ N ≤ 10^5)가 있으며, 각 소는 최대 c_i(1 ≤ c_i ≤ 10^6)만큼의 학비를 낼 의향이 있다. 등록금을 책정했을 때, 소가 지불할 수 있는 최대 금액보다 높으면 해당 소는入学하지 않는다. FJ는 최대 수익을 얻고자 하며, 그때의 등록금을 구해야 한다. 여러 답이 있다면 가 ...
7월 31일 14:39에 게시됨
자바로 구현한 버블 정렬, 선택 정렬, 삽입 정렬
버블 정렬:
버블 정렬은 배열을 반복적으로 순회하며 두 개의 요소를 비교하고 필요에 따라 교환하는 과정을 통해 정렬을 수행합니다. 이 과정이 배열이 정렬될 때까지 계속됩니다.
특징: 비교적 안정적이며, 작은 크기의 배열에서 잘 작동합니다.
package sorting.example;
public class BubbleSortExample {
private static boolean validateArray(int[] array) {
...
7월 31일 10:38에 게시됨
투 포인터 알고리즘 활용
파트너 매칭
남성과 여성의 매력도 배열에서 차이가 1 이하인 쌍의 최대 개수를 구합니다. 두 배열을 정렬한 후 포인터를 이동하며 매칭합니다.
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
int maleArr[100], femaleArr[100];
int n, m, cnt = 0, i = 0, j = 0;
sort(maleArr, maleArr + n);
sort(femaleArr, ...
7월 29일 18:43에 게시됨
자바스크립트 고급 정렬 알고리즘 구현
셸 정렬
삽입 정렬의 개선된 버전으로, 원소를 멀리 떨어진 요소부터 비교합니다. 전체 배열을 부분 시퀀스로 분할하여 각각 삽입 정렬을 수행한 후 최종적으로 전체 정렬을 완성합니다.
동작 과정
감소하는 증분 시퀀스(t₁, t₂, ..., tₖ) 설정 (tₖ=1)
각 증분 크기별로 부분 배열 분할
부분 배열에 삽입 정렬 적용
function shellSort(arr) {
const len = arr.lengt ...
7월 27일 09:50에 게시됨
힙(Heap) 자료구조
목차
기초 지식
이진 트리
포화 이진 트리
완전 이진 트리
정의
인터페이스 (최소 힘 예시)
노드 삽입 - push
노드 삭제 - pop
힙 구축 - make_heap
힙 정렬 - heap_sort
요약
1. 기초 지식
이진 트리:
n개의 노드로 구성된 트리 형태의 자료 구조로, 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.
포화 이진 트리:
각 레벨의 노드 수가 최대로 채워져 ...
7월 19일 20:28에 게시됨
ABC388 문제 해설 및 코드 풀이
C 문제: 과자 쌍 찾기
각 과자에 대해 크기의 두 배 이상인 과자를 이진 탐색으로 찾아, 이 과자와 쌍을 이룰 수 있는 과자의 수를 계산합니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
int n;
cin >> n;
vector<int> desserts(n);
...
7월 17일 07:24에 게시됨
로구 P2672 영업사원 문제 해결 (탐욕 알고리즘, 시뮬레이션)
해결 접근법
첫 번째 방법:
i번 가게를 선택하는 경우, 명백하게 a 값이 가장 큰 i-1개 가게는 반드시 선택해야 합니다. 따라서 마지막 가게 선택 방식만 고려하면 됩니다.
a 값이 i번째로 큰 가게를 선택하는 방법과, 남은 가게 중 s 값이 가장 큰 가게를 선택하는 방법 중에서 선택해야 합니다.
각 가게의 정보(s와 a)를 구조체에 저장한 후, a 값을 기준으로 내림차순으 ...
7월 8일 19:16에 게시됨
C++ STL 알고리즘 가이드
1. 변경하지 않는 순차 알고리즘
이러한 알고리즘은 작업 중인 컨테이너의 요소를 변경하지 않습니다.
1.1 find 및 find_if
find(시작, 끝, 값): 값과 같은 첫 번째 요소를 찾아 반복자를 반환 (찾지 못하면 끝 반환)
find_if(시작, 끝, 술어): 술어(predicate)를 만족하는 첫 번째 요소를 찾음
find_end(시작, 끝, 부분시작, 부분끝): 하위 시퀀스가 마지막으로 나타나는 ...
7월 8일 01:32에 게시됨
PTA 배열과 정렬, 탐색 문제 풀이 및 핵심 알고리즘 설명
함수형 문제풀이
6-1 2차원 배열에서 최댓값과 그 위치 찾기
이 문제는 이중 반복문을 통해 2차원 배열 전체를 순회하며 최댓값과 해당 인덱스를 추적하는 기본적인 탐색 문제다. 전역 변수 Row와 Col에 최댓값의 위치를 저장해야 하며, 초기값 설정 시 주의가 필요하다.
int fun(int arr[4][M]) {
int maxVal = arr[0][0];
Row = 0; Col = 0;
for (int i = 0; ...
6월 28일 23:45에 게시됨