[Algorithm] 그리디
* Python을 기준으로 합니다 그리디 (Greedy) - 개념 그리디 전략 : 각 단계에서 최적의 결과만을 선택하여 문제를 해결하는 방식 이전 선택이 이후 선택에 영향을 주지 않으면서, 부분 문제에 대한 해가 전체 문제의 최적 해로 구성되는 Greedy Choice Property를 가지는 최적 부분 구조 문제에 적용 가능 그리디 적용 가능 예시 : 다익스트라, 분할 가능 배낭 문제, 거스름돈 나누기, 회의실 배정 문제, 신장 트리 (프림, 크루스칼 알고리즘) 그리디를 적용할 수 없는 경우 : 0-1 배낭 문제, 외판원 순회, 이진 트리의 최적 합 경로 - 구현 1. 분할 가능 배낭 문제 무게 $w$와 가치 $v$인 $n$개의 물건들을 배낭에 넣을 때, 물건들의 가치의 합이 최대가 되도록 배낭을 채우..
[Algorithm] 백트래킹
* Python을 기준으로 합니다 백트래킹 (Backtracking) - 개념 백트래킹 : 가능성이 없는 해는 포기하여 되돌아가고, 가능성이 높은 해결책만을 탐색하는 방법 여러 제약 조건을 만족하는 상태를 탐색해야 하는 제약 충족 문제에 적합한 방식 대표적으로 DFS는 더 이상 탐색할 경로가 없으면 (해가 없으면) 되돌아가서 다른 깊이를 탐색하는 방식으로 동작하므로 백트래킹의 예시로 볼 수 있음 - 즉, 백트래킹은 DFS를 기본 골격으로 함 백트래킹의 동작 가능한 해들의 후보 집합을 정의하고 정의된 집합을 그래프로 표현함 - 이를 상태 공간 트리 (state space tree)라고 함 유망 함수를 정의하고, 상태 공간 트리를 루트에서부터 DFS로 탐색하면서, 유망 함수에 따라 방문한 노드가 정답이 아니..
[Algorithm] 재귀, 분할 정복
* Python을 기준으로 합니다 재귀 (Recursion), 분할 정복 (Divide and Conquer) - 개념 재귀 : 자기 자신을 호출하는 것 재귀를 활용하면 함수는 시스템적으로 스택에 누적되는데, 해당 스택의 용량에는 한계가 있으므로 일정 횟수 이상을 넘어가면 overflow가 발생함 - Python은 일반적으로 1000의 재귀 상한을 가짐 (`sys.setrecursionlimit()`를 통해 재귀 상한을 늘릴 수 있음) 반복문 대신 재귀를 사용하는 이유 점화식이 존재하는 경우 (e.g. 피보나치 수열, 파도반 수열 등) 가독성 향상을 위해 (e.g. DFS) 변수 사용을 줄이기 위해 재귀의 사용 문제를 해결할 수 있는 점화식 (상태)에 대한 정확한 정의가 필요함 재귀 호출이 멈추고 값이 ..
[Algorithm] 최단 경로 - 벨만-포드 알고리즘
* Python을 기준으로 합니다 최단 경로 - 벨만-포드 (Bellman-Ford) 알고리즘 - 개념 벨만-포드 알고리즘 : 최단 경로를 찾는 알고리즘 중 하나로, 매 단계마다 모든 간선의 가중치를 확인하여 최단 거리를 갱신하는 방식으로 동작함 다익스트라와 달리 음의 가중치를 가지는 그래프에서도 동작 가능 벨만-포드 알고리즘의 동작 시작 노드를 선정하고, 최단 거리 테이블을 시작 노드는 0 나머지 노드는 최대값 INF로 초기화 아래 과정을 노드 개수 -1 만큼 반복 - 현재 노드에서 갈 수 있는 각 노드들에 대해, 전체 노드 각각을 거쳤을 때 더 짧은 최단 거리가 있는지 확인 - 더 짧은 최단 거리가 있다면 최단 거리 테이블을 갱신 위 과정을 한번 더 수행하여 갱신되는 최단 거리가 있는지 확인 - 있다..
[Algorithm] 최단 경로 - 다익스트라 알고리즘
* Python을 기준으로 합니다 최단 경로 - 다익스트라 (Dijkstra) 알고리즘 - 개념 다익스트라 알고리즘 : 그래프의 최단 경로를 찾기 위한 알고리즘 중 하나로, BFS를 기반으로 가장 비용이 적은 노드만을 선택하는 그리디 방식으로 동작함 그래프에서 간선의 가중치가 모두 양수라는 조건하에서 사용 가능함 - 다익스트라 알고리즘은 각 노드에 대한 최단 거리를 배열 저장하고 계속 갱신한다는 특징이 있음 다익스트라 알고리즘의 동작 과정 시작 노드를 설정하고, 최단 거리를 저장할 배열을 매우 큰 값(INF)으로 초기화함 방문하지 않은 노드 중에서 가장 최단 거리(최소 비용)를 가진 노드를 선택함 해당 노드를 거쳐 다른 노드로 가는 최단 거리를 계산하고, 현재까지 구한 최단 거리와 비교하여 작은 값으로 ..
[Algorithm] 위상 정렬
* Python을 기준으로 합니다 위상 정렬 (Topology Sort) - 개념 위상 정렬 : 방향 비순환 그래프 (Directed Acyclic Graph, DAG)의 모든 노드를 순서대로 나열하는 것 진입차수 (Indegree) : 그래프에서 특정 노드를 가리키는 간선의 개수 위상 정렬의 동작 진입차수가 0인 노드를 큐에 push 큐에서 노드를 pop 하면서, 인접 노드의 진입차수를 1씩 줄임 이후 진입차수가 0이 된 노드를 큐에 push 위 2~3번 과정을 큐가 빌 때까지 반복 위상 정렬의 동작 과정에서 모든 노드들을 방문하기 전에 큐가 비어지면, cycle이 존재하는 것으로 볼 수 있음 - Cycle이 존재하는 경우 어떠한 노드도 큐에 push 되지 못하기 때문 - BUT, 일반적으로 위상 정렬..