자료구조4 algorithms/자료구조 & 알고리즘에 대하여 자료구조? 자료구조=데이터 구조=data structure 자료구조란, 현실 세계의 정보를 디지털 형태(데이터)로 저장 및 관리할 수 있게 하는 데이터 구조다. 특히, 적절한 자료구조를 이용해 대량의 데이터를 효율적으로 관리할 수 있다. 효율적인 데이터 처리를 위해서는 데이터가 가진 특성이 무엇이냐에 따라 어떤 데이터 구조를 사용할 것인지가 결정된다. 적절한 데이터 구조를 사용할수록 효율적인 코드가 된다. 데이터를 관리하는 대표적인 예로는 백과사전, 그리고 주민등록번호가 있다. 백과사전은 알파벳의 순서대로 지식들이 나열된 커다란 자료구조라고 볼 수 있다. 또한, 대한민국 국적을 가진 모든 성인남녀의 신원이 명확히 구분하기 위해 도입된 주민등록제도에 따라, 한국인은 모두 앞 6자리와 함께 추가적으로 7자리.. 2019. 12. 30. [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. 이전 1 다음
