알고리즘 검색 결과

해당 글 51건
에라토스테네스의 체 : 소수가 아닌 것들을 지운다.

소수를 구할 때 쓰는 알고리즘 중에서, 에라토스테네스의 체 알고리즘이 있습니다. 제가 ps를 하면서 상당히 많이 썻던 것인데요. 결론부터 말씀드리겠습니다. [1,n]까지 해당 알고리즘을 이용해서 훑는 경우에, 시간 복잡도는 O(nlog(logn))입니다. 생각보다 상당히 빠르게 동작한다는 것을 알 수 있어요. [1,14]의 범위에 있는 자연수가 소수인지 아닌지 빠르게 훑어봅시다. 하늘색은, 아직 visit를 하지 않았다는 의미입니다. 일단 이것이 무엇을 의미하는지 추후에 보도록 합시다. 먼저, 1은 소수가 아니므로, 노란색으로 표시를 합니다. 다음에, 2를 봅시다. 2는 하늘색으로 표시가 되어 있으므로, 방문한 녀석이 아닙니다. 그러면 여기서 우리는, 2를 제외한, 2의 배수들을 모두 제거를 할 건데요...
자료알고/알고리즘 2019. 9. 2. 18:30
중복 조합 : 어떻게 ps에서 쓰일까요?

가끔 ps에서 중복 조합이 등장하는데요. nHk는, 서로 다른 n개의 원소에서 중복을 허용해서, 순서에 상관 없이 k개를 뽑는 가짓수를 의미합니다. 예를 들자면, n = 2이고 k = 2라고 해 봅시다. 원소는 0, 1이라고 해 봅시다. 이 때, 중복을 허용하지 않으면, 2개 중에 2개를 뽑는 가짓수는 (0, 1) 이렇게 나올 거에요. 그런데, 중복을 허용하는 경우 (0, 0)도 가능하고 (0, 1)도 가능하고, (1, 1)도 가능합니다. 따라서, 3이 나옵니다. n = 2이고 k = 3인 경우는 어떤가요? 중복을 허용하는 경우, (0, 0, 0), (0, 0, 1), (0, 1, 1), (1, 1, 1) 이렇게 4개가 나옵니다. 이것을 다른 문제로 변환해 봅시다. 우리는 0을 x개 뽑고, 1을 y개 뽑..
자료알고/알고리즘 2019. 8. 24. 19:02
퀵 정렬 평균 시간 복잡도 : 왜 O(nlogn)일까?

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

코딩 테스트에서 next_permutation의 사용 빈도는 상당히 높을 겁니다. 특히 역량 테스트라고 불리는 것에서는요. 구현이 들어가면 대략 50% 정도는 조합, 순열 등에서 나오는데요. 그 때, 이전 순열이라던지 다음 순열을 구하기 위해서 쓰는 함수가 저 함수입니다. 이전 순열은 데이터를 조금 변형을 하면 구할 수 있고요. 그러면 이 함수가 어떻게 구현이 되어 있을까요? 만약에 레퍼런스 없이 구현하라고 하면 어떻게 해야 할까요? 단계별로 이해해 봅시다. 사실 이 함수의 복잡도는 O(n)입니다. 왜 그렇게 나올 수가 있는 것인지, 상대적으로 비효율적인 구현 방법으로 먼저 구현해 보고 이야기 하도록 하겠습니다. O(n^2)의 핵심 접근은, 결정 함수입니다. 이게 무슨 어려운 것이냐라고 생각하실 수도 있..
레퍼런스/분석 2019. 8. 19. 17:59
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