자료알고/알고리즘 검색 결과

해당 글 87건
왜 유클리드 알고리즘 함수는 최악의 경우 O(log)일까?

질문이 왔습니다. 왜 확장 유클리드는 최악의 경우에, 대략 log(min(a,b))개의 gcd 함수를 호출하나요? 생각보다 빨리 끝나는 것 같은데. 이 질문에 대한 답을 하기 위해서는 재귀 함수의 기저 조건에서부터 위로 쭉 올라가 보아야 합니다. 그러면 기저 조건을 먼저 볼 건데요. gcd(2,1)의 값은 1입니다. 2는 1로 나누어 떨어지기 때문입니다. 이 때, gcd는 재귀적으로 1번 호출합니다. 유클리드 알고리즘은, a = bQ+r꼴로 표현이 될 때 (단 0b이면서 3으로 나눴을 때 나머지가 2인 가장 작은 자연수는 얼마인가요? 5입니다. 우리는 b 다음에 a 이렇게 커지는 수열을 생각할 때, a를 최대한 작은 친구를 선택하는 겁니다. 최대한 천천히 증가하게끔. 그러면 gcd(5,3)을 호출하였을 ..
자료알고/알고리즘 2019. 8. 21. 15:50
퀵 정렬 평균 시간 복잡도 : 왜 O(nlogn)일까?

평균적으로 퀵 정렬은 머지보다, 빠른 것으로 알려져 있습니다. 물론 최악의 경우에, skew만 계속 일어나면, 별로 좋지는 않겠지만요. 이건 왜 그럴까요? 머지에 비해서 Quick은 추가적인 공간을 쓰지 않기 때문에 그렇습니다. 사실, 이게 제일 큰 요인입니다. 이것이 어떻게 동작하는지 이해가 가지 않으시다면, 관련 글을 보고 오시는 것도 좋겠습니다. [관련글] 퀵 정렬에 대해서 알아봅시다. 그러면 평균 복잡도는 왜 O(nlogn)일까요? 몇 가지 가정을 해 봅시다. partition이 일어날 때, arr[0]을 pivot으로 잡습니다. 이 때, 정렬을 할 데이터의 갯수가 n개라고 하면, arr[i]보다 작은 것의 갯수가 0개, 1개, 2개, ... , n-1개인 경우가 있을 거에요. 그러한 확률이 모두..
자료알고/알고리즘 2019. 8. 20. 16:18
k번째 수 찾기 : count sort를 응용해 봅시다.

백준 11004번, k번째 수를 구하는 문제가 있습니다. 오름 차순으로 정렬하였을 때, k번째 수가 무엇인지를 묻는 문제입니다. 그런데 배열의 크기가 500만입니다. 그렇기 때문에 fast io를 쓴 다음에 sort를 쓰거나, 아니면 다른 방법을 써야 하는데요. 저번에 배운 count sort를 조금 응용해 보도록 하겠습니다. [관련 글] count sort에 대해 알아봅시다. 이게 k번째 수와 어떠한 관련이 있을까요? [0, 20억] 사이에 있는 수는 다음과 같이 표현할 수 있습니다. 65536a + b (단 a, b는 0보다 크거나 같고 65536보다 작은 자연수) 즉, 65536 진법으로 표현할 수 있습니다. 그러면 몫을 구할 때 (x>>16)을, 나머지를 구할 때에는 (x&65535)로 구할 수 ..
자료알고/알고리즘 2019. 8. 17. 18:27
양방향 탐색 : 시작점과 도착점에서 동시에 탐색을 한다.

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

퀵 정렬 알고리즘은 간단하게 언급만 하고 넘어가겠습니다. 사실, ps에서 그리 많이 쓰이는 정렬 방법은 아니기 때문입니다. 다만, 평균적으로는 병합 정렬보다는 빠른데, 그 이유는 다음 시간에 평균 복잡도를 분석하면서, 언급하도록 하겠습니다. 먼저 퀵 정렬은 피봇을 잡는 것부터 시작합니다. arr의 [s,e] 구간을 정렬한다고 하면, pivot을 선택해서, 그 피벗이 있는 위치와 arr[s]의 값을 교환합니다. 이는, 피봇을 선택하는 함수와, 그걸 토대로 divide 하는 것을 별개로 생각하기 위해서입니다. 여기서 저는 pivot을 5로 잡았습니다. 그리고, 우리는 2개의 포인터를 잡을 겁니다. 이는 각각 le와 ri 포인터입니다. 어떤 식으로 교환이 일어나는지만 보시면 되는데요. 우리는 ri 포인터가 s..
자료알고/알고리즘 2019. 8. 15. 12:12