Algorithm/Theory
멱집합(모든 부분집합)을 비트 벡터를 이용해 구현
멱집합(모든 부분집합)을 비트 벡터를 이용해 구현
2020.02.22원소 개수가 n개이면, 모든 부분집합의 개수는 2^n개가 되므로 멱집합의 원소 개수는 2^n개다. 너무 많다. 비트 벡터를 이용해서 메모리를 n 만큼만 쓰는 방법 https://github.com/umbum/effective-java-3e-source-code/blob/master/src/effectivejava/chapter7/item47/PowerSet.java AbstractList에서 src라는 외부 변수를 사용하고 있다. 클로저.
Dynamic programming, 기억하며 풀기
Dynamic programming, 기억하며 풀기
2018.09.26DP를 번역하면 동적 계획법 이지만 책 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을 본질적인 의미를 더 살려서 기억하며 풀기로 더욱 적절하게 번역하였다. 즉, 이전에 구한 작은 부분 문제의 답을, 다음 문제를 푸는데 이용하는 문제 해결 방식. 이전 답을 재활용하면서 더 큰 문제를 해결하는 방식이다. 피보나치 수열 구하기(그냥 일반항에 대입하면 나오기는 하지만) 처럼 최종 결과를 도출하기 위해서 이를 더 작은 단위의 문제로 나눠서 먼저 해결하고 그것을 조합하여 최종 문제를 해결하는 방법을 말한다. * 분할 정복과 비슷하나, 분할 정복은 분할된 문제가 서로 영향을 주지 않아 독립적으로 해결 가능하다는 차이점이 있다. 진행 방식에 따라 Top-down(Memoization)과 Bottom-up으로 ..
Linked list 구현
Linked list 구현
2018.07.20```c typedef struct _node { unsigned int data; struct _node *next; } node; typedef struct _l_list { node *head; node *tail; } l_list; ``` `` node`` 하나만 써서 관리하면 두가지 단점이 있는데, 1. 항상 head를 잃지 않도록 조심해야한다. 2. 끝에서 부터 접근하지 못한다. (항상 head에서 부터 접근해야 한다.) 반면 `` l_list``라는 구조체를 하나 만들어 head와 tail을 가리키도록 만들어 주면, 앞뒤로 접근 가능하며 언제나 head를 따라갈 수 있음을 보장할 수 있다. C 같은 경우, 잘못해서 `` l_list``를 넘겨야 하는 곳에 `` node``를 넘기는 경우 타입..
선형 시간 안에 중앙값 선택하기
선형 시간 안에 중앙값 선택하기
2018.05.10최악의 경우에도 선형 시간에 중간값을 선택할 수 있는 알고리즘은 다음과 같다. * 아래는 median을 찾는 예이지만, k번째 작은 값 찾는 문제에 적용 가능하다. ``c Element select(SetOfElements S, int k)`` 중앙값만 찾는 거라면 k 파라미터가 필요 없지만, 일반적인 선택 문제로 확장하면 k 파라미터가 필요함. k는 몇번째로 큰 값을 찾을건지. k번째로 작은 값을 찾는다. `` k=n/2`` 를 넘기면 중간값을 찾겠다는 것. 알고리즘 (k번째 작은 값 찾기를 이용해 median 찾는 예제) 1. 입력 배열이 n개라면 원소 5개짜리 \\(\lceil n/5 \rceil\\) 그룹으로 나눈다. 마지막 집합은 \\(n \mod 5\\)개 원소를 가질 수 있다. 2. 각 그룹..
max, min 동시에 찾기 / 두 번째로 큰 값 찾기
max, min 동시에 찾기 / 두 번째로 큰 값 찾기
2018.05.06min, max 모두 찾을 때 조금 더 효율적인 방법 배열에서 최댓값과 최솟값을 모두 찾는 단순하고 일반적인 방법은 최대키, 최소키를 각각 찾는 방법이다. 이런 방식은 최대키를 찾는데 \\(n-1\\)번 비교, 최소키를 찾는 문제도 이와 같으므로 총 \\(2n-2\\)번 비교하게 된다. 다음과 같은 방법을 사용하면 최댓값과 최솟값을 모두 찾는데 \\(3\lfloor{n/2}\rfloor\\)번만 비교할 수 있다. 입력 원소의 각 쌍에 대해 먼저 둘을 비교한 다음, 큰 쪽을 `` max``와 비교하고 작은 쪽을 `` min``과 비교한다. 이렇게 되면 ``c (max, x1), (max, x2), (min, x1), (min, x2)`` 4번 비교해야 하는 것을 ``c (x1 , x2), (max, x1)..
5개의 원소를 7번 비교로 정렬하기 / 6번 비교로 중간값 찾기 (+ 상대자 논증)
5개의 원소를 7번 비교로 정렬하기 / 6번 비교로 중간값 찾기 (+ 상대자 논증)
2018.05.035개의 원소를 7번 비교로 정렬하기 정렬의 lower bound는 \\(\lceil\lg{n!}\rceil\\)이므로, 5개의 원소를 정렬하려면 최악의 경우 최소 7번은 비교해야 한다. (quick, merge, heap 모두 최악의 경우 8번 비교하게 된다.) 최악의 경우에도 7번만 비교하는 알고리즘의 핵심은 이미 정렬된 부분에 대해서 binary search를 적용한다는 점이다. 이런 류의 정렬 알고리즘의 문제점은 삽입할 위치보다 뒤쪽에 있는 원소들을 모두 한칸씩 밀어내야 한다는 오버헤드가 크다는 점을 고려해야 한다. \\(a, b, c, d, e\\) \\(a > b\qquad\cdots 1\\) \\(c > d\qquad\cdots 1\\) \\(a > c\qquad\cdots 1\\) → {a,..
점근적 표기 / 평균 수행 시간 분석
점근적 표기 / 평균 수행 시간 분석
2018.04.20\\(f(n) = \Theta(g(n)) \approx a = b\\)\\(f(n) = O(g(n)) \approx a \le b\\)\\(f(n) = \ o(g(n)) \approx a b\\) \\(W(n) = \max\{\ t(I)\ |\ I \in D_n \}\\) 평균 수행 시간 분석\\[A(n) = \sum_{I \in D_n} Pr(I)t(I) \\]이는 \\(E(x)\\)를 구하는 공식과 같은데, 생각해보면 입력\\(I\\)가 주어졌을 때의 수행 횟수\\(t(I)\\)들의 평균(기대값)을 구한 것이 평균 복잡도이기 때문이다. 평균 수행 횟수는 \\(Pr(I)\\)가 어떻게 정의되느냐에 따라 달라지는데, 각각의 \\(t(I)\\)가 발생할 확률이 모두 동일하다면 간단히 구할 수 있어 별 문제..
피보나치 수
피보나치 수
2018.04.20\\(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...\\) 피보나치 수는 다음 점화식으로 정의된다. \\(F_0 = 0\\)\\(F_1 = 1\\)\\(F_i = F_{i-1} + F_{i-2}\qquad(i \ge 2)\\) 보통 피보나치 수를 구할 때 앞에서부터 두항 씩 더해 구해나갈텐데, 다음 성질을 이용해서 구하는 방법도 있다. 피보나치 수는 황금률 \\(\phi\\)와 그 켤레수 \\(\hat{\phi}\\)와 관련이 있다.\\(\phi\\)와 \\(\hat{\phi}\\)는 다음 방정식의 두 근이다.\\(x^2 = x + 1\\)\\(\phi = {1+\sqrt{5} \over 2} \qquad \quad \hat{\phi} = {1-\sqrt{5} \over 2}\\..
Mergesort
Mergesort
2018.04.17특징 폰 노이만 성님이 개발함. in-place 정렬이 아닌 대표적인 정렬 알고리즘. 정렬된 결과가 저장될 리스트가 1개 더 필요하니까 배열 크기 만큼의 공간 n이 하나 더 있어야 하는 것인데... 잘 짜면 n/2 만큼만 더 사용하도록 할 수도 있음. 외부 정렬도 가능 (메모리에 정렬 대상을 다 올려둘 필요 없이, 디스크에서 일부 가져와서 정렬하고 넣어두고 다시 일부 가져와서 정렬하고 반복하여 전체를 정렬하는 것이 가능함) Mergesort 구현 Top-down 구현 방식과 Bottom-up 구현 방식이 있음. 리스트를 끝까지 분할한 다음, 정렬된 두개의 배열의 맨 앞에서부터 시작하여 index를 하나 씩 증가시키면서 정렬된 1개의 리스트로 merge 하는 것이 아이디어. 이를 Two Pointer 라고..
Quicksort
Quicksort
2018.04.08Quicksort 기본 동작 방식 ko.wikipedia.org/wiki/퀵 정렬 일단 기본적인 동작 방식은 이걸 참고. en.wikipedia.org/wiki/Quicksort 목차를 보면 영문 위키가 더 상세하다. pivot 고르는 법, 다양한 퀵소트 wiki/Sorting_algorithm#Comparison_of_algorithms Worst case : \\(\Theta(n^2)\\) Best case : \\(\Theta(n\lg n)\\) Average case : \\(\Theta(n\lg n)\\)에 근사 대부분의 케이스에 \\(\Theta(n\lg n)\\)로 동작하며 여기에 숨겨진 상수 인자도 매우 작기 때문에 Worst는 \\(\Theta(n^2)\\)이지만 \\(\Theta(n\l..
Primality test
Primality test
2017.11.19Deterministic 순차 탐색 for i in range(3, sqrtN, 2): 에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유 2를 제외한 소수는 홀수이므로 step 2 https://github.com/umbum/leet-hub/tree/main/count-primes 에라토스테네스의 체(sieve_of_eratosthenes)는 \\(n\\)까지의 모든 소수를 찾는 데에는 적합하지만 이를 이용해 \\(n\\)이 소수인지를 판별하고자 하는 경우 메모리 접근 횟수가 크게 늘어나기 때문에 훨씬 느리다. 일반적인 방법은 `` sqrtN``과 `` i``를 둘 다 레지스터에 넣고 `` add reg, 2``해가며 나누고 비교하면 되기 때문에 메모리 접근이 거의 필요 없는 반면,..
재귀, recursion
재귀, recursion
2017.05.31효율을 위해 memoization과 함께 사용하면 좋다. [Languages & Frameworks/JS] - [JS] memoization, currying 재귀 호출은 어떤 문제가 유사한 하위 문제로 나뉘어지며 각각의 문제를 같은 해결 방법으로 처리할 수 있을 때 사용할 수 있다. 일반적으로 하위 문제를 처리하기 위해 자기자신을 호출한다. ``` 전체 - Level 1 - Level 2 - ... - Level n ``` 위와 같은 경우 call stack은 이런 식이다. ... Level2 Level1 전체 주의할 점은 recursive function 내에서 자기 자신을 호출하는 것이 두 번 이상일 경우 각 작업 단위가 순차적으로 증가하지는 않는다는 점이다. 예를 들어 다음과 같이 Level n까..