IT LAB

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출발지로부터 각 교차점까지의 최단 거리를 찾아내고 이 정보를 저장합니다.각 교차점에 기록된 거..