data-structure

[자료구조] 단순/원형/이중 연결리스트(Linked List) 구현 - 파이썬(Python)

연결리스트(Linked List) 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장하는 선형 자료구조 연결리스트는 Node로 구성되어 있고, Node 안에는 Data와 Link(Next)로 구성 Data: 데이터 값 저장 Link(Next): 다음 노드를 가리킴 장점 데이터 추가, 삭제에 유리 배열: 시간복잡도 O(n) 연결리스트: 시간복잡도 O(1) 공간복잡도 측면에서 유리 (배열처럼 연속된 공간을 할당하지 않고 필요 시에만 메모리를 동적 할당하기 때문) 메모리 누수 X 유연한 메모리 관리 단점 데이터 탐색 시 불리 (데이터의 논리적 저장 순서와 물리적 저장 순서가 일치하지 않아 인덱스 접근이 아닌 전체를 순회해야 하기 때문) 배열: 시간복잡도 O(1) 연결리스트: 시간복잡도 O..

[자료구조] 우선순위 큐(Priority Queue/Heapq) 구현 - 파이썬(Python)

우선순위 큐란? 우선순위 큐는 먼저 들어온 데이터가 먼저 처리되는 일반적인 큐와 달리, 우선순위가 높은 데이터부터 처리되는 자료구조이다. 배열, 연결리스트, 힙(Heap)으로 모두 구현할 수 있지만 일반적으로는 시간복잡도가 적은 힙(Heap)을 사용한다. 힙(Heap) 최솟값, 최댓값을 찾아내는 연산을 빠르게하기 위해 고안된 완전이진 트리의 일종인 자료구조이다. 힙은 최소 힙과 최대 힙으로 구분할 수 있다. - 최소 힙: 루트노드가 가장 작은 값을 가지며, 항상 부모노드는 자식노드보다 작은 값을 가짐 - 최대 힙: 루트노드가 가장 큰 값을 가지며, 항상 부모노드는 자식노드보다 큰 값을 가짐 우선순위 큐 구현 (파이썬) - PriorityQueue from queue import PriorityQueue ..

[알고리즘] 그래프 탐색을 위한 DFS와 BFS - 파이썬(Python)

그래프 표현 그래프는 노드(Node)와 간선(Edge)로 표현되며 이때 노드를 정점(Vertex)라고도 한다. 프로그래밍에서 그래프는 '인접 행렬'과 '인접 리스트' 2가지 방식으로 표현할 수 있다. 인접 행렬 : 2차원 배열로 그래프의 연결관계를 표현하는 방식 - 각 노드가 연결된 형태를 기록하여 저장 INF = 999999999 # 무한의 비용 선언 # 2차원 리스트를 통해 인접 행렬 표현 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) 인접 리스트 : 리스트로 그래프의 연결관계를 표현하는 방식 - 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장 # 행이 3개인 2차원 리스트로 인접 리스트 표현 graph = [[] for _..

[자료구조] 스택(Stack)과 큐(Queue) - 파이썬(Python)

스택(Stack) 나중에 넣은 데이터를 먼저 빼는 후입선출(LIFO - Last In First Out) 구조 ex) 박스 쌓기, 트럭에 물건 넣기 파이썬 기본 리스트에서 append()와 pop() 메서드를 사용하여 구현 stack = [] stack.append(1) # stack: [1] stack.append(2) # stack: [1, 2] stack.append(3) # stack: [1, 2, 3] stack.append(4) # stack: [1, 2, 3, 4] stack.pop() # stack: [1, 2, 3] stack.pop() # stack: [1, 2] stack.append(3) # stack: [1, 2, 3] stack.pop() # stack: [1, 2] 큐(Queu..