Algorithm/자료구조

파이썬으로 구현하는 퀵 정렬(Qucik Sort)

Concept 병합 정렬(Merge Sort)과 마찬가지로, 퀵 정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 $O(nlogn)$이다 하나의 리스트에서 피봇(pivot)이라고 불리는 임의의 기준값을 사용하여 pivot 값을 기준으로 pivot 보다 작은 값의 그룹과 큰값의 그룹으로 나눈다. 이 때 두 그룹의 각 요소들은 정렬된 상태는 아니지만, pivot은 정렬된 위치로 들어가게되며 이를 재귀호출을 통해 정렬하게 된다. 전체적인 동작 과정은 다음과 같다 구현 코드 (아래 코드는 pivot을 arr의 첫번째 요소로 잡은 코드입니다; pivot = arr[0]) 1) 정렬되지 않은 데이터 -> 리스트로 입력 받기 >>>3 2 4 6 9 1..

파이썬으로 구현하는 병합정렬(Merge Sort)

Concept 병합정렬은 분할 정복(Divide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘으로, 시간복잡도는 O(nlogn)이다 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는 정렬방법이다. 이때 병합 정렬은 아래와 같은 분할 정복 메커니즘을 따르게 된다 - 분할(Divide): 입력 리스트를 같은 크기의 2개의 부분 리스트로 분할한다 - 정복(Conquer): 부분 리스트를 정렬한다 - 결합(Combine): 정렬된 부분 리스트를 하나의 리스트에 통합한다 *이 때 그림에서 표현은 생략되었으나 부분 리스트의 크기가 1이 될 때까지 분할 후 정렬 후 합병과정을 거치게 된다 구현 코..

파이썬으로 구현하는 덱(Deque)

덱(Deque)이란? double-ended queue로, 큐의 앞과 뒤 모두에서 삽입 및 삭제가 가능한 큐를 의미한다. 덱은 원형 큐(Circular Queue)를 확장하면 손쉽게 구현할 수 있다. 원형 큐 구현에 관해서는 해당 게시글을 참고하시면 좋습니다 https://codingsmu.tistory.com/123 파이썬으로 구현하는 원형 큐(Circular Queue) 원형 큐(Circular Queue)란? 배열로 구현 된 선형 큐(Linear Queue)의 경우 데이터의 삽입/삭제 시 데이터들을 앞으로/뒤로 당겨주는 과정이 필요해 최악의 경우 O(n)의 시간복잡도를 가지게 된다. 이러한 codingsmu.tistory.com 0. 멤버 변수&초기화 먼저 덱 클래스의 멤버 변수(member var..

파이썬으로 구현하는 원형 큐(Circular Queue)

원형 큐(Circular Queue)란? 배열로 구현 된 선형 큐(Linear Queue)의 경우 데이터의 삽입/삭제 시 데이터들을 앞으로/뒤로 당겨주는 과정이 필요해 최악의 경우 O(n)의 시간복잡도를 가지게 된다. 이러한 선형 큐의 단점을 극복한 구조가 원형 큐이다 0. 멤버 변수&초기화 먼저 원형 큐 클래스의 멤버 변수(member variable)화 초기화하는 과정을 살펴보자 class CircleQueue: rear = 0 front = 0 MAX_SIZE = 100 queue = list() def __init__(self): self.rear = 0 self.front = 0 self.queue = [0 for i in range(self.MAXSIZE)] 1. 공백 상태 원형큐가 비워져 있..

[이론] 우선순위 큐 (Priority Queue)

우선순위 큐란? 일반적인 큐는 선입선출(FIFO) 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 되는데, 우선순위 큐는 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다 우선 순위 큐는 최소 우선 순위, 최대 우선 순위 2가지로 구분할 수 있다 최소 우선순위 큐 : 가장 우선 순위가 낮은 요소를 삭제 최대 우선순위 큐 : 가장 우선 순위가 높은 요소를 삭제 스택 vs 큐 vs 우선순위 큐 자료구조 삭제되는 요소 스택 가장 최근에 들어온 데이터 큐 가장 먼저 들어온 데이터 우선순위 큐 가장 우선순위가 높은 데이터 우선순위 큐의 추상 자료형(ADT) 객체 : n개의 element형의 우선순위를 가진 요소들의 모임 연산 create() ::= 우선순위 큐를 생성 init(q) ::..

[이론] 힙(Heap)

힙(Heap)란?여러개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조로  최대 힙(max heap)와, 최소 힙 (min heap)두 가지 종류로 나뉘게 된다최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리최소 힙: 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 최대 힙과 최소 힙은 항상 아래의 조건이 성립하게 된다최대 힙 : $key(부모노드) >= Key(자식노드)$최소 힙 : $key(부모노드)  힙의 특징힙의 목적은 삭제 연산이 수행될 때마다 가장 큰/작은 값을 찾아내기만 하면 된다(가장 큰/작은 값은 루트 노드에 있음) 따라서 힙 안에서 데이터들은 느슨한 정렬 상태를 유지한다 즉, 전체 데이터를 정..