IT LAB

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..

1. Kruskal AlgorithmMST 알고리즘 입니다.Union-Find, 정렬된 Edge set을 사용합니다. Greedy인접한 최소 비용의 간선을 선택하여 MST를 만듭니다. 2. 동작 순서1. 나무 초기화그래프의 각 꼭짓점을 각각 하나의 나무로 초기화합니다., 2. 정렬된 간선 집합 S 생성3. 숲 F 갱신S에서 가장 작은 가중치의 변을 뽑습니다.변의 꼭짓점이 이미 하나의 나무로 구성되어 있으면 버립니다. (사이클 방지)그 변에 연결된 두 나무를 하나의 나무로 만듭니다.전체적으로 하나의 숲을 만듭니다. S가 비어있지 않을 때까지 반복하여 모든 정점을 포함하는 최소 신장 트리를 만듭니다. 3. 예시  4. 구현static class Edge implements Comparable { fin..

난이도 : Gold 5 문제 링크 1. 문제 설명 요구사항 모든 사람들의 친구관계가 주어질 때, 아래와 같은 친구관계가 존재하는지 판별하라. 친구관계 A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 2. 내 풀이 5명의 사람이 연쇄적으로 친구인 관계 존재 여부 자료구조 (친구관계) 친구관계 : 양방향, 다대다, (친구 수)가변적 무방향 그래프 Vertex: 사람, Edge: 친구 인접 리스트 (메모리 관점에서) 자신의 친구들을 효율적으로 기억할 수 있음 코드 // 선언 private static List graph = new ArrayList(); // 초기화 for (int i = 0; i < nodeCnt; i++) { graph.add(new ArrayList()); ..

1. Divide and Conquer문제를 하위 문제로 나누고, 하위 문제들을 각각 해결한 후, 각 해결책들을 결합하여 문제를 해결하는 알고리즘 입니다. 동작 원리분할원래의 문제를 여러 하위 문제로 나눕니다.하위 문제는 원래 문제와 비슷합니다. 정복각 하위 문제를 해결합니다.재귀적으로 반복합니다. 결합하위 문제의 해결책들을 결합하여 원래 문제의 해결책을 찾습니다. 장점성능하위 문제는 병렬 처리 가능 (서로 독립적입니다) 3. 문제Merge Sort주어진 두 리스트를 하나의 정렬된 리스트로 병합하는 알고리즘 입니다.재귀적으로 반복하면서 전체를 정렬하는 방식입니다. 동작 방식분할: 리스트를 반으로 나눕니다.정복: 각 부분 리스트를 정렬합니다.병합: 부분 리스트들을 하나의 정렬된 리스트로 병합합니다. Bin..

1. Dijkstra Algorithm 이란?시작 정점으로부터 모든 정점간의 최단 경로를 찾는 알고리즘 입니다. 가중치가 양수인 그래프에서 사용됩니다. Greedy매 단계에서 현재까지 가장 짧은 경로를 선택합니다.그 경로를 바탕으로 다음 경로를 업데이트 하는 방식입니다.우선순위 큐와 간선 리스트를 사용합니다. 2. 동작 원리교차점마다 출발지로부터의 거리를 기억하여 도착지와의 최단 거리를 찾는 방식입니다. Initialization모든 교차점의 거리를 무한대로 설정합니다. (해당 교차로로 가는 경로가 없음을 의미)출발지의 거리를 0으로 설정합니다. (자기 자신에서 출발하므로) Search & Memorization출발지로부터 각 교차점까지의 최단 거리를 찾아내고 이 정보를 저장합니다.각 교차점에 기록된 거..