algorithm
[Algorithm] 그래프 알고리즘(2) - DFS(깊이우선탐색)(1)
🤔그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는 정점과 간선으로 구성된 자료구조를 뜻합니다. 이번 포스팅에서는 DFS에 대해 알아보도록 하겠습니다. 👉이전 포스팅 더보기 2022.10.04 - [Computer Science/Algorithm] - [Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어 [Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어 🤔 그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는 정점과 간선으로 구성된 자료구조를 뜻합니다. 이번 포스 2t-hong.tistory.com 🔎 Reachability Reachabil..
[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] Master Theorem 맛보기
이번 포스팅은 Master Theorem을 처음 배우면서 맛보기(?)를 하면서 끄적인 것이기 때문에 두서가 없습니다. 분할정복에 대해 자세히 알고 싶으신 분은 아래를 참고해주시면 감사하겠습니다. 👉 분할정복 더보기 닫기 2022.09.28 - [Computer Science/Algorithm] - [Algorithm] 분할정복(1) - Master Theorem과 일반해 [Algorithm] 분할정복(1) - Master Theorem과 일반해 🤔 Divide And Conquer 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말 2t-hong.tistory.com 2022.09.29 - [..