CS/Data Structure

환형 큐(Circular Queues)

환형 큐란? 정해진 개수의 저장 공간을 빙 돌려가며 이용하는 큐이다. 환형 큐에선 front로 데이터를 빼고, rear로 데이터를 입력하는 위치를 가진다. 입력과 출력을 따로 관리함으로써 항상 정렬을 하지 않아도 된다. 밑의 예시에서는 Head가 front, Tail이 rear이다. 환형 큐가 지원하는 연산 목록 size() - 현재 큐에 들어 있는 데이터 원소의 수를 구한다. isEmpty() - 현재 큐가 비어 있는지를 판단한다. isFull() - 큐에 데이터 원소가 꽉 차 있는지 판단한다. enqueue(x) - 데이터 원소 x를 큐에 추가한다. dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거하면서 반환한다. peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환한다. 배열을 이용..

큐 (Queues)

큐란? 자료를 보관할 수 있는 선형구조로, 넣을 떄에는 한 쪽 끝에서 밀어 넣어야(enqueue 인큐연산)하고, 꺼낼 떄에는 반대 쪽에서 뽑아 꺼내야(dequeue 디큐연산)하는 제약이 있다. 이처럼 먼저 넣은 것이 가장 먼저 꺼내어지는 성질 때문에 큐를 다른 말로는 선입선출(FIFO, first-in first-out) 자료 구조라고도 한다. 큐의 활용 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우 자료를 생성하는 작업이 여러 곳에서 일어나는 경우 자료를 이용하는 작업이 여러 곳에서 일어나는 경우 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우 큐..

스택 (Stacks)

스택이란? 접시를 차곡차곡 쌓았다가 맨 위의 접시부터 다시 꺼내어 사용하는 것처럼, 추가된 데이터 원소들을 끄집어내면 마지막에 넣었던 것부터 넣는 순서의 역순으로 꺼내지는 자료구조를 스택(stack)이라고 부른다. 이처럼 마지막에 넣은 것이 가장 먼저 꺼내어지는 성질 때문에 스택을 다른말로는 후입선출(LIFO, last-in first-out) 자료 구조라고도 한다. 스택이 지원하는 연산 목록 size() - 현재 스택에 들어 있는 데이터 원소의 수를 구한다. isEmpty() - 현재 스택이 비어있는지 판단한다. push(x) - 데이터 원소 x를 스택에 추가한다. pop() - 스택의 맨 위에 저장된 데이터 원소를 제거하면서 반환한다. peek() - 스택의 맨 위에 저장된 데이터 원소를 반환한다. ..

양방향 연결 리스트(Doubly Linked Lists)

양방향 연결리스트와 연결리스트의 차이 연결리스트는 앞의 노드가 뒤쪽으로만 연결이 되었다면, 양방향 연결리스트는 앞과 뒤 양쪽으로 연결이 되어 노드의 이동이 더 자유롭다. 노드가 앞뒤로 연결되어 있기 때문에 head와 tail 모두 dommy 노드가 존재한다. 장점 양방향 연결구조로 노드를 탐색하는 방향이 양방향이라는 장점이 있다. 단방향 연결리스트는 맨 마지막에 위치한 데이터를 탐색하기 위해서 head에서 부터 시작하여 순차적으로 방문하며 탐색하지만, 이중 연결리스트는 그럴 필요가 없다. 리스트 처음과 끝에 dummy node를 존재시키면, 데이터를 담고 있는 node들은 모두 같은 모양이 되어 코드 작성에 용이하다. 단점 단방향 연결리스트에비해 링크를 더 갖고 있기때문에 링크를 나타내기 위한 메모리 사..

연결 리스트 (Linked Lists)

연결리스트와 선형 배열의 차이 데이터 원소등를 순서를 지어 늘언호는 점에서는 연결리스트와 선형배열이 비슷하지만, 데이터 원소들을 늘어놓는 방식에서 차이가 있다. 선형 배열은 번호가 붙여진 칸에 원소들을 채워넣는 방식인 반면, 연결리스트는 각 원소들을 줄줄이 엮어서 관리하는 방식이다. 연결리스트 장점 연결리스트에서는 원소들이 링크(Link)라고 부르는 고리로 연결되어 있는데, 67에서 34를 가리키는 고리를 자르고, 58로 이어붙이면서 34를 삭제하거나, 67이 34가 아닌 다른 원소에 연결하여 삽입하는것이 배열보다 빠른시간 내에 처리 할 수 있다. 이러한 이점 때문에, 원소의 삽입/삭제가 번번히 일어나는 응용에서는 연결리스트가 많이 이용된다. 단점 원소의 삽입과 삭제가 용이하다는 장점도 있지만, 연결리스..

선형 배열(Linear Array)

선형 배열(Linear Arrays) 선형 배열은 데이터들이 선처럼 일렬로 늘어선 형태를 말한다. 보통 프로그래밍에서 배열(array) 라고 하면 같은 종류의 데이터가 줄지어 늘어서 있는 것을 말하는데, Python에서는 서로 다른 종류의 데이터 또한 줄세울 수 있는 list 라는 데이터형이 있다. Python 리스트에 활용할 수 있는 연산들 리스트의 인덱싱 파이썬의 리스트의 시작은 0부터이다. 리스트의 순서대로 요소를 출력할 수 있고, 또 -를 붙여 뒤에부터 요소를 출력할 수 있다. L = ['a', 'b', 'c'] print(L[0]) # a print(L[-2]) # b 리스트의 슬라이싱 문자열과 같이 리스트도 슬라이싱 기법을 쓸 수 있다. 리스트명[a:b]를 하게되면 a이상 b미만을 출력한다. ..