조환희의 학습 블로그

해시 테이블 해시 테이블¶ 해시 테이블이 어떻게 작동하고, 왜 성능이 그렇게 좋은지를 알아보기 위해 간단한 맵 구현부터 시작해서 해시 테이블가지 차차 진행해 보도록 한다. 나는 파이썬으로 일일이 구현해서 설명하지만, 실생활에서는 코드를 이렇게 쓰지 않는다. 그냥 사전을 사용하면 된다! 따라서 이 장의 나머지 부분에서 여러분은, 사전이라는 것이 존재하지 않으며 키를 값에 매핑하는 자료형을 구현하려고 한다고 상상하면 되겠다. 여러분이 구현해야 할 연산은 다음과 같다. add(k, v): 키 k에서 값 v를 매핑하는 새 항목을 추가한다. 파이썬 사전 d에서 이러한 연산은 d[k] = v라고 쓴다. get(target): 키인 target에 대응하는 값을 검색해서 반환한다. 파이썬 사전 d에서 이러한 연산은 d..

검색 알고리즘 분석 검색 알고리즘 분석¶ 검색은 어떤 집합과 목표 대상을 받아 그 대상이 해당 집합에 들어있는지를 판별하고 때론 대상의 인덱스를 반환해 주는 알고리즘이다. 가장 단순한 검색 알고리즘은 '선형검색'으로, 집합의 항목들을 순서대로 지나가다가 대상을 찾으면 멈춘다. 최악의 경우 집합을 끝까지 지나야 하는 경우도 있으므로 실행시간이 선형이다. 시퀀스에 사용하는 in 연산자는 선형검색을 사용한다. find나 count 같은 문자열 메소드도 마찬가지다. 만약 시퀀스에 들어있는 원소들이 순서대로 되어있다면, O(log n)인 이분검색을 사용할 수 있다. 이분검색은 여러분이 사전에서(자료형이 아닌 실제 종이사전) 단어를 찾고 싶을 때 쓰는 알고리즘과 굉장히 유사하다. 맨 앞에서 시작해서 순서대로 모든 ..

Untitled2 파이썬 기본 연산 분석¶ 대부분의 산술 연산은 상수 시간이다. 곱셈은 덧셈이나 뺄셈보다 대개 오래 걸리고, 나눗셈은 더 오래 걸리지만, 이들의 실행시간은 피연산자의 크기와는 상관이 없다. 매우 큰 정수들은 예외이긴 하다. 그런 경우, 실행시간은 자릿수에 따라 증가한다. 인덱스 연산(시퀀스나 사전에 들어있는 원소들을 읽거나 쓰는 것) 또한 데이터 구조의 크기에 상관없이 상수 시간이다. 시퀀스나 사전을 쭉 거치는 for 루프는 본문에 있는 연산들이 모두 상수 시간인 한, 일반적으로 선형이라고 보면 된다. total = 0 for x in t: total += x 내장 함수인 sum 또한 선형으로, 위와 동일한 작업을 하지만 더 효율적으로 구현되었기 때문에 약간 빠를 뿐이다. 알고리즘 분석의..

Untitled2 증가 기준(Order of Growth)¶ 여러줍니 두 알고리즘을 분석하고 그들의 실행시간을 입력의 크기에 대한 함수로 표현했다고 치자. 알고리즘 A는 $100n+1$번의 단계를 밟아 크기 n인 문제를 풀 수 있고, 알고리즘 B는 $n^2 + n + 1$ 번의 단계를 밟는다. 다음 표는 여러 가지 크기의 문제들에 대해, A와 B의 알고리즘의 실행시간을 보여준다. 입력의 크기 A 알고리즘의 실행시간 B 알고리즘의 실행시간 10 1001 111 100 10001 10101 1000 100001 1001001 10000 1000001 $> 10^1$$^0$ n=10일 때, 알고리즘 A는 별로 좋아 보이지 않는다. 알고리즘 B보다 무려 10배나 긴 시간이 든다. 하지만 n=100인 경우 두 알..

