동작 방식요소 삽입: 우선순위 큐에 값을 삽입할 때 해당 값의 우선순위가 큐의 규칙에 따라 저장됩니다.요소 삭제: 우선순위 큐에서 값을 삭제할 때는 큐에 저장된 값 중 가장 높은 우선순위를 가진 값이 먼저 삭제됩니다.특징우선순위 기준: 우선순위 큐에서는 각 요소가 우선순위(priority)를 가지고 있으며, 이 우선순위에 따라 처리 순서가 정해집니다.최대 우선순위 큐: 가장 큰 값(우선순위가 높은 값)이 먼저 처리됩니다.최소 우선순위 큐: 가장 작은 값(우선순위가 낮은 값)이 먼저 처리됩니다.내부 구현:우선순위 큐는 보통 힙(Heap) 자료 구조를 사용하여 구현됩니다. 힙은 완전 이진 트리로, 각 노드의 값이 그 자식 노드보다 크거나 작다는 성질을 가집니다.최소 힙(min-heap): 부모 노드의 값이 ..
힙의 주요 특징완전 이진 트리(Complete Binary Tree):힙은 항상 완전 이진 트리의 구조를 가집니다.완전 이진 트리란 트리의 모든 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽에서 오른쪽으로 순서대로 채워져 있어야 합니다.부모-자식 간의 순서 관계:최대 힙 (Max-Heap): 부모 노드의 값이 항상 자식 노드의 값보다 큽니다.즉, 루트 노드가 트리에서 가장 큰 값을 가집니다.최소 힙 (Min-Heap): 부모 노드의 값이 항상 자식 노드의 값보다 작습니다.즉, 루트 노드가 트리에서 가장 작은 값을 가집니다.우선순위 큐:힙은 우선순위 큐를 구현하는 데 적합합니다.우선순위 큐에서 가장 우선순위가 높은 요소를 빠르게 찾아내고 제거해야 할 때, 힙은 O(log n) 시간 복잡도로 이를 처리할 수 있..
Kadane's Algorithm은 배열에서 연속된 요소들의 부분 배열 중 가장 큰 합을 찾는 효율적인 알고리즘입니다. 이 알고리즘은 O(n) 시간 복잡도로 동작하므로, 배열을 한 번만 순회하여 문제를 해결할 수 있습니다. 문제는 주로 "최대 부분 배열 합" (Maximum Subarray Sum) 문제라고 불립니다.알고리즘 설명:배열의 각 요소를 차례대로 살펴보며, 현재 위치까지의 최대 부분 배열 합을 계산합니다.부분 배열의 합이 음수로 떨어지면 그 이전의 부분 배열은 버리고, 새로운 부분 배열을 시작합니다.결국 가장 큰 부분 배열의 합을 찾아냅니다.원리:현재까지의 최대 부분 합(max_ending_here)을 유지합니다.최대 전체 합(max_so_far)을 유지합니다.각 단계에서 현재까지의 최대 부분..
Divide and Conquer와 Dynamic Programming은 둘 다 문제를 작은 하위 문제로 나누어 해결하는 방식이지만, 근본적으로 해결 방식과 적용 상황에서 차이가 있습니다.1. Divide and Conquer (분할 정복)핵심 아이디어:문제를 더 작은 하위 문제로 나누어 각각을 재귀적으로 해결한 다음, 결과를 결합하여 원래 문제를 해결하는 방식입니다.각 하위 문제는 독립적으로 해결됩니다.특징:문제를 재귀적으로 쪼개고, 각 하위 문제를 해결한 후 결합하여 최종 결과를 얻습니다.하위 문제들이 서로 중복되지 않음. 즉, 같은 하위 문제를 여러 번 계산하지 않음.대표적인 예: Merge Sort (O(n log n)), Quick Sort (O(n log n)), Binary Search (O..
Trie의 주요 특징문자 기반 트리: 각 노드는 문자를 저장하며, 루트 노드에서부터 각 문자 노드를 따라가면서 문자열을 구성합니다.공유된 경로: 문자열의 공통된 접두사를 공유하므로 메모리를 절약할 수 있습니다.효율적인 검색: 단어 검색, 삽입, 삭제가 매우 빠릅니다. 검색 시간은 문자열의 길이에 비례합니다.Trie의 구조노드(Node): 각 노드는 하나의 문자 또는 값(보통은 문자)을 저장하며, 자식 노드들을 가리킵니다.루트 노드: 트리의 최상위 노드로, 빈 값(또는 특별한 값)을 가집니다.자식 노드: 각 노드는 여러 자식 노드를 가질 수 있으며, 자식 노드는 다른 문자로 이어지는 경로를 나타냅니다.종료 표시(End of Word): 노드에는 단어가 끝나는지 여부를 표시하는 플래그가 있을 수 있습니다. ..
처리해야할 여러가지 일들이 있고, 이들 사이의 선후 관계가 있는 그래프.DAG (Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 조건. 진입 차수(indegree)를 이용한 정렬탐색큐, 결과큐 사용 시간복잡도 O(|V|+|E|)진입 차수가 0이 아닌 정점이 남아 있으면 사이클이 있는 그래프위상 정렬의 핵심 아이디어위상 정렬은 노드들 간의 의존 관계를 고려하여 모든 노드를 순서대로 나열하는 과정입니다. 예를 들어, 코스 수강 문제에서 A → B가 있으면, A를 먼저 수강해야 하고 그 후에 B를 수강할 수 있습니다. 따라서 위상 정렬은 이와 같은 의존 관계를 가진 작업들을 순서대로 나열하는 방식입니다.위상 정렬의 활용작업 스케줄링: 여러 작업 간의 의존성을 만족시키면서 작..
집합의 공집합을 포함한 모든 부분 집합 크기는 2 ^ n
순열 Permutation 서로 다른 n개의 원소에서 r개를 중복없이 뽑아 순서를 정해 나열하는 경우 nPr = n! / (n-r)! nP0 = 1 , nPn = n! 중복 순열 n개의 원소에서 r개를 순서에 상관있게 뽑는데, 중복을 허락할 때의 경우 n^r 조합 Combination 서로 다른 n개의 원소에서 순서에 상관없이 r개를 뽑는 경우 nCr = nPr / r! nC0 = 1, nCn = 1 nCr = n-1Cr-1 + n-1Cr nCr = nCn-r 중복 조합 조합과 마찬가지로 n개의 원소에서 r개를 순서에 상관없이 뽑는데, 중복을 허락할 때의 경우 nHr = r+(n-1)Cr = n+r-1 C n-1