Programming Pearls/Column1

������ 내������ ������를 ���떻게 ��� 것���가?

대부����� ���������는 ������가 ���미 구���되��� ���다. 그런데 꼭 ���로��� 나만��� ������를 만들������ 될때가 ���다. �����드가 ��� ���만개��� 된다고 ������.���것��� ���리가 ���고 ���는 ��블������, ��������� 같��� 것���로 ���기���는 메모리가 많��� 든다. 32bit(4byte)��� ������라고 ���다면, 40메가바������가 ���������다. ������만 ���떤 ��������� ���때���, ���리가 ��������� ���당��� ��� ���는 공����� 1메가 남������라고 가���������. �������� 많��� ���려����� ���된다. ���떻게 ������ ��� 것���가? ��� �����드들��� 7���리 ��������������기 때문��� 같��� 것��� ���다고 ���다.

• ���력 : 많��� 봐��� n개��� ������. 각각��� n��� ���만보다 ���다. 똑같��� ������가 두�������� 나���면 ���된다. 그 ������랑 관련된 데������가 ���다.
  
• ���력 : ��������������로 ���렬된 ������들
  
• ������ : 메모리를 1메가 �����밖��� ��������� ��� ������. 디������ 공�� ���������. �������������� �������� ������면 ���됨. 10��� �����면 괜������.
  
  

������는 머��� ������를 ������는데 ��렸다. 다른 방법���로는, 각각��� ������를 4byte로 ���������면 ������ 메모리��� 250,000개를 담��� ��� ���다. 250000개를 ���������고, 또 250,000개 ���고... ������ 40�� ���는 ���다. 머��� ������는 ����� ������ ������������ ���������가 ������ ������나고, 두����� 방법��� ���력��� 40����� �������� ���다는게 문���다. ���것 두가������ ��������� ��� ������������ ���력��� �����, ����� ������ ��������� ���게는 ��� ��� ������까?

�����맵, ������ ����� 벡���라 ��리���는 방법��� ���������듯 ���다. ���를 들��� 맥����� 10미만��� ������라 ���때���, {1,2,3,5,8}��� ��������� 보면, (0 1 1 1 0 1 0 0 1 1)��� 된다. ������면 1, ������면 0��� 것���다. ��� ������당 1�����만 ���당��� ������, 그것��� ��������로 ���리를 ���는 것���다. ����������� 말���듯���, 미����과 맥�������� �����가 ���고, 같��� ������가 ������며, 관련된 데������가 ���다는 ���면������ ��� 방법��� ��� ��� ���는 것���다. 대강��� ���드는 다���과 같다.

~cpp 
# 배���값 0���로 ������
for b in bits:
	b=0
# ������면 1
for e in inputFile:
	bits[e]=1
# 1���것만 ���력
for b in bits:
	if b==1:
		print b

���것��� �������������� Θ(n)���다. ��� ������는 문���를 ������ 깊게 ��������다 보면, 가끔 ������난 ���득��� 가���다 ���때가 ���다는 교������ ���고 ���다. 문��� ������는 문��� ��������� 90���로다. ���반������로 많��� 공����� ���������면 ������ �������� ������된다고 ���다. 그런데 �����맵 ������는 ������� ���고, 공���� ������들���따. ������ 데������를 다루는 것���, 그것��� ���������는 데��� 더 ������ �������� 든다는 것���다. 그리고 데������를 디��������� 두기 보다는 메모리 ������ 두는 것��� 디������ ��������� 같��� ����� ���리는 ������ ������ ���가 ���는 것���다. ���로그램��� ��단���게 ������. ������보����� ���고, 견고��� 것���다.

ProgrammingPearls