nolzapan

6) 그다음으로 비용이 가장 작은 간선 (1,2)를 선택한다. 현재 노드 1과 노드 2는 같은 집합에 속해 있지 않기 때문에, 노드 1과 노드 2에 대하여 union 함수를 호출한다. 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 서로소 집합 알고리즘 공통 원소가 없는 두 집합 Ex) 집합{1, 2}와 {3, 4}는 서로소 관계이다. 반면에 집합{1, 2}와 집합{2, 3}은 2라는 원소가 두 집합에 공통적으로 포함되어 있기 때문에 서로소 관계가 아니다. 서로소 집합 자료구조란 서로소 부분 집합들로 나누어진 ..

최단 경로 알고리즘 한 지점에서 다른 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘 종류 : 다익스트라 최단 경로 알고리즘, 플로이드 워셜 알고리즘 다익스트라(Dijkstra) 최단 경로 알고리즘 시간 복잡도 O(ElogV) 다익스트라(Dijkstra) 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 ㅊㄹ발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 음의 간선이 없을때 정상적으로 동작 초기 상태에서 다른 모든 노드로 가는 최단 거리를 무한으로 초기화 한다. 먼저 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하는데, 출발 노드에서 출발 노드로의 거리는 0으로 보기 때문에 처음에는 출발 노드가 선택 된다. 1번 노드를 거쳐 다른 노드로 가..

동적 프로그래밍 큰 문제를 풀기 위해 작은 문제를 풀어 큰 문제를 해결하는 알고리즘 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 동적 프로그래밍 시간 복잡도 O(N) 분할 정복 알고리즘(Divide and Conquer) 차이점 작은 문제가 중복이 일어나는지 안일어나는지 차이점 메모이제이션(Memoization) 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 탑 다운(Top-Down) 방식 큰 문제를 해결하기 위해 작은 문제를 호출 탑 다운 방식 소스코드 바텀 업(Bottom - Up) 방식 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출 바텀 업 방식 소스코드