백트래킹이란?Backtracking은"모든 가능성을 시도하되, 가능성이 없는 가지는 빠르게 포기하는 전략" 입니다.DFS기반으로 경로를 탐색하다가 조건을 만족하지 않으면 되돌아가서(Backtrack) 다시 다른 경로를 시도는 하는 방식입니다.백트래킹이 필요한 문제의 특징해가 여러 개 존재 (조합, 순열, 경로 등)모든 경우를 탐색해야 하되, 중간에 가지치기(pruning) 가능대표 키워드:"모든 경우의 수""최대/최소""가능한 배치""n개의 원소를 이용해 조건 만족하는 케이스 찾기" DFS와 백트래킹의 차이항목DFS백트래킹목적그래프 전체 탐색조건 만족하는 해 찾기되돌아오기단순 순회조건 만족 못하면 되돌아감 (Pruning)사용 구조재귀/스택재귀 + 조건 분기 + 가지치 1: 순열 (Permutation)..

Union-Find란?여러 개의 원소가 있을 때,어떤 원소가 어떤 집합에 속해 있는지 빠르게 알 수 있도록 해주는 자료구조입니다.Find: 어떤 원소가 어느 집합에 속해 있는지 찾기Union: 두 집합을 하나로 합치기 어떤 상황에서 쓰일까? 그래프의 사이클 판별크루스칼 알고리즘 (최소 신장 트리)네트워크 연결 여부 판단집합의 묶음 관리기본 구현 (Python)# 1. 자기 자신을 부모로 초기화parent = [i for i in range(10)]# 2. Find 함수 (재귀)def find(x): if parent[x] != x: return find(parent[x]) return x# 3. Union 함수def union(x, y): root_x = find(x) ..

