https://thin-azimuth-2a9.notion.site/cf-196f4ee21c0080ad9edfe31c198f5c63?pvs=4 원형 수열에서 연속 부분 수열 합의 개수 구하기(cf. 누적합) | Notion누적 합(Prefix Sum)thin-azimuth-2a9.notion.site
이항 계수이항 계수 ?이항 계수는 조합을 계산할 때 사용되는 수학적 개념으로, 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각 간선을 반복적으로 확인하며, 시작 정점에서 다른 정점..