Computer Science/Algorithm

[Algorithm] Dynamic Programming(1) - Warm Up

🤔Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 시간에는 다이나믹 프로그래밍이 어떤 것인가에 대해서 알아보도록 하겠습니다. 🔎 피보나치 수열 컴퓨터를 배운 사람이라면 한 번쯤 풀어봤을 피보나치 수열 문제입니다. (피보나치 수열을 잘 모르시는 분은 해당 링크를 참고하시길 바랍니다.) 피보나치 수열은 Recursion을 이용하여 해결할 수 있습니다. 👉 피보나치 수열 수도코드 더보기 fib(n): if(n == 0) return 0 if(n == 1) return 1 return fib(n-1) + fib(n-2) 해당 알고리즘의 시간 복잡도는 subp..

[Algorithm] 분할정복(4) - Selection

🤔분할정복 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다. 이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다. 이번 시간에는 Good Pivot을 찾기 위한 Selection 알고리즘에 대해 배워보도록 하겠습니다. Good Pivot을 찾는 것은 MOM(Median Of Medians)를 찾는 것에 필수적인 정보이기 때문에 꼭 제대로 숙지해야합니다. 🔎 Selection - Quick Select 🤔 Problem 크기가 $n$인 배열 A가 주어졌을 때, A에서 $k$번째로 작은 원소를 찾아야 합니다. 특별히 $k$가 $n/2$ ($n$이 even 인..

[Algorithm] 분할정복(3) - Matrix Multiplication

🤔 분할정복 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다. 이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다. 알고리즘의 Basic Arithmetic의 연장선인 행렬곱을 알고리즘의 관점에서 알아보겠습니다. 행렬에 대한 알고리즘 공부가 하기 싫어서 미루고 있다 이제야 포스팅 하게 되었습니다. 행렬 중에서도 두 $n\times{n}$ Matrix의 경우만 알아보도록 하겠습니다. 🔎 두 $n \times n$ Matrix 곱하기 연산 먼저 행렬의 각 entry들 간의 사칙연산은 모두 $O(1)$시간이 걸린다고 하겠습니다. 예시로 아래의 행렬을 통해 두 ..

[Algorithm] 그래프 알고리즘(3) - DFS(2), Biconnected Graph

🤔 그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는 정점과 간선으로 구성된 자료구조를 뜻합니다. 이번 시간은 저번 포스팅에 이어 DFS에 대해 조금 더 알아보고 Biconnected Graph에서 Articulation Point를 찾는 방법에 대해 집중적으로 알아보도록 하겠습니다. 👉 이전 포스팅 더보기 2022.10.04 - [Computer Science/Algorithm] - [Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어 [Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어 🤔 그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는..

[Algorithm] 그래프 알고리즘(2) - DFS(깊이우선탐색)(1)

🤔그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는 정점과 간선으로 구성된 자료구조를 뜻합니다. 이번 포스팅에서는 DFS에 대해 알아보도록 하겠습니다. 👉이전 포스팅 더보기 2022.10.04 - [Computer Science/Algorithm] - [Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어 [Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어 🤔 그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는 정점과 간선으로 구성된 자료구조를 뜻합니다. 이번 포스 2t-hong.tistory.com 🔎 Reachability Reachabil..