🖥 Computer Science/알고리즘

🧐 부분 수열(Subsequence) 길이 n인 수열(sequence, ordered list) $S = a_1, a_2, ... a_n$ 이 주어졌을 때, 수열 $S' (= a_{i1}, a_{i2}, ..., a_{ik})$ 가 $1 \leq i1 < i2 < ... < ik \leq n$ 를 만족할 경우, $S'$ 를 $S$ 의 subsequence라 합니다. 🧐 증가 수열(Increasing sequence) 수열 S = $a_1, a_2, ..., a_n$ 에 대하여 $a_1 < a_2 < ... < a_n$ 일 때, increasing sequence라 합니다. 🧐 감소하지 않는 수열(Non-decreasing sequence) 수열 S = $a_1, a_2, ..., a_n$ 에 대하여 $a..

🧐 Memoization 재귀적으로 반복되는 어떠한 함수의 중간 결과를 저장하는 기법을 의미합니다. 🧐 Dynamic Programming Recursion(재귀)과 Memoization을 사용하여 문제를 해결하는 기법을 의미합니다. DP의 본질은 재귀를 올바르고 똑똑하게 하는 것이므로, 재귀를 위한 Recurrence Relation을 올바르게 세우는 것이 중요합니다. 🧐 DP 문제 해결 순서 1. 문제를 정확하게 정의합니다. 2. 정의된 문제에 대하여 부분 문제(Subproblem)을 정의합니다. 3. Subproblem을 이용하여 Recurrence Relation을 세웁니다. 4. Memoization을 이용하여 Recurrence Relation을 계산합니다. - 중간 결과물들들 저장할 자료구조..

🧐 Encoding 알파벳 $\Sigma$ 으로 이루어진 문자열에 대하여 0과 1로 이루어진 binary string(혹은 binary code, codeword) 으로 표현하는 것 간단한 예시를 하나 살펴보면 다음과 같습니다. Binary code A 00 B 01 C 10 D 11 위 표에 주어진대로 다음 문자열 (ABBCCDA) 을 인코딩 해보도록 하겠습니다. A B B C C D A 00 01 01 10 10 11 00 🧐 Decoding Encoding 된 binary string을 다시 original string으로 나타내는 것을 의미합니다. 위의 예시에서 디코딩 시에는 인코딩된 binary string을 두 character씩 확인하면서 해당 codeword에 대응되는 알파벳으로 바꾸어주면..

🧐 Interval Scheduling n개의 작업이 존재하고, 해당 작업들을 수행하는 시간이 각각 [시작 시간, 완료 시간] 으로 주어져 있다고 하겠습니다. 같은 시간에는 하나의 작업만이 가능한 경우, 주어진 시간 내에 최대한 많은 작업들을 수행할 수 있도록 scheduling 하는 것을 Interval Scheduling 이라고 합니다. 이때 작업 $i, j$ 를 동시에 하지 못할 경우, $i$ 와 $j$ 는 overlap 되어 있다고 합니다. ⭐️ Psudocode Initially R is the set of all jobs A is empty // A will store all the jobs that will be scheduled while R is not empty choose job $i..

🧐 Spanning Tree 그레프 내의 모든 정점을 포함하는 트리들 중, 최소 연결 트리를 의미합니다. 최소 연결의 의미는 간선의 수가 가장 적다는 것을 의미하며, 이를 위해서는 사이클이 존재해서는 안됩니다. 따라서 정점의 수가 $n$ 개인 그래프의 Spanning Tree는 edge가 정확히 $n-1$ 개 존재합니다. 또한 하나의 그래프에는 많은 신장 트리가 존재할 수 있습니다. 🧐 최소 신장 트리 (MST) 신장 트리들 중 edge들의 비용(cost)의 총 합이 최소인 트리를 의미합니다. 동일한 Cost를 가지는 Edge가 여러개 있을 경우 MST도 여러 종류가 나올 수 있으며, 반대로 모든 Edge들의 cost가 구분가능한 경우 MST는 단 하나만 존재할 수 있습니다. (이는 뒤에서 증명해 보도록..

🧐 그리디 알고리즘 그리디 알고리즘이란 매 단계마다 현재 상태에서 최적의 해를 만들어주는 것을 선택하며 진행하는 알고리즘입니다. 주로 최적화 문제(Optimization problem)에서 많이 사용되는 알고리즘으로, 대부분의 문제들에서 그리디 알고리즘은 최적해(global-optimal)를 보장해 주지는 않으나 일부 문제들에 한하여 global-optimal 하거나 그에 매우 근접함을 보장해 주는 경우가 있습니다. ⭐️ 그리디 알고리즘 예시 N개의 숫자가 들어있는 바구니가 있습니다. 이 중 그 수들의 합이 최대가 되도록 m개를 고르고 싶습니다. 이러한 경우 그리디 알고리즘을 통해 매 단계에서 현재 바구니에 남아있는 숫자들 중, 제일 큰 숫자를 고른 뒤, 이를 m 번 반복함으로써 문제를 해결할 수 있습니..

🧐 유니온 파인드 자료구조 유니온 파인드 자료구조(또는 서로소 집합(disjoint set) 자료구조)는 다음 두 종류의 연산을 지원하는 자료구조입니다. Union : 두 개의 노드가 포함된 집합을 하나의 집합으로 합치는 연산 Find : 특정 노드가 속한 집합의 루트 노드를 반환하는 연산 우선 동빈나님의 설명이 굉장히 좋기 때문에, 동빈나님의 유튜브 링크를 걸어두도록 하겠습니다. ( 저는 그냥 제가 공부하려고 글 쓴 거니까, 유튜브 보러 가세여..ㅠㅠ ) ⭐️ Find 연산 Find 연산은 다음과 같은 알고리즘을 통해 구현할 수 있습니다. 1. 해당 노드의 부모 노드와 해당 노드를 비교합니다. 이때 두 노드가 같은 경우, 해당 노드는 루트 노드입니다. 2. 만약 같지 않다면 해당 노드의 부모 노드에 대..

🧐 Strongly Connected 방향 그래프에서는 무방향 그래프와 동일하게 Connectivity(연결성)를 정의할 수 없습니다. 방향 그래프에서의 Connectivity는 보통 Strongly Connected 로 정의되며, 해당 정의는 다음과 같습니다. $G$ 는 Strongly Connected 하다 : 임의의 서로 다른 두 정점 $v$, $u$ $\in V(G)$ 에 대하여, $v$ 에서 $w$ 로의 Path와, $w$ 에서 $v$ 로의 Path가 존재한다. 🧐 Strongly Connected Components (강한 연결 요소) 그래프 $G$에 대한 Strong Connected Component $G'$ : $G$ 의 Maximal Strongly Connected Subgraph $..