본문 바로가기

전체 글165

[paper]How to Read a Paper 대학원 생활을 시작한지 이제 2개월 그리고 20일이 지나가고 있다. 랩실 생활을 하면서 논문을 읽을 기회는 딱 한 번 있었는데, 열심히 준비한다고 했는데도 불구하고 세미나때 여러모로 당황했다. 학기가 시작하고나서 접한 본 논문은 나와 같이 이제 갓 석사를 시작하는 아무것도 모르는 그런 학생들에게 도움이 될 것이다. 나는 이 논문을 읽으면서 앞으로 논문을 읽을 땐 어떻게 접근해야하는지에 대한 통찰을 얻을 수 있었다. 지식은 나누면 1/n이 아니라 n배가 된다고 배웠기에 내가 해석한 ‘How to Read a Paper’라는 논문의 해석을 올려본다. 개요 연구자들은 연구 논문을 읽는데에 굉장히 많은 시간을 보낸다. 반면 논문을 읽는 데에 필요한 기술들은 어디서도 거의 가르쳐주지 않는다. 이 논문은 연구 논문.. 2017. 10. 4.
[Algorithms] 해쉬 테이블(Hash Table) 해시 테이블은 궁극의 탐색 알고리즘이라고 불린다. 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해싱(hashing)하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것이 기본적인 컨셉이다. 해시 테이블은 한마디로 공간을 팔아 성능을 얻어내는 것이다. 해시값으로의 접근은 다음과 같은 방식으로 이루어진다. Table[3819] = 123817; 데이터는 해시 함수를 거치면 다음 그림처럼 테이블 내의 주소(즉, 인덱스)로 변환된다. 해시 테이블은 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다. 그렇지 않으면, collision 현상이 발생한다. 통계적으로 해시 테이블의 공간 사용률이 70%~80%에 이르면 성능 저하가 나타나기 시작한다. 다른 배열 형식의.. 2017. 4. 21.
Top down Approach 하향식(Top-Down) 방식은 노드가 ✔ ↓ 의 방향으로 먼저 간 다음, ✔ → 의 방향으로 채워진다. 이 두 순서로 노드가 채워지게 된다. 즉 위에서부터 채워나가되, 각 레벨에서의 삽입은 왼쪽에서 오른쪽 순서로 하게 된다. 이러기 위해선 두 가지 조건이 필요하다. 1. 각 노드에 저장된 값이 두 자식 노드에 저장된 값보다 크거나 같아야 한다. 작거나 같다는 조건으로 바꿔도 된다. 크기가 자식 노드보다 크거나 같은 경우를 Max heap이라 하고, 작거나 같은 경우를 Min heap이라고 한다. 2. 트리는 완전 균형 상태여야 하고, 마지막 레벨에 있는 leaf 노드들은 모두 트리의 가장 왼쪽 부분부터 채워져야 한다. 따라서 트리의 높이는 O(log n)이 된다. 이 두 조건은 자료구조 '힙'의 성질이.. 2017. 4. 20.
[Algorithms] 이진트리(Binary tree) 이진 트리(binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 말한다. 보통 첫 번째 노드를 부모 노드라고 하며 자식 노드는 왼쪽 노드(left noe)와 오른쪽 노드(right node)로 부른다. 이진 트리는 이진 탐색 트리와 이진 힙의 구현에 흔히 쓰이는 자료구조다. 용어정의 방향 간선(directed edge) : 부모 노드에서 자식 노드로 가는 경로를 가리킨다. 위 그림에서 화살표로 표현되어 있다. 루트 노드(root node) : 자신의 위로 부모 노드가 없는 노드다. 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node) : 자식 노드가 없는 노드다. 노드의 깊이(depth) : 루트 노드에서 특정 단말 노드까지의 길이다. 레벨(level)이라고 부르기도.. 2017. 4. 19.

티스토리툴바