Tags

267 pages

Implementation

[Algorithm] C++ 백준 3654번 : L퍼즐

격자에서 빈 칸을 L자 타일로 겹치지 않게 모두 덮을 수 있는지 판정하는 문제입니다. 그래프 모델링과 최대 유량(디닉) 알고리즘을 활용하여, 각 칸을 노드로 변환하고 L자 타일의 배치 가능성을 간선으로 연결해 해를 구합니다. C++로 효율적으로 구현하는 방법과, 이분 그래프, 유량 네트워크의 개념, 좌표 매핑 및 간선 구성 등 다양한 알고리즘적 아이디어를 다룹니다.
[Algorithm] C++ 백준 3654번 : L퍼즐

[Algorithm] C++/Python 백준 16978번 : 수열과 쿼리 22

백준 16978번 문제는 여러 버전의 수열 상태에서 구간 합 쿼리와 값을 갱신하는 쿼리를 빠르게 처리해야 합니다. 이를 위해 영속적 세그먼트 트리(Persistent Segment Tree)를 활용하여, 각 업데이트마다 새로운 버전을 효율적으로 관리하며, 원하는 시점의 구간 합을 O(log N)에 계산할 수 있습니다. 본 글에서는 문제의 요구사항, 제한 사항, 데이터 구조의 원리와 구현 방법을 상세히 설명합니다.
[Algorithm] C++/Python 백준 16978번 : 수열과 쿼리 22

[Algorithm] C++/Python 백준 12928번 : 트리와 경로의 길이

백준 12928번 트리와 경로의 길이 문제는 N개의 노드와 정확히 S개의 길이가 2인 단순 경로를 갖는 트리의 존재 여부를 판별하는 수학+DP 문제입니다. 각 노드의 차수 분배와 경로 수식 변형을 통해 조건을 수식화하고, N과 S가 작으므로 다이나믹 프로그래밍을 활용해 차수 배치가 충족되는지를 탐색합니다. 수학적 귀납 및 조합 원리를 바탕으로 효율적인 검사를 수행하는 것이 핵심입니다.
[Algorithm] C++/Python 백준 12928번 : 트리와 경로의 길이

[Algorithm] C++/Python 백준 1225번 : 이상한 곱셈

백준 1225번 '이상한 곱셈' 문제는 두 개의 매우 큰 숫자가 주어졌을 때, 각 자리 숫자를 곱해 가능한 모든 조합의 합을 구하는 알고리즘을 구현합니다. 수학적 특성을 활용하여, 각 숫자의 자릿수 합을 곱하는 방식으로 효율적으로 해결하는 방법을 알아봅니다. 시간 복잡도를 낮추는 최적화 아이디어와 실제 C++/Python 코드를 통해 설명합니다.
[Algorithm] C++/Python 백준 1225번 : 이상한 곱셈