자료알고 검색 결과

해당 글 130건
퀵 정렬 : bad partition이 발생할 경우 문제가 된다.

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

sleep sort, 슬립 정렬이라고 2년 전이였나? 3년 전에 꽤 핫했던 친구가 있습니다. 사실 왜 Hot했는지는 이해가 가지 않습니다. 아이디어 정도만 보시고 넘어가셔도 무난할 듯 싶어요. 대략적인 구조를 보면, worker 역할을 하는 객체에게 몇 단위시간 동안 sleep 할 건지 그러한 정보를 넘겨주고, 해당 객체가 몇 단위 시간 동안 깨어나면 출력하는 식으로 프로그램을 짜는 듯 싶습니다. 더 쉽게 말하면, 길이가 n인 데이터가 있을 때, worker_i는 arr[i] 단위시간 만큼 잠이 듭니다. t만큼 시간이 지났을 때, t만큼 잠들어야 하는 worker들이 모두 깨어나면서 t를 출력하는 것입니다. 단위 시간이 매우 작다면, 꽤 효율적일 겁니다. 코드는 생각보다 짧은데요. 많이 찾아볼 수 있는 ..
자료알고/알고리즘 2019. 8. 13. 18:10
조세퍼스 문제 : 어느 순서대로 제거되는지 출력해 보자.

조세퍼스 문제는 다음과 같습니다. 시계 방향으로 1번부터 n번 사람이 있습니다. 처음에 k번째 사람을 뽑습니다. 뽑은 사람은 제거가 됩니다. 제거가 된 사람으로부터 k번 시계 방향으로 이동해서 있는 사람을 뽑습니다. 그 사람은 제거됩니다. 이런 식으로 n번 수행했을 때, 어떤 순서대로 제거되는지 구할 수 있을까요? 예를 들어 n = 7이고 k = 3이라면, 3, 6, 2, 7, 5, 1, 4 순서대로 제거가 될 겁니다. 나이브하게 풀었을 때, 주로 일어나는 연산은 2개입니다. 탐색, 삭제. List를 사용하면 배열에 비해 유리할 듯 싶습니다. 그렇지만, 탐색이 매우 많이 일어난다면 꼭 유리하다고 할 수도 없어요. k칸 이동을 O(1)만에 할 수 없기 때문입니다. 대신 배열은 랜덤 접근이 됩니다. 따라서 ..
자료알고/자료구조 2019. 8. 10. 19:51
비교 기반 정렬 : 왜 하한이 nlogn일까?

비교 기반 정렬은, 키 2개를 가지고 비교를 하는 것들을 말합니다. 예를 들어서, 우리가 sort 함수를 호출할 때 이런 식으로 compare 함수를 재작성을 합니다. 그러면 이것은 key a와, b를 비교한 것입니다. 대다수의 정렬은 이 키 값 2개를 비교해서 순서를 ordering 한다고 보시면 됩니다. 물론 예외가 몇 개 있는데요. 카운트, 버킷, 기수 정렬 등이 예외입니다. 크기가 n인 배열이 있습니다. 물론, 이 n개의 수는 서로 다른 수라고 합시다. 보통 그렇게들 많이 주어지니까요. 그러면, 서로 다른 수 n개를 순서 고려해서 배열하는 가짓수는 n!입니다. 즉, 길이가 n인 순열이 n!개가 나온다는 것입니다. 예를 들어서 n = 4라고 해 봅시다. 그러면 1번째 칸에는 4개 중 하나만 들어가면..
자료알고/알고리즘 2019. 8. 10. 11: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