Algorithm BOJ Game Theory Greedy

[Algorithm] C++ 백준 17965번: Absolute Game

각자 자신의 배열에서 하나만 남길 때까지 번갈아 삭제한다. 게임 값은 max_x min_y |x-y|로 환원되며, b를 정렬한 뒤 각 a의 최근접 거리 최댓값을 lower_bound로 계산한다.

Algorithm BOJ Math FFT Convolution Geometry

[Algorithm] C++ 백준 20176번: Needle

세 장벽(위·중·아래) 구멍 3점이 일직선이면 중간 x는 위·아래 x의 평균이다. 위/아래 좌표를 0/1 배열로 만든 뒤 FFT 컨볼루션으로 합=2xm 쌍을 세어 O(R log R)에 통로 개수를 구한다.

Algorithm BOJ Tree LCA

[Algorithm] C++ 백준 20506번: Kaisar - 생존

트리에서 모든 순서쌍 (x,y)의 LCA를 모아 정렬한 뒤 홀수/짝수 위치 합을 구한다. 각 정점이 LCA가 되는 쌍의 개수를 서브트리 크기 제곱으로 O(N)에 계산한다.

Algorithm BOJ Math Sorting

[Algorithm] C++ 백준 22878번: 간단한 문제

점 (p_i,q_i) 쌍에 대해 모든 i,j의 min(|p_i-p_j|,|q_i-q_j|) 합을 구한다. max(|dx|,|dy|)=(|dx+dy|+|dx-dy|)/2를 이용해 p,q,p+q,p-q를 정렬·누적합으로 처리한다.

Algorithm BOJ Math Implementation

[Algorithm] C++ 백준 25201번: 보드 뒤집기 게임

2×2 블록 뒤집기는 각 행·열에서 색이 바뀌는 칸 수의 홀짝을 보존한다. 현재/목표 빨간 칸의 대칭차를 만들고 행·열별 등장 횟수가 모두 짝수인지 확인하면 O(N+M)으로 YES/NO를 판정한다.

Algorithm BOJ DP Greedy Sorting

[Algorithm] C++ 백준 2586번: 소방차

펌프/소방차 좌표를 정렬한 뒤 depth 버킷으로 분해하고, 각 버킷에서 인접 매칭과 1개 제외 DP로 최소 호스 길이 합을 O((P+F) log (P+F))에 계산한다.

Algorithm BOJ Graph Functional Graph

[Algorithm] C++ 백준 2988번: 아보가드로

3×N 표에서 열을 삭제한 뒤 각 행을 정렬했을 때 열별 값이 일치하도록 만든다. 첫 행이 순열임을 이용해 값→값 함수 두 개를 만들고, 두 함수의 순환(cycle)만 남기는 폐포를 BFS로 구해 삭제 최소를 계산한다.

Algorithm BOJ Data Structure Fenwick Tree Prefix Sum

[Algorithm] C++ 백준 3006번: 터보소트

홀수 단계는 가장 작은 수를, 짝수 단계는 가장 큰 수를 인접 스왑으로 제자리로 보낸다. 각 단계의 스왑 횟수는 현재 위치 기준 남아있는 원소 수의 prefix/suffix 합이다. Fenwick Tree로 삭제와 합 쿼리를 O(log N)에 처리한다.

Algorithm BOJ Game Theory Greedy Sorting

[Algorithm] C++ 백준 32115번: 돌 놓기 게임

원형 보드를 돌-돌 사이의 빈 구간으로 분해한다. 같은 색 끝 구간은 독점, 다른 색 끝 구간은 양쪽 절반을 가져가고 홀수 길이는 가운데 값만 남는다. 남은 가운데 값들을 내림차순 정렬해 번갈아 더해 O(N log N)으로 점수를 구한다.

Algorithm BOJ Constructive Math

[Algorithm] C++ 백준 32190번: Ian Sequences

1..N이 각각 두 번 등장하는 길이 2N 수열을 구성한다. S_N=[N,N-1]+S_{N-2}+[N,N-1]로 감싸며 (N-1)^2≡1, N≡1(mod N-1)로 모듈 조건을 귀납적으로 증명한다. 홀짝 베이스(S1,S2)에서 시작해 덱으로 O(N)에 생성·출력한다.

