Computer Science

[Algorithm] Sort(Selection, Insertion, Bubble)

🚗 Selection Sort 선택 정렬을 데이터 중 가장 작은 값의 데이터를 선택하여 앞으로 보내는 정렬이다. Selection Sort is a sort that selects the data with the smallest value and sends it forward. Time complexity $ = N + (N-1) + (n-2) + ... + 2 + 1 $ $ = \frac{N(N+1)}{2}\ $ $ = N * N $ $ = O(N^2) $ Best : $N(O^2)$ Average : $N(O^2)$ Worst : $N(O^2)$ #include using namespace std; void selectionSort(int arr[], int n) { for (int i = 0; i ..

[Algorithm] Dynamic Programming(5) - 플로이드 와샬 (Floyd-Warshall)

🤔Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 포스팅에서는 All-pairs shortest Paths에 대해 알아보도록 하겠습니다. 가장 대표적인 알고리즘인 플로이드 와샬 알고리즘을 통해 해당 알고리즘을 해결하겠습니다. 🔎 All-pairs Shortest Path 이전의 다익스트라 알고리즘 또는 벨만포드 알고리즘의 경우에는 하나의 시작 정점 source에서 다른 모든 정점 들 간에 최소 경로를 구하는 알고리즘입니다. 이와 같은 문제를 single-source 최단 경로 문제라고 합니다. 그에 반해 단일 source가 아닌 임의의 모든 두 정점 ..

[Algorithm] Dynamic Programming(4) - 벨만포드(Bellman-Ford)

🤔Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 포스팅에서는 최단 경로 문제중 하나인 벨만포드 알고리즘에 대해 알아보도록 하겠습니다. 🔎 최단 경로 문제(Shortest Path Problem) ✍️ 최단 경로 문제란? 그래프 G = (V, E)의 상에서 정점 u에서 v로의 가장 짧은 경로의 길이를 구하는 문제를 최단 경로 문제라고 합니다. 우리는 edge-weighted graph의 경우만을 생각하도록 하겠습니다. ( 이때 |V| = n, |E| = m ) ✍️ Edge-weighted graph 그래프 G의 edge(a, b)에 가중치 w(a, ..

[Algorithm] Dynamic Programming(3) - Edit Distance(편집거리)

🤔 Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 포스팅에서는 Edit Distance 문제를 해결하기 위해 Dynamic Programming을 사용하여 해결하는 과정을 정리했습니다. Edit Distance 문제는 어떤 단어와 비슷한 단어는 어떤 방식으로 정의할 수 있을까? 라는 의구심에서 시작되었습니다. 아래의 그림과 같이 Microsoft Word spell check 기능을 사용하면 비슷한 단어를 자동으로 추천해줍니다. 우리도 이를 Edit Distance를 통해 해결해보겠습니다. 🔎 Edit Distance 위에서 어떤 단어와 비슷한 단어..

[Algorithm] Dynamic Programming(2) - LIS(Longest Increasing Subsequence)

🤔 Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 포스팅에서는 LIS문제를 해결하기 위해 Dynamic Programming을 사용하여 해결하는 과정을 정리했습니다. 🔎 LIS(Longest Increasing Subsequence) ✍️Subsequence 길이 n 인 sequence (ordered list) $S = a_1, a_2, …, a_n$ 이 주어졌을 때, sequence $S’ = a_{i1}, a_{i2}, .., a_{ik} 가 1≤ i1 < i2 < … < ik ≤n$ 를 만족할 경우 $S’$ 을 $S$의 subsequence ..