데이터 분석 기술 블로그

동적 계획법 DP"복잡한 문제를 작은 부분 문제로 나누어 해결하고, 중복 계산을 줄여 효율적으로 최적해를 찾는 알고리즘 기법"한 번 계산한 값을 저장(Memoization)하여 중복 계산 방지부분 문제를 조합하여 전체 문제의 해답을 구하는 방식피보나치수열, 최단 경로, 배낭 문제 등 다양한 문제에서 활용동적 계획법(DP) 동작 원리문제를 작은 부분 문제(Subproblem)로 나눔각 부분 문제를 해결하면서 결과를 저장(Memoization or Tabulation)저장된 결과를 이용하여 최종 문제를 해결# Pseudo Code_Top-DownFUNCTION Fibonacci(n): IF n 동적 계획법(DP)의 일반적인 시간복잡도탑다운(Top-Down) 방식: O(부분 문제 개수 × 각 문제 풀이 ..

플로이드-워셜 알고리즘"그래프에서 모든 노드 간 최단 경로를 한 번에 구하는 알고리즘"음수 간선도 처리 가능 (음수 사이클은 처리 불가!)모든 노드에서 모든 노드까지의 최단 경로를 한 번에 계산동적 계획법(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 ..