본문 바로가기

전체 글160

[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.
[19대 대통령 후보 대선 공약 비교] 문재인-안철수-심상정-유승민-홍준표 5명 후보의 주요 대선공약 비교 며칠전, 대통령 후보 4인의 주요 공약들에 대해서 포스팅했는데, 생각보다 많은 분들이 관심을 가져주셨습니다. 오늘은 대통령 4분의 공약과 더불어 홍준표 후보의 공약도 함께 올려드립니다. 또한 기존에 빠진 공약들과 보충이 필요한 공약들에 대해서 보충하였습니다. 유권자분들의 현명한 판단의 기준 중 하나로 작용하기를 바랍니다. 목차 클릭하시면, 해당 부분으로 이동합니다. - 국방력 강화 - 한미관계 - 사드배치 - 전술핵 재배치 - 한일관계 - 한일 성노예(위안부) 합의 - 한중관계 - 남북관계 - 개성공단 - 북핵문제 - 현역병 월급 - 군 복무기간 - 군 비리 근절 - 노동시간 - 4차 산업혁명 - 일자리 창출 - 창업/중소기업 지원 - 부동산 - 최저임금 - 고용안정/유연화/임금차별 - 공정한 시장경제 .. 2017. 4. 18.

티스토리툴바