Algorithm BOJ Data Structure Sorting Binary Search Prefix Sum

[Algorithm] C++ 백준 33543번: 둘이 한 팀

A,B 전체에 동일 증가가 반복된다. d=A-B를 정렬하고 delta=addA-addB로 흡수해 Σmax(d+delta,0)을 upper_bound와 누적합으로 O((N+Q)logN)에 계산한다.

Algorithm BOJ Combinatorics DP

[Algorithm] C++ 백준 3948번: 홍준이의 친위대

양끝을 제외한 모든 위치가 지역 최솟값/최댓값이 되도록 하는 순열을 센다. 이는 up-down(교대) 순열과 동치이며 Entringer 수 DP로 N≤20에서 오일러 지그재그 수를 빠르게 구한다.

Algorithm BOJ DP Convex Hull Trick

[Algorithm] C++ 백준 5498번: Batch Scheduling

연속 작업을 배치로 나눌 때 총 비용(출력시간×가중치)을 최소화한다. DP 점화식을 정리해 일차함수 최소화 형태로 만들고, 단조 조건을 이용한 Convex Hull Trick으로 O(N)~O(N log N)에 해결한다.

Algorithm BOJ Graph Tree Grid Shortest Path

[Algorithm] C++ 백준 5813번: 이상적인 도시

격자 도시(구멍 없음)의 최단거리 합을 행/열 연속구간으로 압축해 두 가중 트리로 분해한다. 각 트리에서 간선 절단 시 양쪽 가중치 곱을 합산해 O(N log N)으로 1e9 모듈 답을 구한다.

Algorithm BOJ Greedy Sorting

[Algorithm] C++ 백준 6223번: Cow Sorting

스왑 비용이 두 소의 값 합일 때, 순열 사이클 분해로 최소 비용을 계산한다. 사이클 내부 교환과 전체 최소값 보조 교환을 비교해 O(N log N)으로 해결한다.

Algorithm BOJ String DP Divide and Conquer

[Algorithm] C++ 백준 7727번: Byephone

두 문자열(각 ≤10000)의 LCS 길이와 수열을 3MB 메모리로 출력한다. Hirschberg 분할정복으로 DP 2행만 유지해 O(nm) 시간, O(min(n,m)) 공간에 LCS를 복원한다.

Algorithm BOJ Data Structures Stack Greedy

[Algorithm] C++ 백준 8155번: Postering

건물의 폭 d는 결과에 영향이 없고 높이만 보면 된다. 단조 스택으로 스카이라인 높이 변화를 추적하며, 높이가 내려갈 때마다 완료된 포스터를 카운트해 O(N)에 최소 포스터 수를 구한다.

English Vocabulary

[Vocabulary] cynicism의 의미와 쓰임 - 명사 핵심 정리

영어 명사 'cynicism'의 핵심 뜻(냉소주의, 사람의 동기에 대한 불신, 부정적 태도)을 정리한다. 철학, 심리학, 뉴스, 일상 표현에서 자주 쓰이는 정확한 용법을 콜로케이션과 EN/KR 예문 50개로 익힌다. 정치, 사회, 개인 관계, 비즈니스에서 반복 등장하는 중요한 명사.

English Vocabulary

[Vocabulary] run-down의 의미와 쓰임 - 형용사 핵심 정리

영어 형용사 'run-down'의 핵심 뜻(낡은, 쇠퇴한, 피곤한)을 정리한다. 건물, 상태, 사람의 컨디션을 표현하는 정확한 용법을 콜로케이션과 EN/KR 예문 50개로 익힌다. 뉴스, 일상 표현, 부동산 분야에서 반복 등장하는 중요한 형용사.

English Vocabulary

[Vocabulary] paleolithic의 의미와 쓰임 - 형용사 핵심 정리

영어 형용사 'paleolithic'의 핵심 뜻(구석기의, 구석기 시대와 관련된, 구식의)을 정리한다. 고고학, 역사, 인류학, 일상 표현에서 자주 쓰이는 정확한 용법을 콜로케이션과 EN/KR 예문 50개로 익힌다. 교육, 과학, 뉴스 분야에서 반복 등장하는 중요한 형용사.