고속 푸리에 변환(FFT)의 원리와 다항식 곱셈의 효율적 처리
다항식 $A(x) = \sum_{i=0}^{n} a_i x^i$와 $B(x) = \sum_{i=0}^{m} b_i x^i$가 주어졌을 때, 두 다항식의 곱인 $C(x) = A(x)B(x)$를 구하는 문제를 생각해 봅시다. 일반적인 계수 중심의 곱셈 방식(Convolution)은 $O(nm)$의 시간 복잡도를 가집니다. 하지만 고속 푸리에 변환(FFT)을 이용하면 이를 $O(N \log N)$ 수준으로 최적화할 수 있습니다.
점-값 표현법 (Point-V ...
10월 2일 17:47에 게시됨
ICPC 알고리즘 대비: 순열 생성과 정렬 알고리즘의 핵심 개념
기초 알고리즘 복습 및 심화
순열 생성 문제
입력된 숫자 배열에 대해 모든 가능한 순열을 생성하는 문제는 STL 라이브러리를 활용하면 효율적으로 해결할 수 있다.
class PermutationGenerator {
public:
vector<vector<int>> generateAllPermutations(vector<int>& inputArray) {
sort(inputArray.begin(), inputArray.end());
...
9월 22일 09:38에 게시됨
알고리즘 문제 풀이: 정렬, 우선순위 큐 및 동적 계획법 활용
1. 참가자 순위 결정 및 상위 K명 선정
이 문제는 주어진 기준에 따라 참가자들의 점수를 계산하고, 이를 기반으로 상위 K명의 참가자를 선정하는 문제입니다. 선정된 참가자는 원래의 ID 순서로 정렬하여 출력해야 합니다.
각 참가자는 두 개의 값(x, y)을 가지고 있으며, 최종 점수는 x + 2*y로 계산됩니다. 점수가 같을 경우, 원래 ID가 작은 참가자가 우선순위를 가집 ...
9월 17일 00:51에 게시됨
포브스 부자 순위 조회 시스템
포브스 잡지는 매년 전 세계 최고 부자들의 순위를 발표합니다. 이 문제에서는 특정 연령대 내에서 가장 부유한 사람들을 찾는 시뮬레이션을 구현해야 합니다. N명의 자산 정보가 주어지면, 각 질의에 대해 지정된 연령 범위 [Amin, Amax] 내에서 자산이 가장 많은 M명을 출력하는 것이 목표입니다.
입력 형식
첫 줄에 사람 수 N과 질의 수 K가 주어집니다. 다음 N줄에는 ...
9월 13일 06:50에 게시됨
AtCoder Grand Contest 002 알고리즘 문제 풀이 및 코드 최적화 분석
A - Range Product
주어진 구간 [A, B]에 속한 모든 정수의 곱의 부호를 판별하는 문제입니다. 구간에 0이 포함되면 곱은 0이 됩니다. 모든 수가 양수라면 결과는 양수입니다. 모든 수가 음수라면 음수의 개수(B - A + 1)가 짝수일 때 양수, 홀수일 때 음수가 됩니다.
#include <iostream>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.t ...
9월 9일 12:02에 게시됨
이진 탐색을 활용한 피크 요소 찾기
문제 설명
LeetCode 162번 문제인 "피크 요소 찾기"를 해결하는 방법에 대해 알아보겠습니다. 이 문제에서는 주어진 배열에서 피크 요소(즉, 그 이웃보다 큰 요소)를 찾아야 합니다.
해결 전략
배열의 인접한 요소들은 서로 같지 않으며, 피크는 여러 개 존재할 수 있습니다. 전체 배열의 최댓값은 항상 피크 중 하나입니다. 따라서 단순히 배열을 순회하며 최 ...
9월 9일 01:15에 게시됨
선택 정렬 알고리즘의 동작 원리 및 자바 구현 분석
선택 정렬 개요
선택 정렬 (Selection Sort) 은 정렬되지 않은 데이터 집합에서 가장 작은 (또는 큰) 값을 찾아 해당 위치로 이동시키는 반복적인 과정을 기반으로 합니다. 기본적으로 전체 데이터를 두 개의 영역으로 나눕니다. 하나는 이미 정렬이 완료된 부분이고, 다른 하나는 아직 처리되지 않은 미정렬 부분입니다.
동작 메커니즘
오름차순 정렬을 기준으로 설명하 ...
9월 4일 17:05에 게시됨
링크드리스트 문제 해결 전략 및 예제 코드
링크드리스트 문제를 해결할 때 가장 먼저 기억해야 할 점은 가상의 헤드 노드를 설정하는 것입니다.
LeetCode 24: 두 노드씩 교환하기
주어진 링크드리스트에서 두 개의 노드씩 교환하는 문제입니다. 이때 중요한 것은 적절한 위치의 노드를 참조하는 것입니다. 특히 두 개의 노드를 교환하기 전의 노드를 기억해야 합니다.
class Solution {
public ListNode swapPai ...
9월 2일 03:46에 게시됨
그리디와 동적 계획법을 활용한 코딩 테스트 문제 풀이
1. 주택 구매를 통한 안락함의 최댓값 계산
n명의 친구가 각각 일정량의 금화를 가지고 있고, m개의 매물이 있는 부동산 시장에서 주택을 구매하려고 합니다. 각 주택은 '안락함'과 '가격'이라는 두 가지 속성을 가집니다. 구매 조건은 다음과 같습니다.
한 사람은 최대 하나의 주택만 구매할 수 있습니다.
한 주택은 최대 한 명에게만 팔릴 수 있습니다.
구 ...
8월 23일 15:09에 게시됨
식별자 컨벤션 변환 및 비트마스킹 기반 순열 알고리즘 풀이
1. 카멜 케이스와 스네이크 케이스 변환 알고리즘
프로그래밍에서 자주 사용되는 두 가지 명명 규칙인 카멜 케이스(CamelCase)와 스네이크 케이스(snake_case) 간의 변환을 처리하는 문제입니다. 문제의 핵심은 입력받은 문자열이 유효한 형식인지 판단하고, 카멜 케이스인 경우에만 스네이크 케이스로 변환하는 것입니다.
변환 및 판별 규칙
카멜 케이스: 첫 번째 ...
8월 21일 17:25에 게시됨