IT LAB

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}\right)\right)&{\mbox{ if }}x_{i}\neq y_{j}\\\end{cas..

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 item = 1; item

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>3 && memo[n] == NOT_UPDATED) memo[n] = fibDP(n-1) + fibDP(..

1. 멱집합 (Power Set) 임의의 집합 S에서 모든 부분 집합들로 구성된 집합입니다. ${\displaystyle {\mathcal {P}}(S)=\{A\colon A\subseteq S\}}$ 코드 private static void powerset(int depth, int r) { if (depth == r) { List temp = new ArrayList(); for (int i = 0; i < visited.length; i++) { if (!visited[i]) continue; temp.add(String.valueOf(src[i])); } System.out.println(Arrays.toString(temp)); return; } visited[depth] = false; pow..

1. 조합 (Combination) 임의의 집합에서 순서를 고려하지 않고 k개의 원소들을 사용해서 만들 수 있는 모든 배열들을 의미합니다. 순열의 수 ${\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}..

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

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.dest = d..

난이도 : 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 문제를 하위 문제로 나누고, 하위 문제들을 각각 해결한 후, 각 해결책들을 결합하여 원래 문제를 해결하는 알고리즘 입니다. 2. 과정 분할 원래의 문제를 비슷하지만 더 간단한 여러 하위 문제로 나눕니다. 정복 각 하위 문제를 해결합니다. 결합 하위 문제의 해결책들을 결합하여 원래 문제의 해결책을 찾습니다. 3. 예시 Merge Sort 주어진 두 리스트를 하나의 정렬된 리스트로 병합하는 알고리즘 입니다. 재귀적으로 반복하면서 전체를 정렬하는 방식입니다. 동작 방식 분할: 리스트를 반으로 나눕니다. - 크기가 1이 될 때까지 정복: 각 부분 리스트를 정렬합니다. 병합: 정렬된 부분 리스트들을 하나의 정렬된 리스트로 병합합니다. 코드 public class MergeS..