Computer Science/Data Structure (7) 썸네일형 리스트형 <자료구조> 우선순위 큐 1. 우선순위 큐(Priority Queue) * 우선순위 큐 - 우선순위 큐는 큐와 달리 우선순위가 높은 것부터 Dequeue를 시키는 자료구조를 의미한다. - 이 장에서는 파이썬 모듈 heapq를 이용하여 구현해보자. * 힙(heap) - 힙은 완전이진트리(complete binary tree)를 기본으로 하는 자료구조이다. - 힙은 부모-자식 노드의 키값 대소 관계가 일정하게 유지된다. - 최대 힙 : 자식 노드의 키 값보다 부모 노드의 키 값이 항상 크다. - 최소 힙 : 자식 노드의 키 값보다 부모 노드의 키 값이 항상 작다. - 참고로 파이썬에서 heapq모듈은 최소 힙 자료구조만 제공한다. 2. 구현하기 * 생성 - 먼저 모듈을 불러와야 한다. import heapq heap = [] - 모.. <자료구조> 해시 테이블과 트라이 * 해시 테이블 - 연결리스트와 트리구조에서 검색시간이 O(n)과 O(log n)이 걸렸다. 그러나 컴퓨터 공학자들은 이 시간을 더 단축시켜서 O(1)에 가깝게 만들기를 원했다. - 위를 가능하게 해주는 구조 중 하나가 바로 해시 테이블이다. - 해시테이블은 연결리스트를 원소로 가지는 배열이다. - 이름표를 바구니에 담는다고 가정하자. 단순히 바구니 하나에 여러 이름표를 담으면 사람들이 찾는 데 오랜 시간이 걸릴 것이다. - 그렇다면 바구니를 여러개로 한다면 어떨까. 이 때 바구니를 무슨 기준으로 나누는 것이 좋을까. - 이 때의 기준이 해시 함수이다. 이름표이므로 해시함수를 이름의 가장 첫 글자로 시도해보자. 알파벳이라면 총 16개의 포인터들이 생기고, 그 알파벳은 각각 연결리스트를 가리키게 된다. -.. <자료구조> 트리구조 * 연결리스트의 장단점 - 연결리스트는 배열과 달리 새로운 값을 추가하면 메모리를 추가하지 않아도 되었다. - 그러나 배열과 달리 임의 접근이 불가능하다. - 위와 같은 단점은 값의 추가, 검색에서 손실을 가져온다. 추가와 검색을 위해 연결리스트의 각 node를 하나하나 이동해야하기 때문이다. - 배열의 경우에는 정렬만 되어 있다면 임의 접근이 가능하여 이진검색을 이용하면 O(log n)의 실행시간을 갖는다. 그러나 위와 같은 단점때문에 연결리스트는 O(n)이 된다. * 트리구조의 등장 - 트리는 연결리스트를 기반으로 한 새로운 데이터 구조이다. - 연결리스트에서 노드의 연결이 1차원이었다면 트리에서의 노드의 연결은 2차원이다. - 위에서 언급되었던 단점을 해결한 '이진 검색 트리' 를 살펴보자. - 가.. <자료구조> 연결리스트와 노드 * 연결리스트 소개 - 배열에선 각 인덱스 값들이 메모리 상에서 연이어 저장되어있다. 그렇다면 배열에 새로운 값을 추가하려면 어떻게 해야 할까 - 기존 배열 바로 뒤에 다른 값이 있을 수 있으므로 배열의 길이를 늘리려면 새로운 메모리를 할당해서 값을 하나하나 복사하여 옮겨야한다. - 위의 방식은 너무 번거롭다. 각 값을 메모리의 다른 곳에 저장하더라도 배열처럼 사용할 수 있다면 어떨까. 각 값에 다음 값의 메모리 주소를 기억하게 하는 것이다. 이를 연결리스트라 한다. (Linked List) - 이제 첫 값인 1은 2의 주소를 갖고, 2는 3의주소를, 3은 Null을 갖게 된다. * 노드 - 연결리스트를 C언어 코드로 구현하면 다음과 같은 구조체로 정의한다. typedef struct node { int.. <자료구조> 스택과 큐(2) 1. 큐란 * 큐 - 스택과 같이 데이터를 임시 저장하는 자료구조이지만 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다는 차이가 있다. (선입선출구조) - 인큐(enqueue) : 큐에 데이터를 추가하는 행위 - 디큐(dequeue) : 큐에서 데이터를 꺼내는 행위 - 프론트(front) : 데이터가 빠지는 가장 앞쪽 부분 - 리어(rear) : 데이터를 넣는 부분 2. 배열과 큐 - 인큐 : 맨 끝 데이터의 다음 인덱스에 원소를 저장하여 처리의 복잡도는 O(1)이고 cost가 적다. - 디큐 : que[0]에 저장된 원소를 꺼내면서 이후의 원소를 모두 앞쪽으로 옮겨야한다. 따라서 복잡도는 O(n)이고 매우 비효율적이다. ※ 우선순위 큐 : 인큐할 때 데이터에 우선순위를 부여하고 디큐할 때 우선순위대로 꺼내는.. <자료구조> 스택과 큐(1) 1. 스택이란 * 스택 - 데이터를 임시 저장할 때 사용하는 자료구조이다. 후입선출 방식의 입출력 순서를 가진다. - 푸시(Push) : 스택에 데이터를 쌓아 넣는 일 - 팝(Pop) : 스택에서 데이터를 꺼내는 일 - 데이터는 겹겹이 쌓이는 방식으로 푸시하면 top에 쌓이고 pop하면 top에서부터 꺼낸다. 2. 스택의 구현 - 스택을 구현하기 위해 크기가 결정된 고정길이 스택을 클래스를 이용하여 만드려면 어떤 요소들이 필요할까. * 스택 구현 - 스택을 구현하기 위해서는 다음과 같은 요소들이 필요하다. - 스택 배열 : 푸시한 데이터를 list형 배열에 저장하도록 하면 첫번째 푸시한 데이터는 list[0]에 저장된다. - 스택포인터 : 스택에 쌓여있는 데이터의 갯수이다. 가장 마지막에 푸시한 데이터는.. <자료구조> 자료구조와 배열 1. 자료구조와 배열 * 배열이란 - 하나의 값이 아닌 묶음 단위의 값을 저장하는 자료구조 - 원소 : 배열에 저장된 객체 한 단위 - 파이썬에서는 주로 리스트와 튜플로 배열을 표현함. * 객체 - 파이썬은 데이터, 함수, 클래스, 모듈 등 전부 객체로 취급하기때문에 변수는 값을 갖는 것이 아니다. - 모든 객체는 메모리를 차지하며 식별번호가 따로 존재한다. - 따라서 변수는 객체를 참조하는 별명이라고 보는 것이 좋다. 예를 들어 10의 고유번호를 19991010 이라고 하자. 이 때 x = 10 이라고 선언하고 x의 식별번호를 확인하면 19991010이 나타난다. ※ 값을 비교할 때 연산자로 == 을 사용하지만 두 객체의 값과 식별번호를 함께 비교할 경우에는 is 를 사용한다. * 리스트와 튜플 - 리.. 이전 1 다음
