알고리즘 검색 결과

해당 글 51건
양방향 탐색 : 시작점과 도착점에서 동시에 탐색을 한다.

bfs는 뎁스가 깊어질수록 생성되는 state 수가 매우 많아집니다. 그러면, depth를 줄일 수만 있다면, 속도가 획기적으로 개선된다는 이야기 또한 됩니다. 시작점과 도착점에서 동시에 bfs를 하는 방식을 양방향 bfs라고 하는데요. 이렇게 하면, s에서 e로 가는 최적해가 2x일 때, s에서 x만큼, e에서 x만큼의 깊이만 탐색하면 됩니다. s에서만 출발하면 2x만큼 탐색하는 것에 비하면 거의 절반 가까이 줄어버린 셈입니다. 일단 어떤 식으로 탐색을 하는지 개략적으로 보고, 입문 문제를 풀어보도록 합시다. 백준에서 흔히 알려진, 루빅의 사각형은 구현이 안 되면 매우 힘든 문제이기 때문에, 입문 문제로 제외하였습니다. branch factor가 b라고 해 봅시다. 즉, 한 상태를 queue에서 뺐을 ..
자료알고/알고리즘 2019. 8. 16. 14:34
최대공약수 최소공배수 알고리즘 : 짧은 코드 이해해 봅시다.

오늘은 간단하게, 최대 공약수와 최소 공배수를 구하는 알고리즘을 알아보도록 하겠습니다. 먼저 a와 b의 최대 공약수란, a와 b를 동시에 나누어 떨어지게 하는 최댓값을 의미해요. 예를 들어서 a가 6이고 b가 3이라면 3이 gcd가 됩니다. 그렇다면 가장 간단한 알고리즘을 생각해 볼 수 있습니다. a와 b의 최솟값을 r이라고 해 봅시다. r부터 1까지 계속 a와 b를 나누어 보면서, 만약에 두 수를 동시에 나누는 수가 있다면 break를 걸어버리는 겁니다. 사실, 이러한 방법은 꽤 효과적일 수 있습니다. 그런데 a = 20억, b = 10억 7 정도가 된다고 하면, 수행 시간이 상당히 길어질 겁니다. 왜냐하면 b는 소수이기 때문입니다. b를 나누는 수는 1과 10억 7밖에 없는데, 20억을 나누는 수는 ..
자료알고/알고리즘 2019. 8. 7. 17:50
c언어 qsort 함수 예제 : 두 문제를 풀면서 이해해 봅시다.

알고리즘에, 정렬 시리즈를 계속 올리고 있습니다. C언어에서도, 손쉽게 빠른 정렬을 쓸 수 있는데요. 에 빠른 정렬을 하는 qsort 함수가 있습니다. 이것의 원형은 다음과 같습니다. void qsort(void *base, size_t num, size_t size, int (*compare)(const void *,const void *)); 뭔가 원형이 복잡해 보이는데요. 특히 4번째 인자가 조금 복잡해 보입니다. 이게 무엇인지 천천히 해석해 보겠습니다. 먼저 identifier를 찾을 건데요. compare입니다. 오른쪽부터 볼 건데요. (나 )를 만날 때 까지 읽어요. compare 뒤에 바로 )가 있으니까, 왼쪽을 봅니다. 보는데 *가 있네요. 즉, compare is pointer라는 겁니다..
레퍼런스/예제 2019. 8. 5. 22:23
약수 구하기 알고리즘 : n^0.5만 보고도 구할 수 있다.

약수를 구하는 것은, 정수론 문제를 풀 때 기본이 되는 연산 중 하나입니다. 우리는 약수를 구하는 알고리즘을 다음과 같은 구현을 생각할 수 있을 겁니다. 이것은 간단합니다. n의 약수를 구할 때, 나누는 수를 1부터 n까지 모두 검사해 봅니다. 만약에 n을 나누는 수 r로 나눴을 때, 나머지가 0이라면, r로 나누어 떨어지는 겁니다. 이것은 올바른 결과를 냅니다. 하지만, 오래 걸립니다. 예를 들어서, n의 값이 10^12만 되어도 아래와 같은 연산을 10^12번 해야 할 겁니다. 10^12번. 상당히 끔찍하지 않나요? 1초에 단순 연산을 10^9회 정도 한다고 한다면, 1000초, 약 20초, 어마무시한 시간이 걸려버립니다. 이 끔찍한 시간을 줄일 수 있는 방법이 없을까요? Lemma 하나 들고 옵시다..
자료알고/알고리즘 2019. 8. 4. 23:51
기수 정렬 (radix sort) : 버킷만 있으면 된다.

오늘은 기수 정렬에 대해서 알아보도록 하겠습니다. 이것은 키 2개를 가지고 비교하는 정렬이 아닌데요. 이 특성은 저번에 배운, counting sort의 '2개의 키 값을 비교'하는 '비교 기반 정렬이 아니다' 라는 성질을 가지고 있습니다. 이들과, merge sort는 키 2개를 직접 비교하는 비교 기반 정렬이냐, 아니냐의 차이가 있어요. 아래 두 개의 글을 잘 보셔도 눈치를 채실 수 있을 듯 싶습니다. [관련글] 빈도를 저장하는 counting sort. 알아봅시다. 정렬된 두 배열을 합치는 합병 정렬 알아보아요. 그러면, 이것은 어떻게 동작할까요? 저는 1가지 용어만 정의하겠습니다. b진법으로 잡고 정렬한다. 버킷의 갯수가 b개이다. 우리는 양의 정수를 표현할 때, x진법으로 표현할 수 있습니다. ..
자료알고/알고리즘 2019. 8. 2. 01:07