2024년 11월 기초 알고리즘 문제 풀이
A. 구간 나누기
문자열 내에서 연속된 '1'은 서로 독립적인 구간으로 처리할 수 있다. 각 구간에 대해 최적의 분할 방식을 고려해야 한다. 길이가 \( k \) 인 연속된 1의 블록이 있을 때, 다음과 같은 전략이 최선이다:
\( k \)가 홀수면, \( \frac{k+1}{2} \) 개의 단일 1로 나누며, 이때 결과는 \( \frac{k+1}{2} \).
\( k \)가 짝수면, \( \frac{k}{2} - 1 \) ...
7월 17일 06:37에 게시됨
알고리즘 문제 해결: 문자열 뒤집기 및 문자 교체
문자열 뒤집기
해결 접근법:
양쪽 끝에서 시작하는 이중 포인터를 사용하여 문자 순서를 교환하다가 좌우 포인터가 만날 때까지 반복합니다;
이 문제에는 또한 XOR 연산자를 활용한 요소 교환 방식도 있습니다.
public void reverseString(char[] s) {
// 이중 포인터 방식으로 문자 순서 교환
int left = 0;
int right = s.length - 1;
while(left < ...
7월 16일 19:45에 게시됨
주어진 범위 내 인접 소수 간 거리 찾기
주어진 정수 범위 [L, R] 내에서 서로 가장 가까운 두 소수와 가장 먼 두 소수를 찾는 문제를 다룹니다. 이 문제는 에라토스테네스의 체와 분할 체(Segmented Sieve) 기법을 활용하여 효율적으로 해결할 수 있습니다.
알고리즘 개요
작은 소수들을 위한 에라토스테네스의 체 실행:
[L, R] 범위의 수들을 체로 거르기 위해서는 R의 제곱근(sqrt(R))까지의 모 ...
7월 15일 17:32에 게시됨
CSP-J/S 2023 대회 후기
이 글은 Oler의 대회 후기이며, 추후 상세한 수정이 있을 예정입니다.
참고: 특별한 사정으로 인해 시험 당일에 후기를 작성하지 못해 아쉬움이 큽니다.
업데이트 (2023-11-20): 합격선이 발표되었는데, 간신히 일반전형 1차 합격선에 들었습니다.
시험 전날
"마지막 밤이니 템플릿이나 외우자"
템플릿 몇 개를 외웠다... (시험장에서 하나도 사용하지 못함)
"정신을 위 ...
7월 15일 16:10에 게시됨
고정밀도 연산 기법
일반적으로 정수 덧셈, 뺄셈, 곱셈, 나눗셈은 프로그래밍 언어에서 기본적으로 제공하는 연산자 (`+`, `-`, `*`, `/`)를 사용하여 처리합니다. 하지만 처리해야 할 숫자의 길이가 100자리, 1000자리에 달하는 등 매우 길어질 경우, `int`나 `long long`과 같은 기본 자료형의 표현 범위를 초과하게 됩니다. 이럴 때 사용하는 것이 바로 고정밀도(High Precision) 연산 기법 ...
7월 14일 21:45에 게시됨
C++ STL 알고리즘 라이브러리 완벽 가이드
1. 비변형 시퀀스 알고리즘원본 컨테이너의 요소를 변경하지 않는 알고리즘들입니다.1.1 find 계열find(first, last, val): 첫 번째로 val과 일치하는 요소의 반복자 반환find_if(first, last, pred): 조건을 만족하는 첫 번째 요소 탐색find_end(first, last, s_first, s_last): 부분 시퀀스의 마지막 등장 위치std::vector<int> data = {2, 4, 6, 8, 10};
// 값이 ...
7월 13일 20:35에 게시됨
정수 배열에서 최대 부분 배열 합 찾기: 세 가지 접근 방식
정수 배열이 주어졌을 때, 그 안에서 연속된 부분 배열 중 합이 가장 큰 부분 배열을 찾아 그 합을 반환하는 것은 고전적인 알고리즘 문제입니다. 이 문제는 다양한 최적화 기법을 통해 해결할 수 있으며, 여기서는 세 가지 주요 접근 방식인 무차별 대입(Brute Force), 분할 정복(Divide and Conquer), 그리고 동적 계획법(Dynamic Programming)을 다룹니다. 특히, 대규모 ...
7월 13일 17:10에 게시됨
점분치 학습 노트
점분치란
트리 구조상의 경로 문제를 해결하기 위해 분치 tư duy를 적용하는 기법입니다. 경로를 두 부분으로 나눌 때, 하나는 중앙 노드를 지난 경로이고, 다른 하나는 중앙 노드를 지난 경로가 아닙니다.
중앙 노드를 지난 경로를 처리할 때는 분치 tư duy를 재귀적으로 하여 서브 트리로 문제를 전가합니다. 기본적으로 O(n²)의 복잡도를 가지지만, 각 단계에서 서브 트 ...
7월 13일 01:18에 게시됨
오일러 함수의 성질과 계산 방법
오일러 함수 φ(n)은 1부터 n까지 n과 서로 소인 수의 개수를 나타냅니다. 두 수 a와 b가 서로 소일 때 gcd(a,b)=1이 성립합니다.
재귀적 계산식
임의의 양의 정수 a에 대해 다음 식이 성립합니다:
φ(ab) = φ(a)×φ(b)×gcd(a,b)/φ(gcd(a,b))
a와 b가 서로 소일 경우 φ(ab) = φ(a)×φ(b)가 됩니다.
증명
n을 소인수 분해한 후 φ(n)을 계산하는 방식을 통해 증명할 수 있습니 ...
7월 11일 23:00에 게시됨
전략 패턴: 유연한 알고리즘 설계 방법론
전략 패턴(Strategy Pattern)은 행위 디자인 패턴 중 하나로, 관련된 알고리즘 패밀리를 정의하고 각각을 캡슐화하여 상호 교체 가능하게 만듭니다. 이 패턴을 사용하면 알고리즘을 사용하는 클라이언트로부터 알고리즘을 독립적으로 변경할 수 있으며, 실행 중에 알고리즘을 동적으로 전환할 수 있습니다.
전략 패턴의 핵심 구성 요소:
전략 인터페이스(Strategy Interfa ...
7월 11일 02:30에 게시됨