🧐 최장 증가 부분 수열 (LIS)란? 최장 증가 부분 수열, Longest Increasing Subseqeunce는 어떠한 수열의 부분 수열중 오름차순으로 증가하는 가장 긴 수열을 의미한다. (이때 각 원소는 연속할 필요는 없다.) 아래의 예시 수열을 보자. [ 7, 3, 5, 2, 7, 4, 8, 2] 이 수열에서 증가하는 순열에는 [2, 4], [2, 4, 8], [3, 5] 등 다양한 것이 있지만 LIS는 [3, 5, 7, 8]이 된다. 📝 LIS를 구해보자 LIS를 구하는 방법에는 동적 계획법(DP)와 이분탐색으로 크게 두가지의 방법이 있다. DP는 $O(n^2)$의 시간복잡도를 보이며, 이분탐색으로 구현하게 되면 $O(n\log{n})$의 시간복잡도가 나타난다. 1) 동적 계획법 (Dynam..
동적 계획법(Dynamic Programming, DP)은 알고리즘이라기 보다는 하나의 기술이다. 분할 정복에서 사용하는 기법으로, 큰 문제들을 작은 문제들로 쪼개서 그 답을 저장하고 재활용한다. 쉽게 말하자면 '기억하며 풀기' 라고 할 수 있다. 왜 DP를 사용하는가? 다음과 같은 함수를 계산한다고 해보자. $f(a, b) = f(a-1, b)+f(a, b-1)\space(a, b\ge 1)$ $f(0, n)=f(n, 0)=1$ 이떄 f(2, 2)를 계산한다고 하면 다음과 같은 계산 과정를 거치게 된다. 위 에서는 총 5번의 연산을 수행하는데, 이때 f(1, 1)에 대한 연산을 2번 수행하고 있으므로 이를 미리 연산한다고 가정하면 f(2, 2)를 구하기 위해 4번의 연산만 수행하면 된다. 만약 a, b..
DFS와 BFS는 모두 그래프를 탐색하는 알고리즘이다. 그래프란 노드(Node)과 간선(Edge)로 이루어진 자료구조로, 그래프를 탐색한다는 것은 모든 정점을 방문하는 과정을 의미한다. DFS와 BFS는 이러한 정점을 방문하는 과정에서의 차이로 구분된다. 이 글에서는 DFS와 BFS에 대해 이야기 해볼것이다. 깊이 우선 탐색 (DFS) 이름에서 알 수 있는 DFS는 깊이를 우선한다. 즉, 분기를 만나면 현재 진행 중인 분기를 완전히 깊게 탐색을 마친 후 다음 분기를 탐색한다. DFS는 다음과 같은 특징을 갖는다. 모든 노드를 방문할 때 주로 사용한다. 구현이 BFS보다 간단하다. 검색속도 자체는 BFS보다 느리다. a. 구현 (1) 인접 행렬을 이용한 구현 #include using namespace s..