Untitled1 알고리즘 분석¶ 알고리즘 분석은 알고리즘의 성능을 연구하는 컴퓨터 과학의 한 분야로, 특히 실행시간과 필요공간에 대해 연구한다. 더 많은 정보를 보려면 http://en.wikipedia.org/wiki/Analysis_of_algorithms 를 참고하자. 알고리즘 분석의 실질적인 목표는 디자인을 결정하기 위해서 여러 가지 다른 알고리즘들의 성능을 예측하는 것이다. 2008년 미국의 대선 캠페인 기간에 구글을 방문했을 때 버락 오바마 후보는 즉흥적인 분석을 해보라는 요청을 받았다. 에릭 슈미트 최고경영자는 그에게 농담 삼아 '100만 개의 32비트 정수들을 정렬하는 가장 효율적인 방법은 무엇이냐'고 물었다. 분명히 오바마는 누구에게 귀띔을 받았을 것이다. 재빠르게 '버블 정렬 알고리즘..

랜덤 그래프, 연결 그래프, 폴 에어디쉬 랜덤 그래프¶ 랜덤 그래프는 문자 그대로의 뜻을 가지고 있다. 무작위로 생성된 연결선들이 있는 그래프인 것이다. 그래프를 생성할 수 있는 무작위 프로세스는 당연히 여러 가지 종류가 있으며, 그래서 랜덤 그래프의 종류도 여러 가지다. 그 중에서 흥미로운 것이 G(n,p)로 나타내는 에어디쉬-레니 모델이다. 해석하자면 두 개의 노드 사이에서 연결선이 존재할 확률이 p일 때, n개의 노드로 된 그래프를 생성하는 모델이다. 참고 : http://en.wikipedia.org/wiki/Erdos-Renyi_model 연결 그래프¶ 모든 노드에서 다른 모든 노드로 경로가 존재할 때 그 그래프는 연결되었다고 말한다. 참고 : http://en.wikipedia.org/wiki..

그래프 표현하기 그래프 표현하기¶ 그래프를 그릴 때는 일반적으로 노드를 동그라미나 사각형으로, 연결선을 선으로 그린다. 위 그래프에서 연결선들의 가중치는 미국 동북부 도시들 간의 대략적인 이동시간을 나타낸다. 이 경우, 노드의 배치는 도시들의 대략적인 지리적 위치를 반영하고 있지만, 일반적으로 그래프의 레이아웃은 임의로 배치된다. 그래프 알고리즘을 구현하기 위해서, 여러분은 그래프를 데이터 구조의 형식으로 나타내는 법을 알아야 한다. 그러나 가장 좋은 데이터 구조를 선택하기 위해서는 그래프가 어떤 작업들을 지원해야 하는지를 먼저 알아야 한다. 이 같은 닭이 먼저냐 달걀이 먼저냐 하는 문제에서, 여러 가지 그래프 알고리즘에 쓰기 좋은 그래프 구조를 먼저 보여주고자 한다. 이후에 이 구조로 다시 돌아와 장단..

그래프란 무엇인가?¶ 많은 사람들이 '그래프'라고 하면 데이터 세트의 표현, 즉 막대 차트나 심전도 같은 것을 연상한다. 이 장에서 다루는 그래프는 그런 것이 아니다. 이 장의 그래프는 이산의, 서로 연결된 원소들이 포함된 시스템을 모델링하기 위한 추상화라고 생각해야 한다. 여기서 원소들은 노드로 표현되고 상호 연결은 연결선으로 표현된다. 예를 들자면 도시 각각을 하나의 노드로, 도시들을 연결하는 도로를 연결선으로 표현해서 도로 지도를 그릴 수 있다. 또는 소셜 네트워크의 경우, 각 사람을 노드로 표현하고 사람들이 서로 '친구'인 경우 그들 사이에 연결선을 그리고, 그렇지 않은 경우 연결선으로 잇지 않는 식으로 표현이 가능하다. 어떤 그래프에서는 연결선들의 길이가 서로 다른데, 이것은 '가중치'나 '비용..