알고리즘/기술면접 완전 정복 올인원 패키지 Online.
배열
데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
같은 종류의 데이터를 효율적으로 관리하고 순차적으로 저장하기 위해 사용한다.
장단점
-
장점
데이터에 빠르게 접근이 가능하다. -
단점
데이터의 추가/삭제에 있어서 메모리 낭비 등의 고려할 점이 있다.
미리 최대 길이를 정해놔야한다.
파이썬과 배열
파이썬 리스트를 활용한다.
# 1차원 배열
data = [1, 2, 3, 4, 5]
# 2차원 배열
data = [1, 2][3, 4][5, 6]
print(data[1][1]) # 4
큐
구조
가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조(FIFO, First In First Out)
용어
-
Enqueue
데이터를 큐에 넣는 기능 -
Dequeue
데이터를 큐에서 꺼내는 기능
파이썬과 큐
- FIFO Queue
import queue
data_queue = queue.Queue()
data_queue.put('insert data')
data_queue.get()
-
queue.Queue()
큐 선언 -
.put(data)
enqueue -
.get()
dequeue -
.qsize()
큐의 사이즈를 반환한다.
- LIFO Queue
import queue
data_queue = queue.LifoQueue()
Last In First Out의 구조를 가진 큐를 선언한다.
- Priority Queue
우선순위와 함께 데이터를 넣어서 우선순위에 따라서 데이터를 추출한다.
import queue
data_queue = queue.PriorityQueue()
data_queue.put((10, "apple"))
data_queue.put((3, "banana"))
데이터를 넣을 때 tuple((priority, data))의 형태로 넣는다.
구현해보기
queue_list = list()
def enqueue(data):
queue_list.append(data)
def dequeue():
data = queue_list[0]
del queue_list[0]
return data자바스크립트와 큐
class Queue {
constructor() {
this._arr = [];
}
enqueue(data) {
this._arr.push(data);
}
dequeue() {
return this._arr.shift();
}
}
스택
구조
데이터를 제한적으로 접근할 수 있는 구조
한쪽 끝에서만 자료를 넣고 뺄 수 있다. (LIFO, Last In First Out)
용어
-
push()
데이터를 넣기 -
pop()
데이터를 꺼내기
장단점
- 장점
- 구조가 단순해서 구현이 쉽다.
- 데이터의 저장/읽기 속도가 빠르다
- 단점(일반적인 스택)
- 데이터의 최대 갯수를 미리 정해야한다.
파이썬의 경우 재귀함수 호출이 1000번까지만 가능하다.
-> 저장 공간의 낭비가 발생할 수 있다.
- 데이터의 최대 갯수를 미리 정해야한다.
파이썬과 스택
파이썬 리스트 기능에서 제공하는 append()와 pop()을 사용하여 스택의 push와 pop을 사용할 수 있다.
구현해보기
stack_list = list()
def push(data):
stack_list.append(data)
def pop():
data = stack_list[-1]
del stack_list[-1]
return data
자바스크립트와 스택
class Stack {
constuctor() {
this._arr = [];;
}
push(data) {
this._arr.push(data);
}
pop() {
return this._arr.pop();
}
peek() {
return this._arr[this._arr.length - 1];
}
}
링크드 리스트
구조
떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조
C언어에서는 주요한 데이터 구조이지만, 파이썬에서는 리스트 타입이 링크드 리스트의 기능을 모두 지원한다.
배열이 공간을 미리 예약해두고 사용해야하는 단점을 보완할 수 있다.
용어
-
노드
데이터 저장 단위(데이터값, 포인터)로 구성 -
포인터
다음 데이터를 가르키는 주소값이다. 연결 정보를 가지고 있는 공간.
파이썬과 링크드 리스트
파이썬 클래스를 활용하여 노드를 구성해야한다.
# 노드 만들기
class Node:
def __init__(self, data):
self.data = data
self.next = none
# 노드 연결하기
node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1
데이터를 추가하기 위해서는 마지막 노드를 찾고, 마지막 노드의 next에 data를 추가해주면 된다.
# 데이터 추가
def add(data):
node = head
# 마지막 노드 찾기
while node.next:
node = node.next
node.next = Node(data)
데이터 출력(검색)하기
# 데이터 출력
node = head
while node.next:
print(node.data)
node = node.next
print(node.data)
장단점
-
장점
데이터 공간을 미리 할당하지 않아도 된다. -
단점
- 연결을 위한 데이터 공간(포인터의 공간)이 별도로 필요하다.
- 접근 속도가 느리다. (다음 노드를 계속 찾아야한다.)
- 중간 데이터 삭제 시 데이터의 연결을 재구성해야하는 부가적인 작업이 필요하다.
복잡한 기능 구현 - 중간 데이터 추가
위의 사진을 구현하기 위해서는 먼저 data가 12인지 판별하고, 찾으면 해당 노드의 next를 넣으려는 데이터로 다시 설정하고, 넣으려는 데이터의 next에 99를 설정하면 된다.
node = head
search = true
while search:
if node.data == 12:
search = false
else:
node = node.next
node_next = node.next
node.next = new_node
new_node.next= node_next
파이썬으로 구현하기
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
# 노드 관리
class NodeMgmt:
def __init__(self, data):
self.head = Node(data)
def add(self, datt):
if self.head == '':
self.head = Node(data)
else:
node = self.head
while node.next:
node = node.next
node.next = Node(data)
# 순회
def desc(self):
node = self.head
while node:
print(node.data)
node = node.next복잡한 기능 구현 - 데이터 삭제
-
첫번째 노드 삭제
첫번째 노드를 삭제하면 그 노드의 next를 head로 만들어주는 작업이 필요하다. -
마지막 노드 삭제
마지막 노드를 삭제하면 그 노드를 가리키고 있던 next를null로 만들어주는 작업이 필요하다. -
중간 노드 삭제
노드를 삭제하고 그 노드를 가리키고 있던 prev.next를 삭제된 노드의 next와 연결시켜주는 작업이 필요하다.
def delete(self, data):
# 첫번째
if self.head.data == node:
temp = self.head
self.head = self.head.next
del temp
# 두/세번째
else:
node = self.head
while node.next:
if node.next.data == data:
# 삭제할 노드
temp = node.next
node.next = node.next.next
del temp
else:
node = node.next더블 링크드 리스트
Node가 (이전 데이터 주소, 데이터, 다음 데이터 주소) 의 형태를 띈다.
데이터를 순회할 때, 뒤에서부터 데이터를 찾고 싶을 때 이런 구조로 생기면 가능하다.
class Node:
def __init__(self, data, prev=None, next=None):
self.prev = prev
self.data = data
selr.next = next
class NodeMgnt:
def __init__(self, data):
self.head = Node(data)
self.tail = self.head
def insert(self, data):
if self.head == None:
self.head = Node(data)
self.tail = self.head
else:
node = self.head
while node.next:
node = node.next
new = Node(data)
node.next = new
new.prev = node
self.tail = new
def desc(self):
node = self.head
while node:
print(node.data)
node = node.next
# 앞에서부터 검색
def search_from_head(self, data):
if self.head == none:
return false
node = self.head
while node:
if node.data == data
return node
else:
node = node.next
return false
# 뒤에서부터 검색
def search_from_tail(self, data):
if self.tail == none:
return false
node = self.tail
while node:
if node.data == data
return node
else:
node = node.prev
return false
# 중간 데이터 추가
def insert_before(self, data, before_data):
if self.head == none:
self.head = Node(data)
return true
else:
node = self.tail
while node.datt != before_data:
node = node.prev
if node == none:
return false
new = Node(data)
before_new = node.prev
before_new.next = new
new.prev = before_new
new.next = node
node.prev = new