알고리즘

[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..

[Algorithm] 알고리즘 기본(2) - Basic Arithmetic

🤔 Basic Arithmethic 덧셈, 뺄셈, 곱셈, 나눗셈 즉 기본연산(사칙연산)을 Basic Arithmethic이라고 합니다. n-bit를 가지고 있는 기본적인 bit 연산에 대해 알아보도록 하겠습니다. 이전에 모든 계산에 있어 단일 bit에 대해 기본적인 bit 연산에 $O(1)$시간이 소모된다고 가정하겠습니다. 🔎 두 n-bit 이진수의 덧셈 $53$과 $35$의 이진수인 "1 1 0 1 0 1"과 "1 0 0 0 1 1"을 예시로 더해보겠습니다. 위와 같이 6bit 연산에서 최상위 비트에서의 Carry가 발생하여 7bit가 결과값으로 출력되었습니다. 두 개의 n-bit 짜리 이진수가 주어졌을 때 n 번의 덧셈이 반복되면서 일어나는 것을 알 수 있습니다. 즉 두 n-bit 이진수의 덧셈의 시..