이 책은 내가 봐온 알고리즘/프로그래밍 관련 책중 단연 손 꼽히는 책. 감동이다 진짜. 구성/내용이 너무 알차다. 강력 추천.
칼럼1~15 로 구성 되어 있고 각 칼럼 마다 연습문제와 해답이 존재한다.
칼럼 1 ~ 5 : 준비
칼럼 6 ~ 10 : 성능
칼럼 11 ~ 15 : 프로덕트
진짜 이 책과 cracking the coding interview 만 잘봐도 인터뷰를 위한 기본 내공을 쌓기에는 충분할 것이라 확신.
칼럼 1 프로그램 디자인
for i = [0, n) : 0부터 n-1까지 반복한다는 의미 '[' 는 open, ')' 는 close
문제 : 한정된 메모리를 활용하여 파일을 읽어들여 정렬 후 다시 디스크에 쓰는 함수 작성하여야 함
입력 : 최대 n개의 양의 정수를 포함하는 파일로, 각 숫자는 n보다 작고, n= 10^7임. 중복 없음. 정수만 존재
출력 : 입력된 정수를 오름차순으로 정렬한 리스트
제약사항 : 메모리 1MB만 사용 가능함. 디스크 공간은 충분, 10초~2분 실행시간 안에 완료 되어야 함
my solution :
레코드 1개당 크기 : 10^7 정수이므로 커봐야 4바이트 integer로 간주, 1MB=1024KB=1000000B 이므로 약 250000개 레코드 메모리에 load 가능. 전체 레코드 갯수 10000000 개 이므로 10000000/250000 = 약 40개의 block으로 나눌 수 있음. 머지소트 또는 비트벡터 문제가 아닐까? 머지소트가 블럭단위로 divide and merge 하는 알고리즘 이므로...입력/출력 파일이 각각 따로 있다는 것, 또는 중간 작업 파일(추가 용량)을 사용할 수 있는지 여부를 사전 질문을 통해 이끌어내면, 문제를 좀 더 수월하게 풀 수 있음. 계속 입력파일에 rewrite한다고 착각하여 문제를 어렵게 접근했음1000000B = 8000000 bit 이므로 최대 8백만개까지 bit set이 가능함. 따라서 이 비트셋을 하나의 해쉬테이블로 활용, 파일 처음부터 8백만개까지 순차적으로 읽어가면서 해당 수가 존재하는 비트를 1로 set.(예를들어 3, 5, 2, 1233232,.. 으로 저장되어있다면 01101......1 이런식으로 정수의 존재 유무를 표시) 최대 2번의 disk access가 필요하다. 8백만개 읽어서 출력 파일에 쓰고, 나머지 2백만개 읽어야 하므로.여기서 핵심은 파일에 저장되어있는 정수 '자체'를 메모리에 load하여 파일에 써야한다는 고정관념에서 벗어나, 정수의 존재유무(정수가 아닌 데이터였으면 문제는 달라졌을 것)만 체크하여 이를 bit로 체크, 파일에 출력시에는 해당 정수를 '생성' 한다는 아이디어에 있다. -> 관련 서적 James L. Adams 가 쓴 Conceptual Blockbusting, 1986 한글판 존재
알고리즘 프로그래밍에서 시간-공간은 서로 트레이드오프인 관계인 경우가 많다. 하지만 사용공간을 줄이면, 시간까지 줄어드는 경우도 자주 있음. 간단한 코드가 복잡한 코드보다 유지보수가 쉽고 더 신뢰할 수 있고, 안전하고 견고하다.(오컴의 면도날)
칼럼 2 정렬
세 가지 문제를 중심으로 정렬/탐색 관련 설명
A. 최대 40억개의 32비트 정수가 랜덤으로 파일에 저장되어 있음. 이 때 포함되어 있지 않은 임의의 정수 하나를 찾는 알고리즘 작성하기.1) 메모리를 넉넉하게 쓸 수 있다면? 2) 메모리는 수백바이트밖에 없고 3~4개의 임시 파일(==디스크 메모리)를 쓸 수 있다면?B. n개의 원소를 가지는 1차원 벡터를 i만큼 왼쪽으로 회전시켜라. 예를 들어 n=8, i=3일 경우 abcdefgh를 왼쪽 회전시키면 defghabc가 된다. 메모리가 수십 바이트 밖에 안되는 상황에서도 O(n)으로 회전이 가능한가?C. 영단어 사전에서 anagram의 집합을 모두 찾아내라(anagram: 동일한 철자로 구성되지만 순서만 다른 단어의 집합) 예를들어 pots, stop, tops는 모두 anagram이다.
A solution:최대 40억개의 숫자는 모두 32bit 10101010010101010101 으로 구성되어있고, 맨 오른쪽 bit 부터 차례로 0/1 로 나뉘어 두 개의 sub file에 저장하면서, 파일에 저장된 정수의 갯수가 2의 제곱수가 아닌 경우, 반드시 빠진 정수가 존재하므로 계속해서 그쪽으로 deep down해서 찾아 나가면 n + n/2 + n/4 ... = 최악의 경우 O(n) 에 빠진 정수를 찾을 수 있다.어떻게 하면 이러한 솔루션을 생각해 낼 수 있을까? -> 어떤 수가 포함되어 있는지를 찾는 것과 포함되어있지 않는 수를 찾는 것은 서로 다르다. 포함되어있는 수를 찾는 알고리즘은 해당 수가 메모리에 저장되어있는지를 확인해야하므로 전수검사가 필요하다(no 정렬인 경우) 하지만 포함되어있지 않은 '어떤' 수를 찾는 것은 '추정' 을 통해 파악이 가능하다. 해당 배열의 최소-최대 범위를 알고 원소의 갯수를 알면 있어야 할 수가 없는지 여부를(2비트짜리 정수 2개가 있는 파일에서 전체 4비트 정수중 파일존재 하지않는 정수 1개를 찾는 알고리즘의 경우, 2^2= 4개의 수가 존재해야 하는데 2개만 존재하므로 2개가 빈다는 것을 당연히 알 수 있다). 따라서 남은 것은 전체 배열 또는 파일을 binary로 쪼개가며(선험적으로 binary로 쪼개는게 가장 효율적인 것임을 알고있으므로) sub file의 최소-최대범위(2^32-> 2^16 -> 2^8 .. 개)와 실제 정수 갯수를 비교, 어느 쪽 파일이 정수 갯수가 부족한지 알 수 있다(양팔 저울로 벌레먹은 사과의 무게를 추정하여 범위를 좁혀나가는 것과 비슷)남은 것은 어떠한 기준으로 파일을 binary로 쪼개는 것인데, '비트' 는 0/1 2개만 존재하므로 오른쪽 끝 비트부터 0을 가지고있는 정수와 1을 가지고 있는 정수로 파일을 쪼개어 가야한다는 것을 아는 것이 핵심.예를 들어 4비트 정수 8개가 파일에 저장되어있고, 포함되어있지 않는 정수 1개를 찾아야할 경우, 오른쪽 끝 비트가 0인 정수 집합과 1인 정수 집합으로 쪼개었을때 각각 3개 5개로 쪼개졌다고 가정하면, 원래 2^4개-> 2^3개 로 8개가 존재해야하는데 3개 5개이므로 양쪽다 빠진 정수가 존재함을 알 수 있다. 따라서 가능한 갯수가 작은 파일로 계속 deep down 하다보면 빠진 정수를 찾을 수 있다.B solution:처음에 단순히 맨 왼쪽 원소를 맨 오른쪽에 붙이고 한칸씩 << shift 하는 알고리즘을 생각했으나, 시간 복잡도가 O(n^2)이므로 좋지 않은 방법이다. extra memory를 이용하면 O(n)에도 간단히 구현가능하나, extra memory 사용이 없는 아름다운 솔루션을 생각해보면,처음에 shift할 length 'i'를 알고있다는 것이 힌트이다. 맨 처음 문자를 예를들면 끝에서 i번째 문자와 치환하고 치환된 문자는 현재 자리에서 i번째 앞의 문자와 다시 치환한다. 이를 반복하면 된다. 예를들어 abcde 이고 i가 2일때,abcde->xbcae, d(x는 비어있는 메모리 공간, 치환된 d는 따로 변수에 저장 중)->xdcae, b-> xdcab,e -> xdeab, c->cdeab 완성시간복잡도 O(n), 공간복잡도O(1)에 shift가 완성됨을 알 수 있다.핵심은 미리 shift할 length를 알고있다는 점, in-place algorithm을 위해서 i번째 이후 문자열이 저장된 공간을 활용한다는 아이디어를 떠올리는 것이다.또 다른 방법은 reverse함수를 통해 구현 가능하다. 예를 들어 abcdefgh를 왼쪽으로 3만큼 회전시키려면
reverse(0, i-1) // cbadefghreverse(i,n-1) // cbahgfedreverse(0, n-1) // defghabc위와 같이 구현 가능하다
칼럼 3 데이터 구조C. solution:예를 들어 23만개의 단어가 있는 사전을 대상으로 모든 anagram 쌍을 출력하는 함수를 생각해보면, 1) sorting? 2)모든 순열찾기 3) extra memory 를 사용, 해쉬 테이블을 이용해서 순회하면 O(n^2)에 파악 가능하다.책 해답: 3단계로 구분한다. 1) 단어마다 marking을 하고(매 단어를 알파벳순으로 정렬) 2) marker를 알파벳순으로 정렬 3) 같은 marker 끼리 squash(1개로 합치기) 과정을 통해 anagram을 검출해낸다. O(kn); k는 평균 단어 길이 + O(nlogn); qsort 사용 + O(n) = 최종 시간 복잡도는 O(nlogn) 이다.
데이터와 데이터를 어떻게 다루느냐에 따라서 코드의 구조가 결정된다. 예제를 통해서 데이터를 다루는 예와(테이블을 다룰때 각각의 변수에 모두 저장하는 방법 vs 배열에 깔끔하게 처리해서 코드 라인수를 10배이상 줄이는 경우) 를 보여준다.
코드라인수가 줄어들면=>유지보수가 쉽고=>잠재적인 버그가 77ㅕ7777ㅕㅕㅕㅕㅕㅕㅕㅕㅓㅕㅓ줄어들고=>가독성이 높아진다. 같은 기능을 하는 코드라면 코드라인이 짧고 간결한 것이 낫다. 물론 가독성vs간결함의 줄다리기를 현명하게 하는 것이 실력.
데이터 자료구조만 바꾸어도 필요한 코드 구조 및 라인수가 확 줄어들 수도 있다. 코드자체+데이터 자료구조 통합설계의 중요성 강조.
"데이터의 표현이 프로그래밍의 본질이다"
칼럼 4 프로그램 검증 by loop invarient, assert(단정문)
binary search를 예시로, loop invarient를 어떻게 활용하여 작성한 알고리즘이 유효한지 보여준다. 불변식을 정확하게 기술하고, 코드를 한 줄씩 따라가며 불변식이 유지되는지 검증을 통해 정확성을 확인할 수 있다.(100%는 아님)
루프의 정확성을 증명하려면, 세가지 속성을 입증해야한다. 1)보존, 2)초기화, 3) 종료 1,2,3 동안에 불변식이 유지됨을 보이면 그 루프는 정확하다고 확신할 수 있다.
함수의 정확성을 증명하려면, precondition, postcondition으로 으로 검증가능함.
"항상 코드를 이해하려하고 동작할때까지 단지 고치기만 하고 싶은 좋지 못한 충동을 이겨내야 한다"
칼럼 5 프로그래밍에서의 사소한 문제
다 작성된 프로그램(알고리즘)을 테스트하기위해서, 스캐폴딩(가 건축물, 완성된 함수에 테스트 케이스를 input으로 제공하는 wrapper 같은 개념)을 활용하는 것이 영리한 방법.
칼럼 6 퍼포먼스
컴퓨터 시스템은 다음과 같이 상위 수준 디자인 부터 하위 수준 디자인 레벨까지 다양한 레이어에서 정의된다.
문제정의(문제를 어떻게 정의하느냐에 따라서 프로그램은 몇배로 복잡해질수도, 빨라 질수도 있다) - 시스템 구조(전체 1개의 큰 모듈로 디자인 할것이냐, 분산된 여러개의 모듈로 나누어 문제를 해결할 것이냐 등 시스템 구조 디자인에 따라 효율성이 달라질 수 있다) - 알고리즘과 데이터 구조(시간 복잡도에 기반한 알고리즘 성능 개선 사용하기) - 코드 튜닝(ex 가장 많은 시간이 드는 함수하나를 low level assembly로 바꾼다던지) - 시스템 소프트웨어(때로는 프로그램자체보다 프로그램이 동작하는 시스템 소프트웨어, 데이터베이스 시스템을 바꾸는것이 도움이 될수도있다) - 하드웨어(하드웨어 개선은 당연히 속도개선을 불러온다. 또는 소프트웨어 아키텍쳐에 따른 적절한 하드웨어 선택이 중요하다)
칼럼7 간단한 주먹구구식 계산으로 시스템에 걸리는 부하 및 알고리즘 퍼포먼스 추정해보기
struct node { int i; struct node *p; }; 이러한 노드 200만개를 128MB 메모리를 가지는 컴퓨터에 저장할 수 있는지 추정 해보기
일반적으로 128MB 메모리중 OS 및 app에 사용되는 메모리는 제하면 보통 70%정도의 가용 메모리가 있다고 가정 즉 81MB 정도 사용 가능함.
int 형 4바이트+ node 포인터 4바이트 해서 1노드당 크기 8바이트인데, 여기에서 노드당 오버헤드가 얼마나 들것인지(언어에서 메모리 집합을 할당/유지 하기위한 추가 비용)를 제대로 추정해 내는 것이 핵심. 책에서는 연속된 포인터들 간의 차이를 계산하여 이 차이가 레코드의 크기라고 추정하여 계산.
컬럼 8 알고리즘 디자인 기법
부동소수점으로 이루어진 벡터(ex: -1, 2, 3,4,5,-6,0)에 대해 연속된 sub array중에 largest sum을 계산하여 출력하는 문제를 가지고 O(n^2), O(nlogn), O(n) 으로 알고리즘 디자인하는 과정을 설명.
O(n^2) 솔루션은 간단하게 모든 원소를 다 순회하면서, 해당 원소에서부터 끝까지 모든 subarray 를 max 함수를 이용하여 비교하는 단순한 방법.
배열 순회에 관한 문제는 종종 x[0...i-1]에 대한 답을 어떻게 x[0...i]에 대한 답으로 확장할 수 있을까? 라는 물음에 의해 풀린다.
위 문제의 경우, O(n) 솔루션이 존재하는데, 0..i-1에서 끝나는 최대 벡터의 합을 한 변수에 저장하고, i가 양수라면 최대 백터의 합에 x[i]를 더한다. x[i]가 음수라면 ..i-1까지의 합이 최대이므로 더할 필요 없다. i+1이 양수라면 i-1까지의 합 max와 max+x[i]+x[i+1]를 비교해서 큰쪽에 저장한다.
정리하면 알고리즘의 복잡도를 줄이기 위한 기법으로 이 챕터에서는 아래 4가지 기법을 다루고 있다.
1) 재계산을 피하기 위한 상태 저장
2) 정보를 사전처리하여 데이터 구조에 보관
3) 나누어 푸는 알고리즘(divide and conqure)
4) 스캐닝 알고리즘(x[0...i-1]에 대한 답을 x[i]로 확장하기)
컬럼 9 코드 튜닝
문제1 - 정수에 대한 나머지 연산
k = (j+rotdist) % n; 에서 % 연산자는 매우 비용이 많이 드는 연산이므로 % 연산자를 활용하지 않도록 아래와 같이 코드 튜닝 가능
k = j+rotdist;
if( k>= n) k -= n;
실제로 실행시간을 측정한 결과, rotdist==1 인 경우 119ns -> 57ns로 줄어듬. 하지만 rotdist==10 인 경우, 동일하게 206 ns가 걸림. 왜냐하면 rotdist==1인 경우는 알고리즘이 메모리를 순차적으로 접근하게 되고 나머지 연산자가 전체 실행시간을 결정. 하지만 rotdist == 10인 경우는 메모리의 매 10번째 워드에 접근하게 되므로 RAM에서 캐시로 데이터를 가져오는 시간이 중요하게 된다.(아직 이해안됨)
문제2 - 함수, 매크로, 인라인 코드
max함수를 #define max(a,b) ((a) > (b) ? (a) : (b)) 으로 바꾸려 한다면 오히려 가독성이 떨어질 뿐 아니라 오히려 속도가 떨어질 수도 있다. 8.4에서 largest sum 문제의 경우는 속도가 빨라지지만, 8.3에서 매크로를 사용했을때 오히려 속도가 떨어졌다. 왜냐하면 매크로의 이름에 의한 호출(call-by-name) 시멘틱스로 인해 알고리즘3이 자신을 재귀적으로 두 번 이상 호출하게 되어 결국 실행시간이 더 빠르게 증가함.(이해안됨)
문제3 - 순차 탐색
정렬되어있지 않은 테이블 순차탐색의 경우,
int ssearch1(t) {
for i = [0, n)
if( x[i] == t) return i;
return -1
} 에서 for loop에서는 매번 i가 [0,n) 범위에 포함되는지 체크하는 연산이 있다. 이를 아래처럼 없애면
int ssearch2(t)
hold = x[n]
x[n] = t
for(i=0 ; ; i++) //무한 루프이므로 i범위 체크안함.
if x[i] == t break;
x[n] = hold
if i == n return -1
else return i
i를 매번 체크하는 시간을 좀 더 줄일 수 있다(다만 좋은 코드는 아님. 만약 t가 범위에 없을 경우 무한루프)
마지막으로 아래처럼 loop unrolling(loop 내용을 펼치기)을 이용하면 아름답진 않지만 실행시간 감소를 기대할 수 있다.
int ssearch3(t)
x[n] = t
for(i=0; ; i+=8)
if(x[i] == t) break;
if(x[i+1] == t) i+=1; break;
if(x[i+2] == t) i+=2; break;
...
if(x[i+7] == t) i+=7; break;
if i == n return -1;
else return i;
loop unrolling은 파이프라인 지연을 피하게하고, 분기를 감소시키고, 명령어 수준의 병렬처리가 증가하도록 도와준다.
파이프라인 지연이란, 파이프라인에서 다음 명령어가 조건부(if)일때 그 결과가 다음 명령어의 실행여부에 영향을 미치기 떄문제 파이프라인 과정에서 명령어가 조건부일 경우는 파이프라인 흐름을 지연시켜 if 실행후의 결과를 실행한 후 그 다음 명령어를 실행하는 것을 말한다.
문제4 - 구면체 위의 거리 계산(데이터 format 변경)
구면체 위의 거리계산시, 좌표계를 위도경도 -> 카테시안(x,y) 좌표로 변경하기만해도 연산 시간을 줄일 수 있다.
이진 탐색 4단계 코드 튜닝
1960년대 처음 발표된 이후 수정을 거쳐, 현재 많이 알려진 이진탐색의 코드는 완벽하다, 하지만 튜닝을 통해 상황에따라 좀 더 속도를 개선할 수 있다.
l=0;컬럼 10 메모리 절약
u=n-1;
loop
/* invarient: if t is present, it is in x[l...u] */
if(l>u) p = -1; break;
m = (l+u)/2;
case
x[m] < t: l=m+1;
x[m] > t: u = m-1;x[m] == t: p = m; break;일반적인 이진탐색의 코드는 위와 같다. 이제 불변식 x[l]<t<x[u]와 l<u의 관계를 이용하여 이를 튜닝하면l= -1; u=n;while l+1 != u/* invarient: x[l] < t && x[u] >= t && l<u */m = (l+u)/2;if(x[m]<t) l=melse u=m/* assert l+1 = u && x[l] < t && x[u] >= t */p=uif(p>=n || x[p] !=t) p= -1; (어떻게 해서 이렇게 유도되었는지 이해 안됨)이 코드는 if 문 비교를 3회에서 1회로 줄였기 때문에 장기적으로 보면 시간 이득이다.또한 n의 길이를 미리 알고(아래서는 n==1000이라 가정) 범위를 upper, lower로 표기하는 대신에 l+i=u로 표기하고 i가 항상 2의 거듭제곱수가 되도록 보장하는 방식으로 튜닝하면i = 512;l = -1;if(x[511] < t) l=1000-512;while i != 1/* invarient: x[l] < t && x[l+i] >= t && i = 2^j */nexti = i/2;if(x[l+nexti] < t)l = l+nexti;i=nexti;elsei=nexti;/* assert i=1 && x[l] < t && x[l+i] >= t */p=l+1;if( p>1000 || x[p] != t) p=-1;
데이터를 메모리에 저장할때, 2차원 행렬을 많이 사용한다. 하지만 저장된 데이터의 분포가 흩어져있어, 행렬의 일부부분에 데이터가 집중되고, 나머지 메모리가 낭비되고 있다면 sparse data structure를 활용하여 이를 절약 가능하다. Linked list와 각 linked list의 head를 가리키는 포인터들의 배열하나로 이를 구현 가능하다.
데이터압축 - c가 십진수 정수일때, c=10Xa+b로 표기가능하고 두 십진수 a와b를 1바이트로 부호화하면 메모리 절약 가능
코드 공간 압축- 1970년대에는 코드자체가 저장되는 메모리조차 부족한 경우가 많았으므로 코드를 배열에 부호화하여 저장하고, 필요할때 이에 접근하여 실행하는 기법도 사용하였다(p204)
※프로그램 소스의 각 라인이 얼마나 많은 메모리를(만약에)살펴볼 일이 있으면, 컴파일러의 linker의 출력과 소스파일을 연결하여 소스의 각 행이 얼마나 많은 메모리를 소모하였는지를 확인가능(어떤 매크로들은 수백 줄의 코드로 확장되는 경우도 존재)하고 이를 이용하여 목적코드의 크기를 줄일 수 있다. 유용성을 떠나 이러한 지식들은 컴파일러 등 컴퓨터공학 기초 지식이 튼튼해야 알 수 있는 참 지식.
컬럼 11 정렬
삽입정렬(insertion sort)를 예제로, 정렬 프로그램의 속도를 개선하는 과정을 보인다.
for i= [0,n)
for(j=i; j>0 && x[j-1] > x[j] ; j--)
swap(x[j-1], x[j]);
이 코드에서 모든 j를 shift 하기위해 swap 할 필요는 없다. 아래 코드같이 변경할 경우 약 3배 빠르게 동작한다.
for i= [0,n)
t = x[i];
for(j=i; j>0 && x[j-1] > t ; j--)
x[j] = x[j-1];
x[j] = t
중략
컬럼 12 표본 선정 문제
m개의 0~n-1 범위내의 랜덤한 정수를 출력하는 함수를 작성해보자. 중복되는 정수는 없어야하고, 정렬된 정수리스트를 리턴해야한다. 큰 정수를 랜덤하게 리턴하는 bigrand()와 범위 i..j내에서 정수 1개를 랜덤하게 리턴하는 함수 randint(i,j)가 있다고 가정하라. 모든 가능한 정수 리스트는 선택될 확률이 동일하다.
첫번째 풀이:
select = m
remaining = n
for i= [0,n)
if(bigrand() %remaining < select) // n보다 작은 정수를 오름차순으로 정렬해서 출력
print i
select--
remaining--
for의 i를 순차적으로 출력하므로 출력되는 정수는 오름차순으로, 중복되지않고 정렬되었음을 보장
또한 random하게 0~remaining 범위내의 정수를 출력하기위해 bigrand()%n 을 이용하였고
< select를 이용하여 m개의 정수만이 리턴되도록 하였다.
두번째 풀이:
knuth의 답(알고리즘은 위와같고, 코드량 줄임) :
void genknuth(int m, int n) {
for(int i=0; i<n; i++) {
if(bigrand() % (n-i)) < m) {
cout<<i<<"\n";
m--;
}
}
}
또한 set(자동 중복 제거)을 이용하여 간단하게 구현 가능하다
void getsets(int m, int n) {
set<int> S;
while(S.size() < m)
S.insert(bigrand() % n);
set<int>::iterator i;
for(i= S.begin(); i != S.end() ; ++i)
cout<< *i <<"\n";
}
STL 명세에 따르면 set insert는 logm 내에, 조회는 m(해쉬를 사용한다면 1)에 가능하므로 전체 시간복잡도는 O(mlogm)이다.
세번째 풀이:
또한 1부터 n까지의 정수를 뒤섞은 다음에 처음부터 m개까지의 정수를 선택하는 방법도 있다.
발견된 문제를 충분히 이해하라
추상적인 문제를 구체화 하라
디자인 공간을 탐구하라
한 솔루션을 구현하라
회고하라
컬럼 13 탐색
n개의 최대값 m을 가지는 정수 집합에 대해서 insert/print을 array/list/BST/bitvec/bins 5가지 자료구조를 가지고 구현하고, 각각의 장단점 및 속도를 비교한다. bin은 일종의 radix sort에 사용되는 자료구조인데 범위가 0~99이고 bin 갯수가 4 라면 0~24까지 첫번째 bin, 25~49 까지 두번째 bin 이런식으로 저장 가능함. bin을 이용할떄 정수t를 몇번째 bin에 저장할 것인지가 중요한데, t*binnumber/maxval 과 같은 코드는 자칫 오버플로우를 발생시킬 수 있으므로 대신에, t/(1+maxval/bins) 를 이용
일반적인 경우 가장 최악의 경우에도 성능을 보장하는 STL을 많이쓰나, 특수한 목적의 경우 STL보다 최적화된 알고리즘을 직접 구현하는것이 더 빠를 수 있다.
사용된 기법 :
1) sentinal(보초병) 삽입하여 max value를 언제나 넘지 않도록 유지
2) 재귀함수 제거
3) 메모리 동적 할당 대신에 생성자에서 미리 m개를 선언 후 나누어주기
컬럼 14 힙
힙(heap)은 정렬을 하는데 최대 O(nlogn)을 보장하고, 추가적인 메모리 사용량도 적다. 또한 우선순위 큐(각 오퍼레이션은 O(logn))를 구현하는데에도 적절하다. 정렬 가능한 집합이면 어떤 것이든 힙에 저장 가능함. 예를 들어 이진트리는 1) 정렬가능한 순서가 있고(모든 노드는 자식보다 작거나 같다) 2) 모양 속성이 삼각형(??) 이기 때문에 힙의 한 부분집합이라 볼 수 있다.
힙의 정의 heap(l,u) : 2l <= i <= u x[i/2] <= x[i]
x[1...n-1]이 힙일때 x[n]에 임의의 값이 들어와 힙구조가 깨졌을 때, 이를 복구시키는 siftup 함수의 구현 절차는 아래와 같다
부모를 거꾸로 타고올라가면서, 부모보다 작을때까지 shift up->오른쪽 child node/부모로 값 저장. O(logn) 보장.반복문 불변식 : heap(1,n) except between i and its parent(i와 부모 사이를 제외한 모든 곳에서 힙 속성을 만족한다)따라서 i==1 일 경우, root이므로 부모가 존재하지 않으므로 종료, parent의 index는 x[i/2] 이므로 i가 부모를 가지고 있다면 p=i/2를 대입하여 p를 부모 인덱스로 만들고 x[p]<=x[i]이면 불변식이 성립하므로 루프가 종료되고, 그렇지 않다면 swap(x[i] x[p])를 실행하고 i=p를 대입하여 루프를 계속 실행한다.void siftup(n)pre n>0 && heap(1,n-1)post heap(1,n)i=nloop/* invarient: heap(1,n) except between i and its parent */if i == 1breakp=i/2if x[p] <= x[i]
break
swap(x[p], x[i])
i = p
shift down을 구현할때에도 비슷하다.
반복문 불변식: heap(1,n) except between i and its (0,1,2) children(i와 자식들 사이를 제외하고 모든 구간; 0~i and i+2~n 에
서 heap 성립)
heap으로 이용하여 우선순위 큐를 구현할 수도 있다. P289 참조.
컬럼 15 문자열
사전에서 가장 긴 반복 단어를 어떻게 효율적으로 찾을 수 있을까? -> set/map을 사용할 수도 있고 좀 더 속도/공간을 최적화 하기 위해서는 직접 hash_table을 구현하고 value로 단어, 단어에 대한 포인터, 카운터, next 포인터를 포함하는 node를 정의하여 구현하면 훨씬 더 빠른 퍼포먼스를 낼 수 있다.
단어에서 좀 더 확정하여, 어구를 이루는 가장 긴 문자열을 검출하려먄 어떻게 해야할까? -> suffix array(접미사 배열) 이라는 자료구조를 사용하면 nlogn만에 검출이 가능하다. 접미사 배열이란 각 단어를 가리키는 char* pointer 들의 집합으로, 추가적으로 n 만큼의 메모리를 사용하여 접미사 배열을 생성한 후, quick sort 를 이용하여 정렬 후에 배열을 읽어나가면서 가장 많이 반복되는 문자열을 찾는다,
'Books' 카테고리의 다른 글
| 웹을 지탱하는 기술 - 야마모토 요헤이 (0) | 2014.08.01 |
|---|