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

해당 글 87건
팬 케이크 정렬 : 위에서부터 k개를 뒤집는다.

팬케이크 정렬은 유튜브에서 영상으로 한 번 쯤은 보셨을 겁니다. 이것을 최소한으로 뒤집는 횟수를 구하는 것은 경시 대회 이상에서 나올 만한 문제입니다. 우리는 단지, 어떻게 잘 뒤집어서 정렬을 잘 시키면 됩니다. 팬 케이크 더미에서는 위에서 k개만 뒤집을 수 있습니다. 단, k는 총 갯수보다 작을 거에요. 갯수를 n개라고 한다면 2n-3번 이하 뒤집어야 합니다. 이 때에는 어떻게 해야 할까요? 사실, 잘 모르겠습니다. 일단, 1회전이 끝날 때 마다, 2회의 단위 연산을 수행해야 한다는 것은 알겠습니다. 그러면 한 회전마다 어떤 일이 일어나면 좋을까요? 팬 케이크가 이런 식으로 쌓여 있다고 생각해 봅시다. '위에서 k개를 뒤집는다'는 연산 특성상, k가 n이 아니라면, 맨 아랫쪽에 있는 것은 움직이지 않습..
자료알고/알고리즘 2019. 9. 17. 13:29
라빈 카프 알고리즘 : 그래도 비벼볼 만한 문제가 있다.

오늘은 라빈 카프 알고리즘을 배워 보겠습니다. 어떠한 문자열을 수 하나, 혹은 2개, 3개로 압축할 수 있다. 이것은 꽤 엄청납니다. 그렇게 하면, 사실 어떠한 문자열에서 다른 패턴을 찾는 거 또한, 상당히 빠르게 수행할 수 있습니다. 다만, 정확성이 문제라면 문제인데요. 이 부분은 모듈러를 2개, 3개 이상 주는 식으로 해결합니다. 즉, 데이터가 강하지 않을 거라는 믿음을 가지고 수행을 하는 편입니다. 이 알고리즘을 잘 배워놓으면, 문자열 알고리즘을 모를 때, 조금이라도 건드려 볼 수 있습니다. 그러니 알아두시면 나름 좋습니다. 이 포스팅은 부분합 알고리즘을 이해했다는 전제 하에 쓰여졌습니다. 만약에, 그 부분에 대해서 이해를 하지 못하셨다면, 아래 포스팅을 먼저 보시고 오시는 것을 강력하게 권해드립니..
자료알고/알고리즘 2019. 9. 6. 17:16
조화 급수 : ps에서 간간히 나온다.

A(x)을 x의 약수 갯수라고 해 봅시다. 이 때, A(1) + ... + A(n)의 값은 어디에 근접할까요? 이 간단한 질문에서, 오늘의 주제를 이야기 해 보도록 하겠습니다. a가 b의 배수라면, b는 a의 약수입니다. 이 점을 이용해 봅시다. 예를 들어 4의 약수는 1, 2, 4입니다. 그러면, 4는 1의 배수이면서 2의 배수이고, 4의 배수이기도 합니다. 그러면 1에서 출발해서, 1만큼 건너 뛸 때, 2에서부터 출발해서 2만큼 건너 뛰었을 때, 4에서부터 출발해서 4만큼 건너 뛰었을 때, 4를 visit 할 수 있게 됩니다. 그러면 1부터 n까지의 약수의 갯수의 합을 구하는 건 어떻게 하면 좋을까요? 역시 거꾸로 생각하시면 됩니다. 예를 들어서, 약수가 1인 수들을 찾는다고 해 봅시다. 그러면 1,..
자료알고/알고리즘 2019. 9. 5. 18:05
에라토스테네스의 체 : 소수가 아닌 것들을 지운다.

소수를 구할 때 쓰는 알고리즘 중에서, 에라토스테네스의 체 알고리즘이 있습니다. 제가 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