데이터 분석 기술 블로그

플로이드-워셜 알고리즘"그래프에서 모든 노드 간 최단 경로를 한 번에 구하는 알고리즘"음수 간선도 처리 가능 (음수 사이클은 처리 불가!)모든 노드에서 모든 노드까지의 최단 경로를 한 번에 계산동적 계획법(DP) 기반으로 O(V³)의 시간복잡도를 가짐노드 개수가 작을 때 사용하기 적합플로이드-워셜 알고리즘 동작 원리모든 노드 간의 최단 거리를 저장하는 2차원 DP 테이블(행렬) 초기화모든 노드를 '경유지(K)'로 설정하면서 최단 경로 갱신테이블이 더 이상 갱신되지 않으면 종료# Pseudo CodeFUNCTION FloydWarshall(graph, V): 거리 = 그래프의 가중치 행렬 초기화 FOR k FROM 1 TO V DO: # 모든 노드를 경유지로 설정 FOR i FRO..

벨만-포드 알고리즘"가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘으로, 음의 가중치(음수 간선)도 처리 가능하다!"다익스트라와 달리 음수 가중치가 있는 그래프에서도 사용 가능모든 간선을 최대 V-1번 반복하여 최단 경로를 업데이트하는 방식음수 사이클(무한히 거리가 줄어드는 경우)도 감지 가능벨만-포드 알고리즘 동작 원리모든 노드까지의 최단 거리를 무한(∞)으로 초기화, 단 시작 노드는 0으로 설정그래프의 모든 간선을 V-1번 반복하며 갱신 (V는 노드 개수)V번째 반복에서 값이 갱신되면 음수 사이클이 존재함!# Pseudo CodeFUNCTION BellmanFord(graph, start): 거리 = {모든 노드를 ∞(무한대)로 초기화} 거리[start] = 0 # 시작 노드는 0 ..

"가중치가 있는 그래프에서 특정 시작 노드로부터 모든 노드까지의 최단 경로를 찾는 알고리즘"음의 가중치가 없는 그래프에서 최단 경로를 찾을 때 사용됨우선순위 큐(Priority Queue)를 활용하여 효율적으로 탐색네트워크 라우팅, GPS 길 찾기, 그래프 기반 문제 해결 등에 사용됨다익스트라 알고리즘 동작 원리시작 노드에서 모든 노드까지의 거리를 무한(∞)으로 초기화, 단 시작 노드는 0으로 설정현재 가장 가까운 노드를 선택하여 인접 노드의 거리 갱신모든 노드를 처리할 때까지 반복# Pseudo CodeFUNCTION Dijkstra(graph, start): 거리 = {모든 노드를 ∞(무한대)로 초기화} 거리[start] = 0 # 시작 노드는 0 우선순위 큐 PQ에 (0, star..

너비 우선 탐색 BFS"그래프 탐색 기법 중 하나로, 가까운 노드부터 차례대로 탐색하는 방식"큐(Queue)를 사용하여 구현한 단계씩 확장하며 탐색 → 최단 경로 문제에서 유용함DFS(깊이 우선 탐색)와 달리, 모든 노드를 동일한 깊이(레벨)에서 먼저 탐색BFS 동작 원리시작 노드를 큐(Queue)에 삽입하고 방문 처리큐에서 노드를 꺼내고, 인접한 노드를 모두 큐에 삽입큐가 빌 때까지 위 과정을 반복# Pseudo CodeFUNCTION DFS(node): 방문[node] = True # 현재 노드를 방문 처리 출력(node) # 노드 방문 FOR 모든 인접 노드 in node의 이웃 리스트: IF 방문[인접 노드] == False THEN DFS(인접..

깊이 우선 탐색 DFS"그래프 탐색 기법 중 하나로, 한 노드에서 출발하여 최대한 깊이 들어간 후 다시 돌아오는 방식"재귀(Recursion) 또는 스택(Stack)으로 구현 가능한 경로를 끝까지 탐색한 후, 다시 돌아가면서 다른 경로 탐색트리, 그래프, 미로 탐색 등에서 많이 사용됨DFS 동작 원리시작 노드에서 가능한 한 깊이 내려감더 이상 갈 곳이 없으면 되돌아옴 (Backtracking)모든 노드를 방문할 때까지 반복# Pseudo CodeFUNCTION DFS(node): 방문[node] = True # 현재 노드를 방문 처리 출력(node) # 노드 방문 FOR 모든 인접 노드 in node의 이웃 리스트: IF 방문[인접 노드] == False THEN ..

이진 탐색"정렬된 리스트에서 중간 값을 기준으로 범위를 좁혀가며 탐색하는 알고리즘"탐색할 때마다 범위를 절반으로 줄이므로 매우 빠름시간복잡도: O(log n) (탐색 범위가 계속 반으로 줄어듦)정렬된 데이터에서만 사용할 수 있음! (정렬이 안 되어 있으면 사용 불가)이진 탐색 동작 원리리스트가 정렬되어 있어야 한다.중간 값을 기준으로 찾고자 하는 값과 비교찾는 값이 중간 값보다 작으면 왼쪽으로, 크면 오른쪽으로 탐색 범위 축소이 과정을 반복하여 값을 찾음# Pseudo CodeFUNCTION BinarySearch(arr, target) left = 0 right = length(arr) - 1 WHILE left ≤ right DO mid = (left + right) / ..

선형 탐색"배열이나 리스트에서 처음부터 끝까지 하나씩 확인하면서 원하는 값을 찾는 탐색 알고리즘"순차적으로 모든 요소를 확인하는 방식시간복잡도: O(n) (최악의 경우, 모든 요소를 확인해야 함)구현이 쉽지만 데이터 크기가 커질수록 비효율적선형 탐색 동작 원리리스트(배열)의 첫 번째 요소부터 순차적으로 확인찾고자 하는 값이 나오면 탐색 종료끝까지 찾지 못하면 "없음" 반환# Pseudo CodeFUNCTION LinearSearch(arr, target) FOR i FROM 0 TO length(arr) - 1 DO IF arr[i] == target THEN RETURN i # 찾으면 인덱스 반환 END FOR RETURN -1 # 찾지 못하면 -1 ..

상황에 따라 가장 적절한 정렬 알고리즘을 선택해야 한다.퀵 정렬(Quick Sort) → 일반적으로 가장 빠른 정렬 (O(n log n), 평균적)병합 정렬(Merge Sort) → 항상 안정적인 성능 보장 (O(n log n), 최악 포함)힙 정렬(Heap Sort) → 추가 메모리 없이 정렬 가능 (O(n log n), 안정 정렬 X) 상황 추천 정렬 알고리즘 일반적인 경우 (랜덤 데이터)퀵 정렬 (Quick Sort)이미 정렬된 데이터병합 정렬 (Merge Sort)Stable Sort(안정 정렬)이 필요할 때병합 정렬 (Merge Sort)추가 메모리 없이 정렬해야 할 때힙 정렬 (Heap Sort)우선순위 정렬이 필요할 때힙 정렬 (Heap Sort)Linked List를 정렬해야 할 때병합 ..