알고리즘 이론

완전 탐색 알고리즘1\. 순열2\. 조합3\. 부분집합

순열조합부분집합서로 다른 것n개의 원소 중 r개를 순서 없이 골라 나열 한 것조합 공식 : $nC_r = \\frac {n!} {(n - r)!r!}$ $(n\\leq r)$중복 조합 공식 : $\_nH_r = {n+r-1} C \_{r}$ 조합의 시간복잡도는 n값에

순열조합부분집합집합에 포함된 원소들을 선택하는 것부분 집합 공식 : 원소가 n개 일 때, 2 x 2 x 2 x ... = 2^n (각 원소에 대해 부분집합에 포함시키거나 포함시키지 않는다라는 2가지 경우를 적용) 집합의 원소가 n개 일때,공집합을 포함한 부분집합

비트의 가장 왼쪽 비트는 부호비트이다.

현 순열에서 사전 순으로 다음 순열을 생성$\_nP_n$만 가능arri-1<arri : $O(N)$arri-1<arrj : $O(N)$swap(i-1,j) : $O(1)$arrk부터 reverse : $O(N)$총 시간 복잡도 : $O(N) + O(N) +

그래프는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조이다.정점 (Vertex) : 그래프 구성요소로 하나의 연결점간선 (Edge) : 두 정점을 연결하는 선차수 (Degree) : 정점에 연결된 간선의 수간선의 수V : 정점의 개수무향 그래프 간선

그래프에서 최소 비용 문제를 해결하기 위한 트리 1\. 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리 2\. 두 정점 사이의 최소 비용 경로 찾기❓ 여기서 신장 트리란? : V개의 정점으로 이루어진 무향그래프에서 V개의 정점과 V-1개의 간선으로

0-1 Knapsack 쪼갤 수 없는 물건을 배낭에 담는 문제Dynamic programming 문제Fractional Knapsack쪼갤 수 있는 물건을 배낭에 담는 문제Greedy 문제쪼갤 수 없는 가중치를 담을 때 사용하는 알고리즘이다.탐욕적 방법으로 최적해를 찾

동일한 물건을 여러 번 선택할 수 있을 때 0/1 Knapsack과 점화식이 달라진다.

BFS에 PriorityQueue를 사용하면 2차원 다익스트라다.

항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하는 알고리즘$O(n+k)$ : n - 리스트 길이 / k - 정수의 최대값제한 사항각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문에 정수나

카운팅 정렬 (Counting Sort) 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하는 알고리즘 $O(n+k)$ : n - 리스트 길이 / k - 정수의 최대값 제한 사항 각 항목의 발생 횟수를 기록하기 위해, 정수 항목으로 인덱