IT LAB

1. N-ary Tree 각 노드가 세개 이상의 자식노드를 가지는 트리입니다. 주로 데이터베이스나 파일시스템에서 인덱스용으로 사용합니다. 디스크 접근을 최소화하는데 유용합니다. 2. 종류 B-Tree B+Tree

1. 이진 탐색 트리 (Binary Search Tree, BST)정렬된 이진 트리입니다. 왼쪽 노드는 루트보다 작고, 오른쪽 노드는 루트보다 큽니다.검색에 특화된 이진트리 입니다. 특징정렬되어 있어 탐색, 삽입 삭제 연산이 효율적입니다. Time Complexity$O(logN)$ 2. 종류AVL Tree (균형 이진 트리)Red-Black Tree (균형 이진 트리)

1. Travelling salesman problem 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 떄, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는데 드는 최소 거리 구하기 그래프 이론 각 변에 가중치가 주어진 완전 그래프에서 가장 작은 가중치를 가진 해밀턴 순환 구하기 2. brute-force (permutation. NP) time complexity $O(n!)$ 3. dynamic programming (Held-Karp algorithm) 동작 원리 초기화 모든 도시를 1부터 n까지 번호 매기기 임의의 도시를 시작점으로 선택 상태 정의 $g(S, e)$ : 출발지에서 S에 포함된 모든 도시를 거쳐 e에 도달하는 최단 경로의 길이 최솟값 계산 (재..

1. Longest Common Subsequence (LCS. 최장 공통 수열)두 수열의 공통 부분 수열 중, 가장 긴 수열을 찾는 문제입니다. 부분 수열주어진 수열에서 몇 개의 원소를 선택해 만든 수열원소의 순서는 원래 수열에서의 순서를 유지해야 함 점화식${\displaystyle LCS\left(X_{i},Y_{j}\right)={\begin{cases}\emptyset &{\mbox{ if }}\ i=0{\mbox{ or }}j=0\\{\textrm {}}LCS\left(X_{i-1},Y_{j-1}\right)+1&{\mbox{ if }}x_{i}=y_{j}\\{\mbox{longest}}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\r..

1.  Knapsack Problem (배낭 문제)베낭에 담을 수 있는 최대 무게가 정해져 있고, 무게와 가치가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐 채우기 0-1 Knapsack Problem각 짐을 한 번만 선택할 수 있음각 짐을 넣거나 넣지 않는 선택을 할 수 있음 점화식$m[0, w] = 0$$m[i, w] = m[i-1, w] \quad \text{if } w_{i} > w$$m[i, w] = \max(m[i-1, w], m[i-1, w-w_{i}] + v_{i}) \quad \text{if } w_{i} \leqslant w$ 2. 풀이코드costs = new int[N+1];volumes = new int[N+1];dp = new int[N+1][K+1];for (int..

1. Fibonacci (피보나치 수열)직전 두 항의 합인 수열입니다. (첫째항과 둘째항은 1) 점화식$fib(n) = fib(n-1) + fib(n-2)$ 예시: $fib(5)$$fib(4)+fib(3)$$(fib(3)+fib(2)) + (fib(2)+fib(1))$$((fib(2)+fib(1)) + (fib(1)+fib(0))) + ((fib(1)+fib(0)) + fib(1)$$(((fib(1)+fib(0)) + fib(1)) + (fib(1)+fib(0))) + ((fib(1)+fib(0)) + fib(1))$ 2. 풀이 코드더보기public int fibDP(int n) { if (n == 0) return 0; if (n == 1) return 1; if (memo[n]..

1. 멱집합 (Power Set)임의의 집합 S에서 모든 부분 집합들로 구성된 집합입니다.${\displaystyle {\mathcal {P}}(S)=\{A\colon A\subseteq S\}}$ 코드더보기private void powerset(int depth) { if (depth == size) { List temp = new ArrayList(); for (int i = 0; i  예${\displaystyle \{a,b\}}$의 멱집합${\displaystyle {\mathcal {P}}(\{a,b\})=\{\varnothing ,\{a\},\{b\},\{a,b\}\}}$ ${\displaystyle \{a,b,c\}}$의 멱집합${\displaystyle {\m..

1. K-Combinationk개의 원소들을 사용해서, 순서를 고려하지 않고 배열한 모든 경우의 수 순열의 수${\displaystyle C(n,r)={\frac {n(n-1)\cdots (n-r+1)}{r!}}={\frac {n!}{r!(n-r)!}}}$ 성질대칭성n개의 원소에서 r개를 선택하는 것과 (n-r)개를 선택하는 방법의 수가 동일합니다.${\displaystyle {\binom {n}{r}}={\binom {n}{n-r}}}$ 재귀적 (파스칼의 삼각형)두 집합의 합원래 집합에서 하나의 원소를 제외하고, r개를 선택하는 방법의 수원래 집합에서 하나의 원소를 제외하고, r-1개를 선택하는 방법의 수${\displaystyle {\binom {n}{r}}={\binom {n-1}{r}}+{\bi..

1. Permutation집합의 원소들을 모두 사용하여 순서를 고려하여 배열한 모든 경우의 수 전단사 함수정의역과 공역이 같습니다. 순열의 수${\displaystyle n!=n(n-1)(n-2)\cdots \cdot 2\cdot 1}$ 예좌석 배치(1,2,3,4)(2,1,3,4)(3,1,2,4)(4,1,2,3)(1,2,4,3)(2,1,4,3)(3,1,4,2)(4,1,3,2)(1,3,2,4)(2,3,1,4)(3,2,1,4)(4,2,1,3)(1,3,4,2)(2,3,4,1)(3,2,4,1)(4,2,3,1)(1,4,2,3)(2,4,1,3)(3,4,1,2)(4,3,1,2)(1,4,3,2)(2,4,3,1)(3,4,2,1)(4,3,2,1)  2. K-Permutation서로 다른 n개의 원소 가운데 유니크한 k개를..

1. Prim AlgorithmMST를 찾는 알고리즘 입니다.인접 행렬과 우선순위 큐를 사용합니다. Greedy최소 비용의 인접 간선을 선택하여 MST를 만듭니다. 2. 동작 순서 0. 인접행렬 생성1. 시작 꼭짓점 선택2. MST에 간선 추가대상: 트리 정점에 부속된 간선들순서: 가중치가 가장 작은 간선 (우선순위 큐 사용) 모든 꼭짓점이 MST에 포함될 때까지 반복합니다.(모든 간선을 조사한 후 MST에 모든 꼭짓점이 없다면, 해당 그래프에는 MST가 존재하지 않습니다.) 3.  구현static class Edge implements Comparable { final int dest, weight; public Edge(int dest, int weight) { this.des..