이항 계수이항 계수 ?이항 계수는 조합을 계산할 때 사용되는 수학적 개념으로, n개의 원소 중 k개의 원소를 고르는 경우의 수를 의미한다.$$C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!} $$💡 이항 계수 계산 방법팩토리얼 사용 :public class BinomialCoefficient { public static long factorial(int n) { if (n == 0 || n == 1) return 1; long result = 1; for (int i = 2; i n) return 0; return factorial(n) / (factorial(k) * factorial(n - k)); } ..
세그먼트 트리세그먼트 트리 ?세그먼트 트리는 구간 쿼리 문제를 효율적으로 해결하기 위한 자료구조이다 ! → 특정 범위의 데이터(ex: 구간합, 구간 최소값, 최대값)를 빠르게 계산하고, 데이터가 업데이트될 경우 효율적으로 반영할 수 있다.세그먼트 트리는 완전 이진 트리 형태를 가진다.리프 노드 → 입력 배열의 각 요소를 표현한다.내부 노드 → 특정 범위의 구간 정보를 나타낸다.트리의 루트 노드는 전체 배열의 정보를 나타낸다.💡 세그먼트 트리 - 구현세그먼트 트리에는 3가지 핵심 연산이 있다.트리 구성 (Build)입력 배열을 기반으로 세그먼트 트리를 구성한다.각 노드는 특정 범위의 값을 저장한다.구간 쿼리 (Query)특정 구간 [L, R]의 값을 계산한다.현재 노드의 범위와 [L, R]의 관계에 따라..
이진 트리 순회이진 트리 순회 ?이진 트리 순회는 트리 구조에서 각 노드를 방문하는 방법을 의미한다.주요 순회 방식전위 순회(Preorder Traversal) : 루트 → 왼쪽 자식 → 오른쪽 자식현재 노드를 먼저 방문한 뒤, 왼쪽 서브트리를 순회하고 오른쪽 서브트리를 순회한다.트리 복사, 표현식 트리를 평가하는 경우에 사용된다.중위 순회(Inorder Traversal) : 왼쪽 자식 → 루트 → 오른쪽 자식왼쪽 서브트리를 먼저 순회한 뒤 현재 노드를 방문하고, 오른쪽 서브트리를 순회한다.정렬된 순서로 출력하는 경우(특히 이진 탐색 트리에서 유용)에 사용된다.후위 순회(Postorder Traversal) : 루트 → 왼쪽 자식 → 오른쪽 자식현재 노드를 먼저 방문한 뒤, 왼쪽 서브트리를 순회하고 오..
플로이드 워셜플로이드-워셜(Floyd-Warshall) ?각각의 모든 노드에 대하여 다른 모든 노드로의 최단 거리를 구할 수 있는 알고리즘 ! ↔ 특정 시작점에서 다른 모든 노드로의 최단 거리를 구하는 다익스트라, 벨만-포드 알고리즘음수 가중치를 갖는 간선이 있어도 수행 가능하나, 음수 사이클이 있는 경우엔 사용할 수 없다.💡 플로이드 워셜 핵심 개념 - 동적 계획법(DP)DP는 하나의 큰 문제를 여러 개의 작은 문제로 나눈 후에, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하기 위한 알고리즘이다 ! → **기억하며 풀기**(Memoization)메모이제이션 : 변수 값에 따른 결과를 저장할 배열 등을 미리 만들고, 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 ..
벨만-포드벨만-포드(Bellman-Ford) ?벨만포드 알고리즘은 그래프에서의 단일 출발지 최단 경로 문제(One-To-All)를 해결하기 위한 알고리즘으로, 다익스트라 알고리즘과 달리 **음수 가중치 간선**이 포함된 그래프에서도 사용할 수 있다. 💡경로 탐색 방식에는 3가지가 있다 ?One-To-One: 한 지점에서 다른 특정 지점까지의 최단 경로 구하기One-To-All: 한 지점에서 다른 모든 지점까지의 최단 경로 구하기All-To-All: 모든 지점에서 다른 모든 지점까지의 최단 경로 구하기 다만, 음수 사이클이 있는 경우에는 최단 경로를 계산할 수 없으며, 이를 탐지하는 기능도 포함되어 있다.💡 핵심 개념 - 단계별 Relaxation각 간선을 반복적으로 확인하며, 시작 정점에서 다른 정점..
최소 스패닝 트리최소 스패닝 트리(MST) ?최소 스패닝 트리는(MST)는 가중치 그래프에서 모든 정점들을 연결하는 최소 비용의 연결 부분 그래프이다.MST 조건모든 정점이 연결되어 있어야 한다 !사이클이 없어야 한다 !가중치의 합이 최소여야 한다 !💡 핵심 개념 - 스패닝 트리스패닝 트리는 주어진 그래프의 모든 정점을 포함하는 연결 그래프이며, 간선의 수는 V(정점의 수)-1이다. → 여러 스패닝 트리 중 가중치의 합이 최소인 트리가 MST이다.💡 핵심 개념 - MST를 구하기 위한 알고리즘크루스칼 알고리즘: 간선을 정렬한 뒤, 최소 가중치 간선을 하나씩 선택하면서 사이클이 생기지 않도록 트리를 구성한다.프림(Prim) 알고리즘: 하나의 정점에서 시작하여 인접한 간선 중 최소 가중치를 선택하며 트리..
