전체 글
-
[Python 자료구조 #정렬과 탐색2] 순차탐색, 이진탐색, 보간탐색, 해싱Programming 기초/Python 2023. 5. 24. 18:41
* 탐색(searching) 탐색은 레코드(record)의 집합에서 원하는 레코드를 찾는 작업이다. 테이블(table) : 보통 이러한 레코드들의 집합 탐색키(search key) : 레코드들이 서로를 구별하여 인식하기 위해 가지고 있는 키(key) 탐색은 테이블에서 원하는 탐색키를 가진 레코드를 찾는 작업이다. 탐색에서는 테이블을 구성하는 방법에 따라 효율이 달라진다. 맵 또는 딕셔너리는 자료를 저장하고 탐색키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 탐색을 위한 자료구조를 말한다. * 맵(map) 맵(map)은 엔트리(entry)라고 불리는 키를 가진 레코드(keyed recod)의 집합이다. 엔트리는 두 개의 필드를 가진다. 키(key) : 영어 단어나 사람의 이름과 같은 레코드를 구분할..
-
[Python 자료구조 #정렬과 탐색1] 선택정렬, 삽입정렬, 버블정렬, 정렬 응용한 집합Programming 기초/Python 2023. 5. 23. 21:32
* 정렬(sorting) 오름차순( ascending order) 내림차순(descending order) 레코드(record) : 정렬시켜야 될 대상 필드(field) 레코드는 여러 개의 필드로 이루어지고, 필드는 속성들이다. 키(key) 또는 정렬 키(sort key) : 정렬의 기준이 되는 필드 정렬 : 레코드들을 키(key)의 순서로 재배열하는 것 * 정렬 장소에 따른 분류 내부(internal)정렬 : 모든 데이터가 메인 메모리에 올라와 있는 정렬 외부(external)정렬 : 외부 기억 장치에 대부분의 데이터가 있고 일부만 메모리에 올려 정렬하는 방법으로 대용량 자료를 정렬하기 위해 사용한다. * 구현 복잡도와 알고리즘 효율성에 따른 분류 단순하지만 비효율적인 방법 : 삽입정렬, 선택정렬, 버..
-
[Python 자료구조 #연결리스트3] 이중연결리스트 : 연결된 덱Programming 기초/Python 2023. 5. 23. 02:21
* 이중연결리스트의 응용 : 연결된 덱(linked deque) 먼저 덱을 단순연결리스트로도 구현할 수 있다. 그러나 deleteRear연산에서 문제가 생긴다. 다른 연산들은 모두 O(1)에 처리가 가능한데 비해 이 연산은 O(n)이 걸린다. 후단을 삭제하고 나면 rear가 한 칸 앞으로 움직여야 하는데, 선행 노드의 정보가 없어서 front부터 탐색해야 하기 때문이다. 이 문제를 해결하는 방법은 이중연결리스트를 사용하는 것이다. ※ 이중연결리스트를 이용하면 전후단 삭제의 시간 복잡도는 모두 O(1)이 된다. class DNode: # 이중연결리스트는 2개의 링크를 갖는다. def __init__(self, elem, prev=None, next=None): self.data = elem # 노드 내의 ..
-
[Python 자료구조 #연결리스트2] 원형연결리스트 : 연결된 큐Programming 기초/Python 2023. 5. 23. 01:40
* 원형연결리스트의 응용 : 연결된 큐(linked queue) 맨 앞과 뒤에 있는 노드를 front와 rear가 가리키는 구조. 삽입은 후단(rear), 삭제는 전단(front)에서 이뤄짐 front는 tail.link이다. 원형연결리스트에서는 tail(또는 rear)만을 변수로 저장한다. front를 변수로 하면 rear을 찾을 때 O(n)의 시간이 걸리므로 tail을 사용하는 것이 rear와 front에 바로 접근할 수 있다는 점에서 훨씬 효율적이다. class Node: # 노드 클래스 생성 def __init__(self, elem, link=None): self.data = elem self.link = link class CircularLinkedQueue: def __init__(self)..
-
[Python 자료구조 #연결리스트1] 단순연결리스트 : 연결된 스택Programming 기초/Python 2023. 5. 22. 21:29
* 연결 리스트 용량이 고정되어 있지 않다. 삽입과 삭제가 용이하다. n번째 항목에 접근하는데 O(n)의 시간이 걸린다. * 연결 리스트 구조 노드(node) : 연결된 구조에서 하나의 데이터 상자 노드는 데이터 필드(data field)와 하나 이상의 링크 필드(link field)를 갖는다. 데이터 필드에는 저장할 데이터가, 링크 필드에는 다른 노드의 주소를 저장하는 변수이다. *헤드 포인터(head pointer) 연결 리스트는 첫 번째 노드만 알면 링크로 매달려 있는 모든 노드에 순차적으로 접근할 수 있다. 따라서 시작 노드의 주소를 반드시 저장해야 한다. 연결리스트에서 첫 번째 노드의 주소를 저장하는 변수를 헤드 포인터라고 한다. 마지막 노드는 더 이상 연결할 노드가 없으므로 링크의 값을 Non..
-
[Python 자료구조 #큐3] 우선순위 큐, 미로 찾기Programming 기초/Python 2023. 5. 15. 14:33
* 우선순위 큐(priority queue) 삭제 연산에서 어떤 요소가 먼저 삭제되는가에 따라 최대 우선순위 큐와 최소 우선순위 큐로 나누어지지만, 특별한 언급이 없으면 우선순위 큐는 가장 높은 우선순위의 요소가 먼저 삭제되는 최대 우선순위 큐를 의미한다. 실제로 가장 효율적인 우선순위 큐의 구현 방법은 트리 구조를 사용하는 힙(heap)이다. (여기서는 리스트를 이용해서 구현할 것임.) 단순화를 위해 데이터 자체가 우선순위를 나타낸다고 가정한다. 일반적으로는 (데이터, 우선순위) 형식의 튜플 구조가 바람직하다. from Stack import*# 이전 포스팅에서 만든 stack.py 모듈을 가져왔다. class PriorityQueue :# 우선순위 큐 클래스 생성 def __init__( self )..
-
[Python 자료구조 #큐2] 원형 덱Programming 기초/Python 2023. 5. 11. 04:05
* 덱(데크, deque) 큐가 FIFO의 단 방향으로만 삽입 삭제가 가능한 자료구조라면, 덱은 전단(front)과 후단(rear) 양쪽에서 삽입과 삭제가 가능한 자료구조이다. 원형 큐를 상속하여 원형 덱(CircularDeque) 클래스를 구현한다. 덱 ADT(추상 자료형) CircularQueue는 이전 포스팅 참고. from CircularQueue import *# CircularQueue를 포함한다. class CircularDeque(CircularQueue) : # 원형 큐의 크기는 10으로 설정했었다. # def __init__( self ) : # 여기서는 생성자를 굳이 호출할 필요가 없다. # super().__init__() # 부모의 생성자를 호출하기 위해서는 super().를 붙인..
-
[Python 자료구조 #큐1] 선형 큐, 원형 큐, 너비우선탐색Programming 기초/Python 2023. 5. 10. 23:55
* 큐(queue) 선입선출(First-In First Out: FIFO)의 자료구조이다. 실시간 비디오 스트리밍에서 다운로드 된 데이터가 비디오를 재생하기에 충분하지 않으면 큐에 순서대로 모아두었다가 충분한 양이 되었을 때 비디오를 복원하여 재생하는데 이것을 버퍼링(buffering)이라고 한다. * 선형 큐 삭제 연산(pop)의 시간 복잡도는 O(n)이다. 비효율적이다. 삭제연산을 O(1)로 동작하도록 구현한 것이 원형 큐다. items = [ ]# 선형 큐 # 선형 큐 ADT(추상 자료형) def isEmpty():# 큐가 비어있는지 확인 return len(items) == 0 def enqueue(item):# 항목 x를 큐의 맨 뒤에 추가한다. items.append(item) def dequ..