최소 신장 트리 알고리즘 - 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 - 대표적인 최소 신장 트리 알고리즘 : 크루스칼 알고리즘 신장 트리 - 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 - 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 함 최소 신장 트리 (MST) - 신장 트리의 조건을 만족하면서 최소 비용으로 만들 수 있는 신장 트리 - 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리 - 특징 - 사이클 포함하지 않음 - N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개 크루스칼 알고리즘 - 그리디 알고리즘의 일종 👉 유..
플루이드 - 음수 사이클이 없는 그래프 내의 각 모든 정점에서 각 모든 정점에 까지의 최단거리를 모두 구할 수 있는 알고리즘 - 음의 가중치를 갖는 간선이 존재해도 상관없음 - 다익스트라는 음의 가중치를 가질 수 없음 - 다이나믹 프로그래밍 기법을 사용한 알고리즘 - 인접행렬을 이용하여 각 노드가 최소 비용 계산 - 시간 복잡도가 복잡해 입력의 크기가 크면 곤란하다~ (시간복잡도 O(V^3)) - 플로이드 워셜을 사용하는 문제는 일반적으로 노드의 개수의 범위가 다른 그래프에 적게 나타남 점화식 D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 순서 1. 배열을 선언하고 초기화하기 D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 배열 S와 E의 값이 같은 ..
벨만 포드 그래프에서 최단 거리를 구하는 알고리즘 기능 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 특징 음수 가중치 에지가 있어도 수행할 수 있음 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음 시간복잡도 O(VE) (노드 수 : V, 에지 수 : E) 핵심 이론 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현 최단 경로 배열(D)은 출발 노드는 0, 나머지 노드는 무한대로 초기화 모든 에지를 확인해 정답 배열 업데이트 최단 거리 배열에서 업데이트 반복 횟수는 노드 개수 - 1 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수는 N - 1 특정 에지 E = (출발 노드 s, 종료 노..
다익스트라 (Dijkstra) - 그래프에서 최단 거리를 구하는 알고리즘 - 출발 노드와 모든 노드 간의 최단 거리 탐색 - 에지는 모두 양수 => 음의 가중치가 없는 그래프의 한 노드에서 모든 노드까지의 최단 거리를 구하는 알고리즘 - 시간 복잡도 : O(ElongV) (E : 에지 수, V : 노드 수) - 우선순위 큐를 사용 - 기본적으로 Greedy와 DP 알고리즘을 사용한 기법 1. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 (그리디) 2. 해당 노드로부터 갈 수 있는 노드들의 비용 갱신 (DP) - 위의 두 단계를 반복하여 각 모든 노드 까지의 최단 거리를 구함 🌝 핵심 이론 1. 인접 리스트로 그래프 구현하기 - 인접 행렬로 구현도 가능하지만 시간 복잡도를 고려한다면 인접 리스트를 ..
위상 정렬 (topology sort) - 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 - 기능 : 노드 간의 순서를 결정 - 특징 : 사이클이 없어야 함 -> 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없어 위상 정렬 적용 불가 - 시간 복잡도 : (노드 수 V, 에지 수E) O(V+E) - 항상 유일한 값으로 정렬되지 않음 - 원리 1. 진입 차수 : 자기 자신을 가리키는 에지의 수 그래프는 사이클이 없는 상태로 ArrayList로 그래프를 구성하였음 진입 차수 배열 D를 세팅함 -> 각자의 진입 차수로 업데이트 2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 빼줌 예..
유니온-파인드 (Union-Find) - 대표적인 그래프 알고리즘 - 두 노드가 같은 집합에 속하는지 판별하는 알고리즘 - 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지 확인하는 find연산으로 구성되어 있는 알고리즘 🌝 작동원리 1. 대상 노드 배열에 index값과 value값이 동일한지 화긴 2. 동일하지 않으면 value값이 가르키는 index위치로 이동 3. 이동 위치의 index값과 value값이 같을 때까지 1번과 2번 반복 => 재귀 함수로 구현 4. 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드값을 루트 노드값으로 변경 // 참고 https://velog.io/@suk13574/%EC%95%8C%E..
그리디 (Greedy Algorithm) - 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지만을 쫒아 최종적인 해달에 도달하는 알고리즘 - 극단적으로 문제에 접근한다는 점에서 정렬(Sort) 기반이 함께 사용되는 경우가 많음 🌝 장단점 - 근사치 추적에 홣용 -> 반드시 최적의 해를 구할 수 있는 것은 아님 🌝 정당성 증명 1. 탐욕적 선택 속성 (greedy choice property) - 이전의 선택이 이후에 영향을 주지 않음 2. 최적 부분 구조 (optimal substructure) - 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 함 🌝 문제 해결 방법 1. 선택 절차 (Selection Procedure) - 현재 상태에서 가장 최선이라고 생각되는 해..
버블 정렬 (Bubble Sort) 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 두 인접한 데이터의 크기를 비교해 정렬하는 방법 비교와 교환이 모두 일어날 수 있어 코드는 단순하지만 성능은 좋지 않음 시간 복잡도 O(n^2) 과정 비교 연산이 필요한 루프 범위 설정 인접한 데이터 값을 비교 swap 조건에 부합하면 swap 연산을 수행 루프 범위가 끝날 때까지 2-3번 반복 정렬 영역을 선택 -> 다음 루프를 실행할 때는 이 영역 제외 비교 대상이 없을 때까지 1-5번을 반복 특정한 루프의 전체 영역에서 swap이 한번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬되었다는 뜻으로 프로세스를 종료 // 참조 https://st-lab.tistory.com/195 p..
이진 탐색 (이분 탐색, Binary Search) 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음 기능 : 타깃 데이터 검색 특징 : 중앙값 비교를 통한 대상 축소 방식 시간 복잡도 : O(longN) 오름차순으로 정렬된 데이터 기준 현재 데이터셋의 중앙값을 선택 중앙값 > 타깃 데이터 일 때 중앙값 기준으로 왼쪽 데이터셋을 선택 중앙값 < 타깃 데이터 일 때 중앙값 기준으로 오른쪽 데이터셋을 선택 위의 과정을 반복 내림차순일 경우 조건을 반대로 하여 과정을 반복 데이터의 삽입, 삭제가 많을 경우에는 적합하지 않아, 주로 고정된 데이터에 대한 탐색에 적합 구현방법 1. 반복문을 이용한 구현 stat..
