[Knapsack Problem] 배낭 문제
배낭 문제(Knapsack Problem)는 배낭에 담을 수 있는 무게의 한도가 정해져 있는 상황에서 물건을 배낭에 최대한으로 담아 배낭에 담긴 물건의 가치를 최대화 하는 문제이다. 배낭에 담는 물건은 무게와 가치를 속성으로 가지며, 배낭은 최대 수용 가능 무게를 속성으로 가진다...
최근 포스트
[Segment Tree] 세그먼트 트리
세그먼트 트리(Segment Tree)는 구간 합 query를 빠르게 수행할 수 있도록 자료를 저장하는 자료구조이다. naive하게 query를 수행하려면 매번 더하기 연산을 일일이 수행해야 하기 때문에, 구간 합 query를 log scale만에 처리해야 하는 경우 Segment...
[Fenwick Tree] 펜윅 트리(= Binary Indexed Tree, BIT)
펜윅 트리(Fenwick Tree)란, 세그먼트 트리에서 한 단계 진화한 자료구조로서 bit 연산을 통해 데이터를 저장하고 관리하는 Tree형 자료구조이다. Fenwick Tree의 시작 index는 1부터 시작하며, 세그먼트 트리와 마찬가지로 배열의 어떠한 연속된 구간의 합을 ...
[Parametric Search] Binary Search를 이용한 정답 도출
Binary Search의 실행 시간이 log scale임을 이용하여 주어진 조건에서 답을 빠르게 구할 수 있다. Binary Search의 경우 Data가 정렬되어 있어야 하므로, 주어진 Data의 order가 명백할 경우 사용할 수 있다. 예를 들어 오름차순 정렬된 list에...
[Shortest Path] 최단거리 알고리즘 : Dijkstra, Bellman - Ford, Floyd - Warshall
Graph에서 최단거리를 구하는 알고리즘인 Dijkstra, Bellman - Ford, Floyd - Warshall에 대해 알아보자. Dijkstra Algorithm Graph의 가중치가 모두 음이 아닌 그래프에서, 특정한 시작 정점 S와 그래프의 다른 모든 점들 사이의 ...
백준 다이아V 달성 후기
백준 다이아V 달성 후기 시작 : 2025.07.03 달성 : 2025.08.25 여름방학 시작부터 약 2달간 열심히 백준을 풀어 다이아V에 도달했다. 아래는 공부했던 Algorithm 들이다. =============================================...