Computer Science

[Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어

🤔 그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는 정점과 간선으로 구성된 자료구조를 뜻합니다. 이번 포스팅에서는 그래프를 구성하는 단어들에 대한 기본용어를 알아보겠습니다. 🔎 그래프의 기본 용어 제가 가장 질투하면서 존경하는 친구의 블로그에 너무 잘 정리되어 있어서 해당 블로그를 살펴보는 것이 도움이 될 것입니다. 그래프의 기본 용어는 이해보다 암기가 필요한 부분이기때문에 포스팅으로 넘어가도록 하겠습니다. 🔎 참조 https://ttl-blog.tistory.com/954?category=964962 [알고리즘] 그래프 (1) - 그래프의 기본 용어 🧐 그래프 (Graph) 그래프는 정점(vertex)들과 간선(edge)들로 이루어..

[Algorithm] 분할정복(5) - Median of Medians

🤔분할정복 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다. 이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다. 이번 포스팅에서는 Median of Medians 에 대해 알아보겠습니다. 🔎 Median Of Medians 크기가 $n$인 배열 A가 주어졌을 때 A에서 k번째 작은 원소를 찾는 알고리즘을 찾아보겠습니다. 앞선 Quicksellect의 시간복잡도 분석에서 결국 Quickselect의 성능은 '좋은 pivot을 얼마나 빠르게 찾아내는가'에 달려있다는 것을 알 수 있었습니다. 좋은 pivot을 찾기 위한 효율적인 알고리즘이 있다면 성능이 좋아..

[Algorithm] 분할정복(2) - Multiplication

🤔 분할정복 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다. 이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다. 이번 포스팅에서는 분할정복의 Multiplication 예시를 알아보겠습니다. 🔎 Multiplication 두 n 비트 이진수인 $x$와 $y$를 곱하는 문제를 해결해보겠습니다. 분할정복 기법을 사용하여 이론적으로 더 빠른 알고리즘을 디자인 하는 방법에 대해 알아보겠습니다. 편의상 $n$은 2의 거듭제곱 꼴이라 가정하고, $x$의 왼쪽 $n/2$ 비트 부분과 나머지 부분을 각각 $x_L, x_R$이라고 하겠습니다. 마찬기자로 $y_L, y..

[Algorithm] 분할정복(1) - Master Theorem과 일반해

🤔 Divide And Conquer 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다. 이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다. 이번 포스트에서는 분할정복을 Master Theorem의 일반해를 구하는 방법을 자세하게 알아보겠습니다. 🔎 Master Theorem Master Theorem에서 Input Size가 $n$일때 분할정복 알고리즘의 일반적인 패턴은 아래와 같습니다. 상수 $a > 0, b > 1, d ≥ 0$에 대하여 1. 문제를 size가 $\frac{n}{b}$인 $a$개의 subproblem으로 나눈다. (recursivel..

[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 이진수의 덧셈의 시..