알고리즘

c언어로 grade school algorithm 구현흔히 하는 직접 곱셈이다.단점 : 계산 시간이 많이 느리다.Wikipedia에 구현 알고리즘 Pseudocode가 있긴한데... 음..일단 나는 index부터 c언어라 다 다르고, char 형 string을 처리해야

Karatsuba 알고리즘을 c언어로 구현했다. 매우매우매우매우 복잡하고 매우매우매우 더럽고 매우매우매우 직관적이지 않은 코드이유1\. Karatsuba 하나를 위해 함수를 여러 개 작성했는데, 더 단순히 할 수 있을듯 하다..2\. Grade school보다 이론상

Quick Sort 알고리즘이란? Quick sort란, 임의의 무작위 배열을 sorting하는 함수의 일종으로, comparison을 기반으로 제작되었다. 시간 복잡도는 comparison을 기반으로 한 함수의 최소인 O(n logn)이다. (one average)

골드바흐의 추측은 다음과 같다.1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.골드바흐의 추측은 유명한

그래프 상에서 최단거리를 구하는 방법은 다양하다.대표적으로, 단순히 모든 edge들을 비교하는 Brute Force가 있을 것이다.하지만 너무 느리고, 그래프가 큰 경우에는 기하급수적으로 느려진다.이를 해결하기 위해 여러 알고리즘이 등장했다.음이 아닌 edge들로 구성

기존의 Dijkstra 알고리즘은 최단거리 탐색에 아주 유용하지만, negative length가 포함되면 사용할 수 없다는 단점이 있다.이를 보완하기 위해 만들어진 알고리즘으로는 BellmanFord 알고리즘과 FloydWarshall 알고리즘, Johnson's 알

APSP를 위해 사용된다.APSP는 All-Pairs Shortest Paths라는 뜻으로, 모든 vertex간 최단 거리를 구할 때 사용한다.BellmanFord로도 source를 모든 vertex로 바꿔가며 찾을 수 있지만, FloydWarshall은 한 번에 모두

앞서 설명한 FloydWarshall처럼 APSP(All-Pairs Shortest Paths)를 계산할 때 사용된다.다만 FloydWarshall보다 시간 복잡도를 조금 더 줄이고자 생긴 Algorithm이다.Sparse한 Graph에서는 훨씬 더 나은 시간 복잡도를

이번에 Leetcode 문제를 풀다 충격적 Solution을 봐서 정리하려 글을 남긴다.먼저 문제이다.문제는 정말 간단하다. 숫자 List가 주어지면 그 중 2개로 가장 큰 XOR 결과를 반환하면 된다.이 문제가 속한 파트는 Trie라서 처음에 Trie로 풀어보려 했다