theory
-
RingBufferAlgorithm/Theory 2021. 4. 7. 10:48
안녕하세요! deque 관련된 문제를 풀다가 간만에 자료구조를 하나 정리해볼까 합니다. 아시다시피 array에서는 뒤에 추가하거나 빼는 작업은 O(1) 이지만, 앞 또는 중간에 추가하거나 빼는 작업은 O(n)의 시간 복잡도가 소요됩니다. 배열의 크기는 고정되어 있기 때문에 앞이나 중간에 작업을 하려면 그 뒤의 나머지 원소들을 모두 옮겨주는 작업이 필요하기 때문이에요. 그럼 원소들을 옮기지 않고 인덱스만 조절하면 되지 않을까? 하는 데서 시작된 아이디어가 RingBuffer가 아닐까 싶어요. RingBuffer는 read / write 포인터를 둬서 배열의 원소들을 움직이지 않고 인덱스만 조절해 덮어쓰는 방식을 사용합니다. 예시를 보면서 살펴볼게요. 처음엔 Read, Write 모두 0번째 인덱스에서 출발..
-
Combination 조합Algorithm/Theory 2020. 8. 25. 14:26
- n개의 원소에서 r 개의 원소를 순서에 상관없이 뽑는 경우의 수 - nCr = n! / (n-r)! * r! - nCr = n-1Cr-1 + n-1Cr 조합? 조합은 n 개의 원소 중에서 순서를 고려하지 않고 원하는 개수만큼 뽑는 경우의 수를 말합니다. 순서를 고려해서 뽑는 순열에서 중복을 제거해준 형태로 볼 수 있죠. 따라서 순열에서 r! 만큼 더 나눠준 형태를 띕니다. nCr = nPr / r! = n! / (n-r)! * r! 조합에는 기억해야 할 중요한 성질이 있습니다. 결론부터 보면, nCr = n-1Cr-1 + n-1Cr 의 공식인데요, 이 의미를 살펴보면, 하나의 원소를 선택할 경우 + 하나의 원소를 선택하지 않을 경우를 나타냅니다. 예를 들어, [1, 2, 3] 에서 2개를 뽑는 경우의..