데이터 구조 활용 알고리즘 풀이: 시뮬레이션 대회 기법 분석
문제 풀이 개요
이번 기술 평가에서는 다양한 데이터 구조 및 알고리즘 패턴을 요구하는 네 가지 문제를 다뤘습니다. 전반적으로 전처리 기법과 효율적인 데이터 접근 방식이 핵심이었으며, 다음과 같이 분류할 수 있습니다.
T1: 수직선상에서의 가중치 구간 합 계산 (좌표 압축 및 누적 합)
T2: 트리의 서브트리 내 희귀 요소 카운팅 (DFS 및 비트집합 병합)
T3: 제한 조 ...
8월 18일 01:36에 게시됨
문자열 해시와 선분 트리, 트리 DP, 비트셋을 활용한 정사각형 탐색 문제 풀이
문제 1: 동적 문자열 집합에서 고유 문자열 수 계산
여러 개의 동일 길이 문자열이 주어지고, 각 쿼리마다 특정 문자열의 부분 구간을 같은 문자로 덮어쓴 후, 전체 집합 내 서로 다른 문자열의 개수를 출력해야 한다.
해결 핵심은 다음과 같다:
각 문자열의 해시 값을 효율적으로 갱신하기 위해 게으른 전파(lazy propagation)가 가능한 선분 트리를 사용한다.
해시 ...
7월 20일 20:48에 게시됨
세그먼트 트리와 비트셋을 활용한 쿼리 문제 해결 (Codeforces Round #538 Div.2 F)
문제 개요
주어진 배열에서 구간 곱과 그 결과에 대한 오일러 피 함수 값을 계산하는 문제입니다. 핵심 아이디어는 오일러 피 함수의 성질과 300 이하의 소수가 62개뿐이라는 점을 활용하는 것입니다.
수학적 배경
구간 [l, r]의 곱을 X라고 할 때, X를 소인수분해하면 다음과 같습니다:
X = ∏ p_i^{c_i} (i = 1 to n)
오일러 피 함수는 곱셈적 함수이므로:
φ(X) = φ(∏ ...
6월 29일 00:36에 게시됨
비트셋에서 set과 reset 연산의 범위가 성능에 미치는 영향 분석
1. bitset의 대량 조작이 프로그램 효율성에 미치는 영향
고성능 알고리즘 구현 시 std::bitset은 불리언 상태를 압축하여 관리하는 핵심 도구로 사용된다. 특히 그래프 탐색, 조합 최적화, 상태 추적 등에서 빈번히 활용되며, 이때 set()과 reset() 메서드의 호출 방식이 전체 실행 시간에 결정적인 영향을 줄 수 있다.
주목할 점은 전체 비트 초기화와 개별 비트 조작 ...
5월 27일 20:48에 게시됨