C++ STL 알고리즘 핵심 정리 및 활용 가이드
1. 시퀀스 비변경 알고리즘 (Non-modifying Sequence Algorithms)
이 알고리즘들은 컨테이너의 원소를 읽기만 할 뿐, 메모리 상의 원소 값을 직접 수정하지 않습니다.
1.1 원소 탐색 (find, find_if, find_end)
find: 특정 값과 일치하는 첫 번째 원소의 반복자를 반환합니다. 없으면 end를 반환합니다.
find_if: 주어진 조건자(predicate)를 만족하는 첫 번째 ...
7월 24일 07:36에 게시됨
NOI2025 예선 대비 문제 풀이 정리
[NOI2025 예선 R1] A - 기본 사이클 구조
다음의 수학적 원리를 활용한다:
Cayley 정리
n개의 노드가 k개의 연결 성분으로 구성되어 있을 때, 이들을 연결하기 위해 k-1개의 간선을 추가하는 방법의 수는 n^(k−2) × ∏(i=1 to k) size_i이다.
이 정리를 바탕으로, 입력 그래프에 이미 사이클이 존재하는 경우 답을 직접 계산할 수 있다.
반면, 초기 상태에서 사이 ...
7월 24일 03:13에 게시됨
C++ 세그먼트 트리 구현 및 지연 전파(Lazy Propagation) 완벽 가이드
세그먼트 트리(Segment Tree)는 펜윅 트리(Fenwick Tree)와 유사하게 구간 합을 구하는 데 주로 사용되지만, 이 외에도 구간 최소/최대값 탐색, 구간 색칠 등 다양한 구간 연산을 효율적으로 처리할 수 있는 강력한 자료구조입니다. 본 가이드에서는 C++를 사용하여 세그먼트 트리의 기본 구현부터 지연 전파(Lazy Propagation)를 활용한 고급 기법까지 단계별로 다룹니다. ...
7월 23일 20:44에 게시됨
C++ STL 표준 알고리즘 완벽 가이드
1、非수정 시퀀스 알고리즘
이 알고리즘들은 연산 대상 컨테이너의 요소를 변경하지 않습니다.
1.1 find와 find_if
find(begin, end, value): value와 같은 첫 번째 요소를 찾으며, 반복자 반환 (찾지 못하면 end 반환)
find_if(begin, end, predicate): 조건자를 만족하는 첫 번째 요소 찾기
find_end(begin, end, sub_begin, sub_end): 부분 시퀀스가 마지막으로出現하 ...
7월 23일 09:17에 게시됨
C++ 스택과 큐 관련 알고리즘 문제 풀이
문제 1: 최소값 스택push, pop, top 연산을 지원하면서도 상수 시간 내에 최소 요소를 검색할 수 있는 스택을 설계하세요.MinStack 클래스를 구현해야 합니다:MinStack(): 스택 객체 초기화void push(int val): 요소를 스택에 삽입void pop(): 스택 상단 요소 삭제int top(): 스택 상단 요소 반환int getMin(): 스택의 최소 요소 반환, 시간 복잡도 O(1)풀이思路두 개의 스 ...
7월 18일 02:27에 게시됨
분할 정복 및 재귀 알고리즘을 활용한 다항식과 행렬 연산 구현
분할 정복을 이용한 재귀적 다항식 곱셈
다항식 곱셈을 효율적으로 처리하기 위해 분할 정복(Divide and Conquer) 기법을 사용할 수 있습니다. 다항식을 일정한 단위로 분할하여 재귀적으로 곱셈을 수행하며, 이 과정에서 다항식의 덧셈과 뺄셈 함수가 보조적으로 사용됩니다. 다음은 리스트 형태로 인코딩된 다항식을 계산하는 로직입니다.
def add_poly(p1, p2):
le ...
7월 18일 02:22에 게시됨
구간 내 고유 요소 개수 구하기 - 펜윅 트리와 오프라인 처리
이 문제는 주어진 배열의 특정 구간에 존재하는 서로 다른 숫자의 개수를 구하는 것을 목표로 합니다. 이를 해결하기 위해 펜윅 트리(Fenwick Tree)와 오프라인 쿼리 처리 기법을 활용합니다.
펜윅 트리를 사용할 때 핵심은 각 위치에서 해당 요소가 마지막으로 등장한 위치를 추적하고, 새로운 위치에서 등장할 경우 이전 위치의 값을 제거하고 현재 위치를 갱신하는 것 ...
7월 17일 22:50에 게시됨
LCA (최소공통조상) 알고리즘 완벽 가이드
LCA (Lowest Common Ancestor)
LCA(최소공통조상)는 트리에서 두 정점의 가장 가까운 공통 조상을 찾는 문제이다. 트리 관련 알고리즘에서 가장基础的인 개념 중 하나이다.
1. 브루트 포스 방식
가장 간단한 접근법은 직접 위로 올라가며 찾는 것이다. 먼저 각 정점의 깊이(depth)와 부모 정보(fa)를 전처리한다.
알고리즘:
두 정점 u, v 중 더 깊은 정점을 찾는다.
...
7월 17일 22:27에 게시됨
문제 풀이 기록: 다양한 알고리즘 문제들
A. 버스 문제 (3)
주어진 s_i, t_i 값들의 최소와 최대를 각각 L, R로 정의합니다. p < min(s_i)인 경우, 우리는 항상 R까지 이동하게 됩니다. 이후에는 s_i > t_i인 구간만 남게 됩니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e6 + 5;
int n, q, m, mn, mx;
long long w[MAXN], f[MAXN], d[MAXN], a[MAXN], b[MAXN], p[MAXN], z[MA ...
7월 17일 21:06에 게시됨
C++ 환경에서의 효율적 데이터 탐색과 정렬 전략 분석
1. 정렬된 시퀀스 기반 검색 메커니즘
데이터가 순차적으로 정리되어 있는 배열이나 벡터 내 특정 값을 신속하게 locating 하는 것은 알고리즘 설계의 핵심 요소다. 여기서는 대표적인 비선형 탐색 기법 세 가지를 다룬다.
1.1 이분 탐색 (Binary Search)
범위를 반으로 나누어 목표값을 축소하는 고전적인 방법이다. 선형 검색의 O(n) 한계를 극복하고 로그 시간인 O(log ...
7월 17일 06:51에 게시됨