데이터 분석 기술 블로그

벨만-포드 알고리즘"가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘으로, 음의 가중치(음수 간선)도 처리 가능하다!"다익스트라와 달리 음수 가중치가 있는 그래프에서도 사용 가능모든 간선을 최대 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를 정렬해야 할 때병합 ..

Heapify"힙 속성을 유지하도록 트리를 정리하는 과정"최대 힙(Max Heap) → 부모 노드가 항상 자식보다 크거나 같아야 함최소 힙(Min Heap) → 부모 노드가 항상 자식보다 작거나 같아야 함Heapify 과정이 있어야 힙이 유지되고, 힙 정렬이 가능함Heapify의 역할힙이 깨졌을 때(힙 속성이 위반될 때) 이를 복구하는 과정최대 힙에서는 부모보다 큰 자식이 있으면 Swap → 힙 속성을 유지최소 힙에서는 부모보다 작은 자식이 있으면 Swap → 힙 속성을 유지완전 이진 트리(Complete Binary Tree) 형태를 유지하면서 실행Heapify의 시간복잡도 힙의 높이(트리 깊이)만큼 Swap이 필요 → O(log n)완전 이진 트리 구조이므로 높이는 log n 수준으로 유지됨따라서 H..