Data Structure & Algorithm (31) 썸네일형 리스트형 트리 (Tree) 1. 트리 (Tree) 구조 트리(Tree)란 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조이다. 특히 트리 중 이진 트리(Binary Tree) 구조는 탐색(검색) 알고리즘 구현을 위해 많이 사용된다. 2. 알아둘 용어 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 상위 레벨(상단)에 연결된 노드 Child Node: 어떤 노드의 하위 레벨(하단)에 연결된 노드 Leaf Node (Terminal Node): Child Nod.. 해시 테이블 (Hash Table) (3) 6. 충돌(Collision) 해결 알고리즘 (좋은 해시 함수 사용하기) 해시 테이블의 가장 큰 문제는 충돌(Collision)이다. 이 문제를 충돌(Collision) 또는 해시 충돌(Hash Collision)이라고 부른다. 두 개 이상의 데이터가 동일한 hash address에 저장이 될 경우 충돌이 발생한다. 충돌 해결의 전략은 크게 2 가지이다. 개방 해싱(Open Hashing) 기법: 해시 테이블 저장공간 외의 공간을 활용하는 기법 폐쇄 해싱(Close Hashing) 기법: 해시 테이블 저장공간 안에서 충돌 문제를 해결하는 기법 Chaining 기법은 개방 해싱(Open Hashing) 기법 중 가장 많이 사용되는 기법이다. 충돌이 일어나면 링크드 리스트라는 자료구조를 사용해서 링크드 리스.. 해시 테이블 (Hash Table) (2) 앞서 알아본 해시 테이블에 대해 조금 더 깊이 알아보겠다. 4. 자료 구조 해시 테이블의 장단점과 주요 용도 장점 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.) 해시는 키에 대한 데이터가 있는지(중복) 확인이 쉽다. 단점 일반적으로 저장공간이 조금 더 많이 필요하다. 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도의 자료구조가 필요하다. 주요 용도 검색이 많이 필요한 경우 저장, 삭제, 읽기가 빈번한 경우 캐시 구현시 (중복 확인이 쉽기 때문) 해시 자료구조의 장점 중 하나는 키에 대한 데이터가 있는지 확인이 쉽다는 것이다. 방대한 데이터가 있을 때, 저장을 하다가 중복된 데이터가 있으면 배열의 경우에는 중복이 되어있는지 안 되어 있는지 기존 데이터를 다 찾아야 한다. 반면.. 해시 테이블 (Hash Table) 1. 해시 구조 Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라진다. 파이썬 딕셔너리(Dictionary) 타입이 해시 테이블의 예이다. Key를 가지고 데이터(Value)를 꺼내는 것 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용한다. (공간과 탐색 시간을 맞바꾸는 기법) (단, 파이썬에서는 해시를 별도로 구현할 필요가 없다. 딕셔너리 타입을 사용하면 되기 때문이다.) 2. 알아둘 용어 해시(Hash): 임의 값을 고정 길이로 변환하는 것 해시 테이블(Hash Table): 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(Hashing Function): Key에 대.. 링크드 리스트 (Linked List) (3) 마찬가지로 앞서 알아본 링크드 리스트(Linked List)에 대해 더 깊이 알아보겠다. 링크드 리스트의 가장 큰 단점은, 어떤 데이터를 찾든 반드시 맨 앞에 있는 노드(헤드)의 데이터를 찾아서 거기에서 주소를 가지고 원하는 데이터로 이동을 해야 한다는 것이다. 만약 노드가 10,000개이고, 내가 찾는 데이터가 8,000번째 노드에 있다고 하면, 0~9,999번까지 sorting 되어 있다고 할 때 0번부터 8,000번까지 찾아야 한다. 이에 반해 아예 맨 뒤에서부터 검색하면 상대적으로 9,999번에서 8,000번까지 찾아가는 것은 훨씬 검색량이 적어서 효율적이다. 더 빠르게 원하는 데이터를 찾을 수 있는 것이다. 그래서 나타난 것이 더블 링크드 리스트(Double Linked List)이다. 더블 링.. 링크드 리스트 (Linked List) (2) 앞서 알아본 링크드 리스트(Linked List)에 대해 조금 더 깊이 알아보겠다. 4. 링크드 리스트 데이터 사이에 데이터를 추가 링크드 리스트는 유지 관리에 부가적인 구현이 필요하다. 위 그림을 보면, 원래 데이터 값이 12인 노드는 데이터 값이 99인 노드를 가리키고 있다. 그런데 데이터 값이 37인 새로운 노드가 이 두 노드 사이에 들어가려고 하면, 원래 99를 가리키고 있던 12는 37을 가리켜야 하고, 추가된 노드인 37은 99를 가리켜야 한다. 부가적인 구현이 필요한 것이다. 링크드 리스트 데이터 사이에 데이터를 추가하는 코드를 만들어보면, node = head# 노드에 헤드값 넣기 search = True while search: if node.data == 1:# 데이터 값이 1인 노드 .. 링크드 리스트 (Linked List) 1. 링크드 리스트 (Linked List) 구조 링크드 리스트(Linked List)란 연결 리스트라 불리기도 하는 자료구조이다. 배열은 순차적으로 연결된 공간에 데이터를 나열하는 구조인 반면, 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다. (파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원한다.) 링크드 리스트의 기본 구조와 용어 노드(Node): 데이터 저장 단위 (데이터값, 포인터)로 구성 포인터(Pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 일반적인 링크드 리스트의 형태 위 그림에서처럼, 한 노드가 두 칸이 있다고 할 때, 하나는 저장된 데이터값을 넣고, 다른 하나는 다음 노드를 가리키는 포인터로 이.. 큐(Queue) & 스택(Stack) 큐 (Queue) 1. 큐 구조 줄을 서는 행위와 유사 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일 FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대 2. 알아둘 용어 Enqueue: 큐에 데이터를 넣는 기능 Dequeue: 큐에서 데이터를 꺼내는 기능 3. 파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용하기 queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공 프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용 Queue(): 가장 일반적인 큐 자료 구조 .. 이전 1 2 3 4 다음
