데이터 분석 기술 블로그

비트마스킹(Bitmasking)"비트를 활용하여 여러 개의 상태를 효율적으로 저장하고 조작하는 기법"정수의 이진수 표현을 이용하여 데이터를 압축적으로 저장특정 비트를 켜거나(1), 끄거나(0), 토글(반전)하는 연산을 수행집합 연산, 최적화 문제, DP, 그래프 탐색에서 자주 사용됨비트마스킹 기본 개념비트(0과 1)를 사용하여 여러 개의 상태를 한 개의 정수로 표현각 비트가 특정 상태(ON/OFF)를 나타냄비트 연산자(&, |, ^, >)를 활용하여 빠르게 연산 가능# 집합 구현S = 0 # 빈 집합# 원소 추가S |= (1 비트 연산 기초연산연산자설명AND&두 비트가 모두 1이면 1, 아니면 0OR``XOR^다르면 1, 같으면 0NOT~0은 1로, 1은 0으로 변환왼쪽 시프트비트를 왼쪽으로 이동 (2..

분할 정복"큰 문제를 작은 문제로 나누고, 각각을 해결한 후 결합하여 최종 해답을 도출하는 알고리즘 기법"재귀(Recursion)를 사용하여 문제를 반복적으로 쪼개어 해결각 부분 문제가 동일한 방식으로 해결 가능해야 함 (재귀적 구조)대표적인 예제: 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary Search), 행렬 곱셈(Strassen Algorithm)분할 정복(Divide and Conquer) 동작 원리분할(Divide): 문제를 더 작은 부분 문제(subproblem)로 나눈다.정복(Conquer): 부분 문제를 해결한다. (대부분 재귀적으로 해결)결합(Combine): 부분 문제의 답을 결합하여 전체 문제의 답을 만든다.# Pseudo CodeFUNC..

탐욕 알고리즘"현재 단계에서 가장 최적의 선택을 반복하여 최종 최적해를 구하는 알고리즘"각 단계에서 최선의 선택을 하는 것이 전체적으로도 최선이라는 보장이 필요함DP와 달리, 이전 선택을 고려하지 않고 즉각적인 최적 선택을 수행대표적인 예제: 거스름돈 문제, 최소 신장 트리(Prim, Kruskal), 최단 경로(Dijkstra)탐욕 알고리즘 동작 원리현재 단계에서 가장 좋은 선택(탐욕적 선택, Greedy Choice)을 함선택한 결과를 확정하고, 다음 단계에서도 동일한 방식으로 진행최종 해답이 전체적으로 최적해인지 확인# Pseudo Code_거스름돈 문제FUNCTION GreedyChange(money, coins): coins.sort(reverse=True) # 동전 내림차순 정렬 ..

동적 계획법 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(인접..