최소 신장 트리 그래프에서 모든 노드를 연결할 때 사용된 Edge들의 가중치의 합을 최소로 하는 트리이다. 특징 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다. N개의 노드가 있을 때 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개이다. 핵심 이론 모든 Edge들을 '가중치'를 기준으로 오름차순 정렬 후, 가중치가 낮은 Edge부터 연결한다. 이때 사이클이 형성되지 않을 때만 연결한다. 1. Edge 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기 그래프를 Edge 중심 형태로 Edge 리스트로 저장한다. edge class는 시작 노드, 끝 노드, 가중치로 구성된다. 사이클 여부를 확인하기 위해 유니온 파인드 배열(parent)를 인덱스의 값으로 초기화..

벨만-포드 알고리즘 벨만-포드 알고리즘 한 정점에서 다른 모든 정점간의 최단 거리를 구하는 알고리즘이다. 특징 • 음의 간선을 포함하는 그래프에서 사용한다. • 음의 사이클의 존재여부를 판단할 수 있다. 시간 복잡도 • O(VE) - V : 정점의 개수 E : 간선의 개수 주요 아이디어 노드의 수가 N개일 때 N-1번 동안 모든 Edge를 탐색하면서 최단 경로를 구한다. 그러므로 시간 복잡도가 O(VE)이다. 아무리 멀리 떨어진 노드라고 할지라도 N-1개의 간선을 지나면 어떠한 노드라도 도달할 수 있다. 그래서 벨만 포드 알고리즘은 보통 N-1번만큼 반복하여 최단경로를 알아낸다. 또한 벨만 포드 알고리즘은 주로 음의 사이클 존재 여부를 판단할 때 더 많이 쓰인다. 이때는 N번만큼 반복하며 N번일 때 최단..

본 포스팅은 Do it! 알고리즘 코딩 테스트 : 자바편을 참고하여 작성되었습니다. 유니온 파인드 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성된 알고리즘이다. 핵심 이론 union, find 연산 union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a,b가 a ∈ A, b ∈ B일 때 union(a,b)는 A ∪ B이다. find 연산 : 특정 노드 a에 관해 a가 속합 집합의 대표노드를 반환하는 연산이다. 노드 a가 a ∈ A일 때 find(a)는 A집합의 대표 노드를 반환한다. 알고리즘 구현 방법 ❶ 유니온 파인드를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것이다..

1. 서론 이분 탐색 알고리즘 관련 문제를 풀다가 잘 이해가 안되는 부분이 2가지 있었는데 바로 원하는 값과 탐색 값이 같을 때 어디서 처리를 해야할지, 두 번째로 low와 high값 중 어떤 것을 결과로 선택 해야할지이다. 여러 블로그들을 방문하여 내가 고민했던 문제를 어떻게 생각했는지 알아봤는데 설명이 잘 되어있는 블로그에서는 대부분 Lower bound와 Upeer bound 중 하나를 선택해서 구현했다. 그래서 이 두 개념에 대해 알아보고자 한다! 2. Lower bound Lower bound 알고리즘 찾고자 하는 값(크거나 같은)의 시작위치를 알아낸다. 시간 복잡도 : O(logn) 2.1 동작 방식 1. 배열의 중간 값을 가져온다. 2. 중간 값과 검색값을 비교한다. 중간 값이 검색 값보다 ..

DFS DFS는 깊이 우선 탐색으로, 한 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 검색 속도 자체는 BFS에 비해 느리지만 조금 더 간단하다. 스택 혹은 재귀함수를 이용하여 구현한다. class Graph{ private int V; private LinkedList adj[]; Graph(int v){ V = v; adj = new LinkedList[v]; for(int i=0; i