넘치게 채우기

덱 덱(deque)는 double - ended - queue의 줄임말로, 앞뒤로 빼고, 넣는 것이 가능한 자료구조이다. 큐와 스택을 합친 자료구조라고 볼 수도 있다. 파이썬에서는 collections 라는 모듈에서 쉽게 사용할 수 있다. 리스트와 비슷해보이는 연산들이 있지만, 들여다보면 차이가 존재한다. 리스트는 맨 앞 데이터를 빼면, 뒤에 있는 데이터들이 다 앞으로 당겨져서 시간복잡도가 O(n)이 된다. 덱은 이중 연결리스트 기반으로 구현되어, 맨 앞 데이터를 빼더라도 시간복잡도가 O(1)이다. 덱의 연산 appendleft(): 앞쪽으로 데이터 enqueue popleft(): 앞쪽에서 데이터 dequeue append(data): 뒤쪽으로 데이터 enqueue pop(): 뒤쪽에서 데이터 dequ..

지난 2-2 글에서, 내가 구현한 배열을 이용한 큐는, 엄밀히 따지면 파이썬의 리스트를 이용한 것이다. '배열'이랑 구현한 것과 다른 점은, 큐의 크기를 정하지 않는다.(append하면 뒤에 새 칸을 만들고, pop하면, 칸이 줄어든다) pop 했을 때, 뒤 데이터들이 빈 자리를 채우러 앞으로 당겨진다. 그래서, '배열스러운' 큐를 다시 구현해보았다. 큐 - '배열'을 이용한 구현(Python) class queue(): #큐 선언 def __init__(self, size): self.size = size self.arr = [None] * self.size self.first = 0 self.last = 0 def isEmpty(self): #큐가 비어있는지 확인 if self.first >= sel..

큐(Queue) 큐 자료구조는 우리가 평소에 줄을 서듯, 먼저 들어온 사람이 먼저 나가는, 선입선출(先入先出, First in First out)의 형식을 따른다. 큐의 연산 큐의 연산은 다음 5가지가 있다: isEmpty(): 큐가 비어있는지를 판단한다. True 또는 False값으로 반환된다. enqueue(data): 큐에 값을 입력시킨다. dequeue(): 큐의 제일 먼저온 값을 내보낸다. rear(): 큐의 맨 뒤에 있는 값을 반환한다. front(): 큐의 제일 반저온 값을 반환한다(큐에서 pop하지는 않는다) 큐의 구현 - 배열을 이용한 구현(Python) class queue(): #큐 선언 def __init__(self): self.arr = [] def isEmpty(self): #..

스택(Stack) 스택 자료구조는 탄창에 총알을 넣고 빼듯, 먼저 넣은 데이터를 늦게 꺼내는 선입후출(先入後出, FILO(First in Last out)), 후입선출(後入先出, LIFO(Last in First Out))을 따른다. 스택의 연산 스택의 연산은 다음 4가지가 있다: isEmpty() : 스택이 비어있는지를 판단한다. push(data) : 스택의 맨 위에 데이터를 쌓는다 pop() : 스택의 맨 위 데이터를 스택에서 뺀다. top() : 스택의 맨 위의 값을 확인한다. 스택의 구현 - 배열을 이용한 구현(Python) class stack(): #스택 선언 def __init__(self): self.arr = [] def _len_(self): return len(self.arr) de..

연결 리스트(Python) - 전체 class Node(): #노드 선언 def __init__(self, data, next = None): self.data = data self.next = next class SimplyLinkedList(): def __init__(self): self.head = None def link(self, node, next): #노드 연결 node.next = next def getTail(self): #꼬리 노드 불러오기 currentNode = self.head while currentNode.next: currentNode = currentNode.next return currentNode def getIndex(self, data): #data의 인덱스 반환 ..