DP(Dynamic Programming)란? Dynamic Programming(동적 계획법)은하위 문제의 정답을 저장해두고 그것을 활용해전체 문제를 효율적으로 푸는 알고리즘 설계 기법입니다. DP는 언제 쓰는가?다음 두 조건을 동시에 만족할 때 DP로 풀 수 있습니다.1. Overlapping Subproblems (부분 문제 중복) → 동일한 계산을 여러 번 반복함2. Optimal Substructure (최적 부분 구조) → 전체 문제의 최적해가 부분 문제의 최적해로부터 구성됨 전통적인 재귀 vs DP 방식 비교 예: 피보나치 수열 재귀 방식 (중복 계산 발생)def fib(n): if n 시간복잡도: O(2ⁿ) - 거의 지수 시간 메모이제이션 방식 (Top-down DP)memo = [-..

BFS란?Breadth-First Search (BFS)는 그래프나 트리에서현재 노드의 이웃 노드를 먼저 방문하고,그 다음 단계로 넘어가는 너비 우선 탐색 알고리즘입니다. 즉, 깊이보다 가까운 노드부터 차례대로 탐색하는 방식입니다. BFS의 핵심 특징특징설명우선순위가까운(레벨 낮은) 노드부터 탐색자료구조Queue(큐)구현 방식반복문 기반대표 사용처최단거리 탐색, 그래프 레벨 구분, 게임 맵 탐색 등 BFS 기본 구현 (Python)from collections import dequedef bfs(graph, start): visited = [False] * len(graph) queue = deque([start]) visited[start] = True while queue: ..

DFS란?Depth-First Search (DFS)는 그래프나 트리에서 한 방향으로 끝까지 파고들었다가, 갈 곳이 없으면 되돌아오는 탐색 알고리즘입니다. 즉, 가장 깊은 노드부터 먼저 탐색DFS가 왜 중요한가?트리 구조 분석백트래킹 문저 (ex: N-Queen, 조합 탐색)경로 찾기 (모든 가능한 경로를 보고 싶을 때)싸이클 탐지DFS 두가지 구현 1) 재귀 (가장 직관적)def dfs_recursive(graph, v, visited): visited[v] = True print(v, end=' ') for neighbor in graph[v]: if not visited[neighbor]: dfs_recursive(graph, neighbor, vis..

해시 테이블 (Hash Tabel) 이란?해시 테이블은 키(Key)를 해시 함수로 계산해서고유한 인덱스(Index)에 값을 저장하는 자료구조입니다. 즉, 리스트처럼 인덱스로 접근하되,그 인덱스를 직접 지정하는 대신 해시 함수가 계산해줍니다. 파이썬에서 가장 대표적인 해시 테이블 구조는 dict, set 입니다.해시 테이블 작동 원래 (간단 예시)key를 hash() 함수로 변환이 값을 배열의 인덱스로 사용그 자리에 value 저장!my_dict = {'apple': 100, 'banana': 200}print(my_dict['apple']) # 100내부적으로 'apple' → hash('apple') → 인덱스 계산 → 해당 위치에 100 저장됨왜 해시 테이블이 빠를까?일반 배열은 인덱스로 접근: ..

자료구조는 상황에 따라 골라야한다.자료구조는 단순히 데이터를 담는 용기가 아니라,어떤 방식으로 꺼낼 것인가를 정의합니다.Stack (스택) - LIFO 구조Last In, First Out - 나중에 넣은 게 넘저 나옴 (쌓는 접시 구조) 🟢 사용 예시웹 브라우저 뒤로 가기재귀 호출 (함수 호출 스택)괄호 짝 검사stack = []stack.append(1)stack.append(2)stack.append(3)print(stack.pop())# 3🟧 시간 복잡도 : append() - O(1), pop() - O(1)Queue (큐) - FIFO 구조First In, First Out - 먼저 들어온 게 먼저 나옴 (줄 서기) 🟢 사용 예시프린트 작업 대기열CPU 태스크 스케줄링BFS (너부 우선 ..

탐색(Search)이란?탐색은 데이터 속에서 원하는 값을 찾는 작업입니다.예를 들어, [1, 3, 5, 7, 9] 안에서 5가 있는지 찾는 것입니다.탐색 알고리즘에는 대표적으로 두 가지가 있습니다선형 탐색 (Linear Search)이진 탐색 (Binary Search)선형 탐색def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i return -1방식: 앞에서부터 하나씩 비교정렬 필요 없음시간복잡도: O(n) (최악의 경우 끝까지 가야 함)이진 탐색전제 조건: 데이터가 정렬되어 있어야 함def binary_search(arr, target): left, right = 0..

정렬이 왜 중요할까?정렬(Sorting)은 거의 모든 알고르짐 문제에서 기본으로 사용됩니다.데이터를 정리하면 검색, 탐색, 그룹핑 등이 쉬워집니다.비교 정렬 알고리즘 (3형제)버블 정렬 (Bubble Sort)인접한 요소를 비교해서 더 큰 값을 오른쪽으로 '계속 밀어내는' 방식가장 큰 수가 '거품처림' 끝으로 떠오른다.def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(n - i - 1): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr ✅ 시간복잡도: O(n²)✅ 안정 정렬 (같은 값의 순서 유..

Big-O가 뭔가요?시간 복잡도(Time Complexity)는 입력 크기(n)에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 수학적으로 표현한 것이고, 그걸 나타내는 게 Big-O 표기법입니다. 예를 들어, 리스트에서 값을 찾는 코드를 보겠습니다.def find_value(arr, target): for i in arr: if i == target: return True return False 이 함수는 arr에 값이 있을 때까지 앞에서부터 하나씩 검사하죠.입력 길이 n이 길어질수록 비교 횟수도 많아져요.=> O(n), 즉 선형 시간 복잡도.자주 쓰이는 시간 복잡도 예시Big-O설명예시O(1)입력 크기에 상관없이 실행 시간 일정딕셔너리 key조회O(log n)절반씩 줄..