IT LAB

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

1. Minimum spanning tree가중 그래프 + 무방향 그래프의 하위 트리 중,그래프의 모든 정점을 포함(spanning subgraph)하고, 사이클이 없으며, 가중치의 합이 최소인 하위트리를 말합니다. 2. Cut그래프의 정점들을 두 개의 분리된 집합으로 나누는 것을 의미합니다.각 집합은 비어있지 않습니다. Cut-Set컷을 통해 나뉜 두 집합의 정점들 사이를 잇는 모든 간선의 집합한 집합의 정점들과 다른 집합의 정점들 사이의 연결을 나타냅니다.Cut-Set에 속한 간선들을 제거하면, 그래프는 두 개의 연결되지 않은 부분 그래프로 나뉘게 됩니다. Cut Propertycut-set의 간선 중, 가중치가 가장 작은 간선들은 반드시 모든 MST에 포함됩니다.가장 가벼운 간선을 선택함으로써, 최..

난이도 : 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. Merge Sort주어진 두 리스트를 하나의 정렬된 리스트로 병합하는 알고리즘 입니다.재귀적으로 반복하면서 전체를 정렬하는 방식입니다. 동작 방식분할: 리스트를 반으로 나눕니다.정복: 각 부분 리스트를 정렬합니다.병합: 부분 리스트들을 하나의 정렬된 리스트로 병합합니다. 3. Binary Search정렬된 리..

1. 삼각함수란 각의 크기를 삼각비로 나타내는 함수입니다. 직각삼각형의 빗변은 항상 밑변, 높이와 일정한 비율을 유지합니다. 직각삼각형 $sinA = $$\dfrac{a}{h}$ $cosA = $$\dfrac{b}{h}$ $tanA = $$\dfrac{a}{b}$ 단위원 $\sin\theta$ = $\dfrac{y}{r}$ $\cos\theta$ = $\dfrac{x}{r}$ $\tan\theta$ = $\dfrac{y}{x}$ 2. 성질 값 특수각 $\sin$ $\cos$ $\tan$ 0 0 1 0 30$^\circ$ 1/2 $\sqrt{3}$/2 1/$\sqrt{3}$ 45$^\circ$ $\sqrt{2}$/2 $\sqrt{2}$/2 1 60$^\circ$ $\sqrt{3}$/2 1/2 $\sqrt{..

1. 코사인 법칙 이란? 삼각형의 세 변과 한 각의 코사인 사이에 성립하는 정리입니다. 피타고라스의 정리에 대한 일반화 입니다. 정의 삼각형의 두 변의 제곱합에서 사잇각의 코사인과 그 두 변의 곱의 2배를 빼면, 남은 변의 제곱과 같아집니다. 사용사례 삼각형의 두 변과 그 사잇각을 알 때, 남은 한 변 구하기 $ c^2 = a^2 + b^2 - 2abcosC $ 삼각형의 세 변을 알 때, 세 각 구하기 $cosC = $$\dfrac {a^2+b^2-c^2}{2ab}$ 출처 Wiki - 코사인 법칙

1. 피타고라스 정리 $ c^2 = a^2 + b^2 $ 직각 삼각형의 빗변을 변으로 하는 정사각형의 넓이는 두 직각변을 한 변으로 하는 정사각형의 넓이의 합과 같습니다. 출처 Wiki - 피타고라스 정리

1. Union-Find서로소 부분 집합들로 나눠진 원소들을 관리하는 자료구조 입니다. 서로소 집합 (disjoint)상호 배타 집합공통 원소가 없는 두 집합입니다. 두 집합 A와 B가 있을 때 교집합이 공집합이라면, A와 B는 서로소 관계에 있습니다. 2. 연산Make-Set하나의 원소만을 가지는 집합을 만듭니다. Union두 대표 원소의 집합들을 하나로 합칩니다.두 대표 원소를 입력 인자로 사용합니다. Find주어진 원소의 대표원소를 반환합니다. 3. 구현Circularly Linked ListHead대표 원소 연산find: head 반환union: 두 링크드리스트 병합 시간복잡도 O(N) 연산 속도가 느려 tree 방식이 고안되었습니다. Tree노드root: 대표 원소link: 자신의 부모 연산fi..

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

1. Subtype 부터 Exception Handler 작성하기 Supertype 부터 작성할 경우, 다형성에 의해 Supertype Exception Handler가 처리함 Subtype의 Exception Handler 처리흐름이 내려오지 않는다.