이중 연결 리스트 이중 연결 리스트는 기존의 연결리스트와는 달리, 쌍방향으로 연결이 되어있다. 이미 한 노드를 지나쳐도, 돌아갈 수 있다. 장점 찾아야 하는 값이 tail쪽에 가까울 때, head부터 시작해서 탐색하는 번거로움 등을 없앨 수 있다. 위치를 모르는 상태에서 값을 찾을 때에도, 앞에서 절반, 뒤 끝에서 절반씩 탐색하면 훨씬 효율적이다. 단점 변수를 3개 사용한다.(이전 메모리주소, 내 엘리먼트, 다음 메모리주소) 이 과정에서 메모리를 더 사용하게된다. 구현이 복잡해진다. 그러나, 이런 단점들을 두고도, 얻게 되는 것이 많아서, 실제 연결리스트를 사용할 때, 이중 연결리스트를 많이 사용한다. 노드의 추가 노드 a↔b↔d에서 b↔d 사이에 c를 연결하고 싶으면, c의 다음 노드로 d를 연결해주고..

연결 리스트는 순차 리스트와는 다르게, 리스트의 노드(요소)값의 메모리주소가 순차적이지 않다. 대신, 노드에 자신의 값과, 다음 노드의 메모리주소를 저장한다. 시작하는 노드를 머리(head)라고 하고, 맨 끝을 꼬리(tail)이라고 한다. 노드에서 다음 노드로 향하는 주소값을 포인터((Pointer)라고 한다. tail노드에서 가지고 있는 포인터값은 none 또는 null이라 한다. 접근 [2]에 있는 값을 보려면, 머리부터 다음 노드를 하나하나 찾아가야한다.(순차적으로 탐색해야한다) 시간복잡도는 O(N)이다. 삽입 A - B - C로 연결되어있는 연결 리스트 중 B-C 사이에 D 노드를 삽입하고 싶으면, B의 포인터를 D의 메모리주소, D의 포인터를 C의 메모리주소로 바꿔주면된다. 이때, 바꾸는 것의 ..

배열 배열은 같은 자료형의 변수들을 각각 순차적으로 이은 자료구조이다. 배열이 가지고있는 자료의 순서와 메모리상에 저장된 자료의 순서가 일치한다. 배열을 각각 구성하는 값을 요소(element)라고 하고, 배열 내에서 요소의 위치값을 인덱스(index)라 한다. 배열 A에서의 인덱스 i값은 A[i]로 표기한다. 일반적으로 배열이라 하면, 크기가 정해진 정적 배열(Static Array)라고 한다. 순차 리스트 순차 리스트는 배열과 같은 개념이나, 하나 다른 점이 있다. 크기가 정해지지 않은 동적 배열(Dynamic Array)라는 것이다. 기존 배열보다 더 많은 요소들을 받아야 할 때, 크기가 더 큰 새로운 배열을 만들어 기존 배열을 복사하고, 새로 받는 값들을 추가시킨다. C언어의 벡터, 파이썬의 리스..

좋은 알고리즘이란 무엇일까? 실행 속도가 빠르고, 컴퓨터의 메모리를 적게 사용하는 것이 좋은 알고리즘이 될 것이다. 알고리즘이 얼마나 빠른지와, 얼마나 메모리를 적게 쓰는지를 평가할 때는 알고리즘의 시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity)라는 척도를 이용한다. 시간 복잡도 시간 복잡도는 알고리즘의 속도에 대한 척도이다. 시간복잡도를 측정하는데는 연산이 이뤄지는 횟수를 센다. 연산은 데이터 입출력, 산술, 반복문, 조건문과 같은 제어문이 있다. 입력 데이터의 수 n에 따른 연산횟수의 함수 T(n)을 구성하고, 데이터의 수 n의 변화와 그 연산횟수 T(n)의 변화를 분석하여 알고리즘의 시간 복잡도를 평가한다. 선형 탐색(순차 탐색) 알고리즘을 예로 들어보면: ..