[Algorithm] 최장 증가 부분 순열, 최장 공통 부분 수열
* Python을 기준으로 합니다 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) & 최장 공통 부분 수열 (Longest Common Subsequence, LCS) - 개념 부분 수열 : 주어진 수열 중 일부를 뽑아 새로운 수열을 만들 때, 기존의 상대적인 순서를 유지하는 수열 최장 증가 부분 수열 (LIS) : 부분 수열의 원소가 오름차순을 유지하면서 가장 길이가 긴 수열 일반적으로 다이나믹 프로그래밍으로 해결가능함 LIS 길이 계산에 다이나믹 프로그래밍 적용하기 다이나믹 프로그래밍을 활용하기 위해서는 전체 문제가 중복되는 최적 부분 구조로써 분해 가능해야함 - 최적 부분 구조 : 전체 수열에 대한 LIS 길이는 각 원소로 끝나는 LIS 길이 중 최대값을 구..
[Algorithm] 신장 트리 - 프림 / 크루스칼 알고리즘
* Python을 기준으로 합니다 신장 트리 (Spanning Tree) - 프림 / 크루스칼 알고리즘 - 개념 신장 트리 : 모든 노드와 연결되어 있으면서 사이클이 존재하지 않는 부분 그래프 이때 간선 개수는 노드의 개수 보다 하나 적음 최소 신장 트리 (Minimum Spanning Tree, MST) : 가중치 합이 최소인 신장 트리 - 이때 구해지는 최소 신장 트리는 여러 개일 수 있음 최소 신장 트리 구하기 공통적으로 그리디 전략을 이용하고, $E$개의 노드 $V$개의 간선에 대해 $O(E \log V)$의 time complexity를 가짐 프림 알고리즘 (Prim Algorithm) 임의의 노드를 선택하여 최소 신장 트리에 추가 최소 신장 트리와 연결되어 있는 노드 중에서 가장 가중치가 작은..
[Algorithm] 다이나믹 프로그래밍
* Python을 기준으로 합니다 다이나믹 프로그래밍 (Dynamic Programming) - 개념 다이나믹 프로그래밍 (동적 계획법) : 전체 문제를 각각의 부분 문제로 나눈 다음 하나의 결과로 합쳐서 해결하는 방법 즉, 전체 문제를 부분 문제로 나누어 해결할 수 있어야 하고 동시에 중복되는 부분 문제가 존재하는 경우 사용 다이나믹 프로그래밍의 구현 메모이제이션 (Memoization) : 하향식 (Top-down) 방식 - 주어진 문제를 작은 부분 문제로 나누어 가면서 전체 문제를 해결하는 방식 - 재귀를 기반으로 이전 값들이 모두 계산되어 있다는 가정 하에 나머지 계산을 수행함 타뷸레이션 (Tabulation) : 상향식 (Bottom-up) 방식 - 작은 부분 문제부터 해결한 다음, 해당 과정을..
[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) 변수 사용을 줄이기 위해 재귀의 사용 문제를 해결할 수 있는 점화식 (상태)에 대한 정확한 정의가 필요함 재귀 호출이 멈추고 값이 ..