algorithm9 정렬: heap(priority queue) 좌우 트리가 균형적일 경우에는 배열로 표현하는 것이 유리합니다. 장점 - 리스트로 구현할 때 소비되는 연결 포인터에 대한 메모리 공간을 절약할 수 있고 포인터 연산에 필요한 메모리 접근을 수식 연산으로 대체합니다. 메모리 접근 비용보다 수식 연산이 빠릅니다. 단점 - 배열 크기를 사전에 결정하여 할당해야 하기 때문에 구현 시 배열 크기가 가늠이 되지 않을 경우에는 사용이 어렵고 사전에 결정이 가능하다고 하더라도 시작부터 전체 메모리를 할당하고 시작해야 하기 때문에 메모리를 효율적으로 사용하기 어렵습니다. 왼쪽 자식 인덱스 (2 x 부모 인덱스) + 1 오른쪽 자식 인덱스 왼쪽 자식 인덱스 + 1 부모 인덱스 (자식 인덱스 - 1) / 2 heap 힙은 완전 이진 트리를 이용하여 힙에 값을 넣을 때나 뽑을.. 2022. 7. 3. 정렬: radix sort counting sort는 전체 원소의 최대값 만큼 counting table을 할당 해서 처리해야 하므로 원소 값들의 차이가 클 때는 불리한 면이 보입니다. 그래서 counting sort 같이 각 원소들의 우선 순위를 비교하지 않는 방법이면서 어떤 묶음 단위로 계층적으로 처리하면 이에 대한 단점을 보완할 수 있기 때문에 radix sort를 사용합니다. radix는 base라고도 하며 2진법, 10진법, 16진법 같은 개념입니다. 그런데 꼭 radix sort는 기존 몇 진법에 따라서만 사용하는 것이 아니라 필요에 따라 1000진법 같은 효율적은 묶음 단위 방법으로 사용해도 좋을 것 같습니다. 10진수로 고정하여 C/C++로 아래와 같이 구현해 보았습니다. #define _CRT_SECURE_NO_W.. 2022. 7. 3. 정렬: counting sort 정렬될 결과에서 배치될 순서를 기준으로 정렬하는 방법으로 해당 항목값이 몇 개씩 있는지 세는 방법으로 정렬하는 방식을 counting sort라고 합니다. counting table만 구해서 그 counting 값을 기준으로 원소 값들을 재 배치하면 단순 하겠지만 다음 radix sort에서도 동일 원리를 사용하여 구현하는 것이 용이하기 때문에 누적 counting 값을 기준으로 원소들을 재 배치 합니다. C/C++로 구현하면 아래와 같습니다. void counting_sort(int *data, int len) { int table_max = max(data, len) + 1; int *counting_table = new int[table_max]; int *sorted_data = new int[l.. 2022. 6. 20. 정렬 1. 각 항목간 비교하여 정렬하는 방법 선택, 삽입, 버블 정렬들은 worst O(n^2) 이므로 일반적으로 사용이 쉽지 않다고 생각됩니다. 분할 정복 기법을 추가하여 정렬하는 합병 정렬과 quick 정렬은 O(nlog n) 이지만 quick 정렬은 피벗을 잘 못 선택하면 worst O(n^2)이기 때문에 주의해서 사용해야 하고 합병 정렬은 최소 정렬할 자료의 크기 만큼 저장소가 추가로 필요하고 recursive로 구현할 때 stack 넘침의 위험성이 있습니다. 그래서 가장 용이하게 시도할 수 있는 방법으로 우선 순위 queue를 구현하는 방법인 heap 정렬을 생각해 볼 수 있을 것 같습니다. 2. 정렬될 결과에서 배치될 순서를 기준으로 정렬하는 방법 각 항목을 서로 비교하여 정렬하는 방법들은 O(nl.. 2022. 6. 19. 의사 난수 생성기 - 4. 메르센 트위스터(Mersenne Twister) 1997에 Makoto Matsumoto와 Takuji Nishimura가 개발하여 현대에 보편적으로 사용하는 PRNG (의사 난수 생성기)로 R 이나 Ruby, Pascal, PHP, Python, GLib, C++ Boost등의 기본 난수 생성기 알고리즘으로 사용되고 있습니다. 그 이름의 유래는 난수 생성 주기가 Mersenne prime 수인 2^19937 - 1 개의 주기 길이에서 만들어졌습니다. 기본 구현인 MT19937은 32 비트로 구현 되었으며 64 비트로 구현된 것은 MT19937-64로 호칭합니다. 624개의 정수(seed 포함)를 짝지어서 623차원의 하이큐브에 해당하는 좌표에 점을 찍어서 일관성을 발견할 수 없을 만큼 분포가 좋습니다. 필요한 버퍼 크기는 일반적으로 2.5KiB로 크.. 2022. 5. 2. 의사 난수 생성 - 1. Middle-square method 1949년 폰 노이만에 의해서 고안된 의사 난수 생성 방법으로 애니악에서 사용되었다고 합니다. 최초값 seed를 제곱한 후에 중앙에서 seed와 동일한 자리수를 추출하는 방법입니다. 예를 들어 seed 값이 117이라고 했을 때 117 * 117 = 13689 이고 중앙에서 3자리를 뽑아 내면 368이 됩니다. 다음에도 368을 seed로 하여 동일한 방법을 반복 합니다. 그런데 이를 계속 반복해 보면 117 368 360 960 160 560 360 금새 같은 값을 가지게 되었습니다. 그리고 많은 seed 값들이 0으로 수렴하게 됩니다. 따라서 현재는 간단한 의사 난수 생성기로 LCG를 사용합니다. 전체적인 의사 난수 생성기의 역사적인 흐름은 아래 링크를 참고 하였습니다. 메르센 트위스터 이후로는 새로.. 2022. 5. 2. 의사 난수 생성 - 2. LCG (Linear Congruential Generator) 선형 합동 생성기 라고 직역 할 수 있겠습니다. C 언어의 rand() 함수 구현과 Java.util.Random에 사용되었습니다. 가장 잘 알려진 간단한 의사 난수 생성 방법 중의 하나로, 1958년에 만들어 졌으며 재귀적으로 아래와 같은 점화식으로 정의 됩니다. 1) m > 0 2) 0 16) % 0x8000; } 참고: https://en.m.wikipedia.org/wiki/Linear_congruential_generator Linear congruential generator - Wikipedia The other widely used primitive for obtaining long-period pseudorandom sequences is t.. 2022. 5. 2. 의사 난수 생성 - 3. LFSR (Linear Feedback Shift Register) PS (Problem Solving) 문제의 입력 데이터 생성을 위해서 재현 가능한 난수가 필요 합니다. 어찌보면 "재현 가능하다"와 "난수"라는 개념이 상반되지만 암호학에서 pseudo-noise sequence, 통신에서 whitening sequence 등이 필요한 곳에서 사용하는 방법으로 실제 상황과 유사하게 임의의 데이터를 발생 시켜서 입력 해야 하지만 분석을 위해서 재현 가능한 패턴이 필요한 것이죠. 사용되는 선형 함수를 잘 선택하면 주기가 길고 무작위적인 실제와 매우 유사한 입력 데이터를 생성할 수 있다고 합니다. 이를 의사 난수 생성(Pseudo Random Number Generation: PRNG)이라고 합니다. 이 때 사용되는 것 중에서 한가지 방법이 1965년에 만들어진 LFSR 이.. 2022. 5. 1. 기본 알고리즘 목록 기본 풀이법 전개 # 되돌아가기 (back-tracking) 되돌아간 지점까지는 같은 행보를 한 후보 중에서 종전의 후보와 관련이 있는 후보를 선택한다. # 나눠풀어 합치기 (divide-and-conquer) 문제를 작은 크기로 쪼개고 그렇게 푼 결과들을 합쳐서 전체 문제의 답으로 만든다. # 기억하며 풀기 (dynamic programming) 문제의 일부분에 대해서 풀고 기억한다. 문제의 다른 부분을 풀 때 기억한 부분의 답을 활용한다. # 질러놓고 다듬기 (iterative improvement) 한개의 답 후보를 임의로 선택하고 다듬으면서 답에 근접해 간다. #1 스택 Memoization DP (Dynamic Programming) DFS (Depth First Search) Back Trac.. 2022. 1. 25. 이전 1 다음
