자료알고 검색 결과

해당 글 130건
조화 급수 : 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
자료구조 덱 (deque) : 앞과 뒤에서 추가되고 삭제된다.

자료구조의 덱, 그러니까 deque는 queue하고 비슷합니다. front와 back, 이렇게 2개의 포인터 있습니다. 그런데, 큐가 front에서 삭제가 일어나고, back에서 삽입 연산이 일어나는데 비해서, 덱은 front에서도 삽입과 삭제가, back에서도 삽입과 삭제가 일어납니다. 이 연산만 구현하려면, 사실 List로 구현하는 게 제일 간단해 보입니다. 먼저 다음과 같이 초기화를 시켜 봅시다. 그러면 이 때가 비어있는 상태일 겁니다. head->next가 tail이고, tail->prev가 head일 때, empty 상태라고 판단할 수 있습니다. 저는 이 두 개의 더미를 인위적으로 잇기만 하였습니다. 여기에서 push_front 연산을 수행해 봅시다. 이것은 맨 앞에 원소를 추가하는 것입니다. ..
자료알고/자료구조 2019. 8. 22. 01:05
왜 유클리드 알고리즘 함수는 최악의 경우 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