반응형
자료구조에 대해 알아보자.배열
- 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 순서대로 저장하는 자료구조
- 데이터 조회에서 O(1)의 시간 복잡도를 가진다.
장점
- 연속된 메모리 공간을 사용하므로 처음 데이터의 주소를 알면 나머지도 쉽게 찾을 수 있다.
단점
- 크기가 고정되어 추가/삭제에 제약이 있다.
연결리스트
- 각각의 데이터가 메모리 공간 상에 고유한 노드로 존재하며, 해당 노드에 앞과 뒤의 메모리 주소를 기억하고 있는 형태
- 즉, 노드들이 서로 연결되어 있는 구조
- 데이터 조회 시 순차적으로 탐색하기 때문에 O(N)의 시간 복잡도
- 데이터 추가와 삭제에는 O(1)의 시간 복잡도
Array vs Linked List
- 배열 (Array): 파이썬의 리스트. 접근 쉬움, 삽입 어려움. (파이썬의 리스트)
- 연결리스트: 직접 구현. 접근 어려움, 삽입 쉬움. 상자랑 화살표 포함해서 노드라고 함
구현
# structures.py
'''
O -> O -> O -> O -> O -> O -> O 형태이다.
'''
class ListNode:
def __init__(self, val=0, next=None):
self.val = val # 상자
self.next = next # 화살표
class LinkedList:
def __init__(self):
self.head = None # 제일 첫 요소
def append(self, val):
if not self.head: # 헤드가 없다면
self.head = ListNode(val, None) # 헤드 노드를 하나 만들고 다음거는 없다
return
node = self.head # 제일 앞을 노드로 설정
while node.next: # 다음 요소가 있을 동안 (없을 때 까지)
node = node.next # 노드를 다음걸로 업데이트
node.next = ListNode(val, None) # 다음 요소 없으면 새로 만들기!
예제
💡 주어진 리스트가 팰린드롬인지 판별하는 프로그램을 작성하세요.
(팰린드롬 : 읽는 순서가 바뀌어도 똑같은 것)
예시1) [1, 2, 2, 1] ⇒ True
예시2) [1, 2] ⇒ FalseContent
isPalindrome : 팰린드롬인지 확인하는 함수는 어떻게 만들까?
- 연결리스트를 리스트로 만든 후,
- 리스트의 첫번째 요소와 마지막 요소를 꺼내서 같은 지를 확인한다.
#prac.py
def isPalindrome(ln): # 연결리스트를 전달받아서
arr = []
head = ln.head #헤드를 꺼내
if not head: #헤드가 없으면 비어있으므로
return True
# 헤드가 있으면
node = head
while node: # 노드를 옮겨가며 연결리스트의 모든 값을 리스트에 넣는다.
arr.append(node.val)
node = node.next
while len(arr) > 1: # 길이가 1이 될 때 까지
# 첫 번째 요소와 마지막 요소를 꺼낸다.
first = arr.pop(0)
last = arr.pop()
if first != last: # 다르면 팰린드롬이 아님
return False
return True
파이썬 배열로 활용한다면
def isPelindrome(arr):
if arr==arr[-1::]:
return True
else:
return False
(배열이 파이썬에서 구현하기는 더 쉽다)
위에서 만든 펠린드롬 검사 함수를 test.py에서 사용하기
# test.py
from structures import LinkedList
from prac import isPalindrome
l1 = LinkedList() # 1->2->2->1
for num in [1, 2, 2, 1]:
l1.append(num)
l2 = LinkedList()
for num in [1, 2]:
l2.append(num)
assert isPalindrome(l1) # assert 뒤의 값을 true로 확언하겠다 (true가 맞는지 test하는 것)
assert not isPalindrome(l2) # assert not 뒤의 값을 false로 확언하겠다 (false 가 맞는지 test하는 것)
스택(Stack)
- 후입선출의 원칙을 따르는 자료구조로 차곡차곡 쌓아올리는(Stack) 것
- 삽입과 삭제시에 O(1), 탐색에는 O(n)의 시간 복잡도
사용 예
- 브라우저의 뒤로가기
- 실행 취소 (Ctrl + z)
- 재귀 함수
- 역순 문자열 (문자열 거꾸로 뒤집기)
구현
# structures.py
'''
연결리스트를 응용해서, 대신 제일 앞이 아니라 제일 위여야 하므로 가장 처음 걸 top으로 한다.
O
↓
O
↓
O
↓
O
↓
O
형태가 된다.
'''
class Node:
def __init__(self, val = 0, next = None):
self.val = val #상자
self.next = next
class Stack:
def __init__(self):
self.top = None
'''
스택은 쌓으므로 append가 아닌 push,
연결리스트와 다른 점 : 새로 들어온 게 항상 top
'''
def push(self, val):
# node = Node(val,None) : 새로 들어오면
# node.next = self.top : 기존에 가장 위에(top)였던 애를 다음 노드로
# self.top = node : 그리고 지금 새로 만든 노드를 top으로
# 결국 val,next 에서 top 이었던 것을 next로 만드는 것이므로 한줄로 표현하면
self.top = Node(val,self.top)
def pop(self):
if not self.top: # 없을 때
return None # None을 넣어준다
# pop 이므로 top 을 위에서 두번째걸로, 즉 다음걸로 바꿔줘야 함
node = self.top
self.top = node.next
# 그리고 선택된 노드(아직 제일 위에거이지만 top은 다음으로 넘겨준)를 반환한다.
return node.val
def is_empty(self):
return self.top is None # pop 에서 넣어준 None 이 리턴되었다면 -> 없다면!
# test.py
def test_stack():
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
stack.push(5)
'''
현재 스택
5
4
3
2
1
'''
# 스택에서 pop 하면 제일 위에 거 (마지막 거이기 때문에)
assert stack.pop() == 5
assert stack.pop() == 4
assert stack.pop() == 3
assert stack.pop() == 2
assert stack.pop() == 1
assert stack.pop() is None
assert stack.is_empty()예제
💡 '(', ')', '{', '}', '[' 및 ']' 만 포함된 문자열이 주어졌을 때 입력 문자열이 유효한지 확인하는 프로그램을 작성하세요.- 열린 괄호가 제대로 닫혔는지 확인 -> 내가 연 순서의 반대로 닫으면 됨 ex) ({[]})
- 여는 괄호가 나올 때 마다 스택에 담고, 여는 게 끝나면 스택 제일 위부터 꺼내서 짝을 비교하면(딕셔너리 사용) 제대로 닫혔는지 확인할 수 있다.
- 실제 문제풀이 할 때는 리스트를 스택처럼 써서 푼다.
#prac.py
def test_problem_stack(s):
pair = {
'}': '{',
')': '(',
']': '[',
}
opener = "({["
stack = []
for char in s:
if char in opener: # 여는 거일 때
stack.append(char)
else: # 닫는 거일 때
if not stack: # 여는 게 끝났는데 닫는 게 남아있다면
return False
top = stack.pop()
if pair[char] != top:
return False
return not stack
큐 (Queue)
- 선형 큐, 우선순위 큐, 원형 큐, 덱 4가지로 나눠서 살펴보겠다.
1. 선형 큐(Linear Queue)
- 한 쪽에서는 데이터 삽입, 다른 한 쪽에서는 데이터의 삭제만 가능한, 선입선출 원칙을 따르는 자료구조
- 삽입과 삭제에는 O(1), 탐색에는 O(n) 의 시간 복잡도
구현
- 스택처럼 쌓기 때문에 넣을 땐 똑같지만
- 뺄 때는 맨 뒤에서, 즉 처음 넣은 것을 뺀다. front를 빼는 게 아니다.
# structures.py
'''
노드 클래스는 연결리스트, 스택과 동일하다.
class Node:
def __init__(self, val=0, next=None):
self.val = val # 상자
self.next = next # 화살표
'''
'''
가장 앞에 있는 게 중요하므로 front
'''
class Queue:
def __init__(self):
self.front = None
def push(self, value):
if not self.front: # 맨 앞에가 없으면
self.front = Node(value) # 노드 만들어서 front로
return
#맨 앞이 있으면
node = self.front # 제일 앞 노드를 잡아서
while node.next: # 다음 노드가 있는 동안 (다음 노드가 없을 때 까지)
node = node.next # 다음 노드를 계속 잡는다.
'''
다음 노드가 없으면 새로 상자를 만들어서 들어온 value를 대입,
그리고 다음 노드로 가리키게 해준다(화살표를 만든다. next는 화살표를 의미함)
'''
node.next = Node(value)
def pop(self):
if not self.front: # 꺼낼 게 없으면
return None
node = self.front # 꺼낼 게 있으면
self.front = self.front.next # 맨 앞부터 (처음 넣은 것 부터) 꺼낸다.
return node.val
def is_empty(self):
return self.front is None
# test.py
def test_queue():
queue = Queue()
queue.push(1)
queue.push(2)
queue.push(3)
queue.push(4)
queue.push(5)
assert queue.pop() == 1
assert queue.pop() == 2
assert queue.pop() == 3
assert queue.pop() == 4
assert queue.pop() == 5
assert queue.pop() is None
assert queue.is_empty()2. 우선순위 큐
- 우선순위 큐의 각 요소는 값과 우선순위, 총 2개의 데이터를 가지고 있습니다.
- 따라서 선형 큐 (Linear Queue)와는 달리 우선순위가 높은 요소일수록 먼저 삭제되는 특징을 가지고 있으며 우선순위가 같은 데이터일 경우 삽입순서를 따릅니다.
- 삽입 및 삭제 시 우선순위에 따라 요소들을 정렬 해야하기 때문에 주로 힙 (Heap)이라는 자료구조로 구현
- 우선순위 큐는 어떻게 구현하느냐에 따라 시간 복잡도가 달라지지만 힙 (Heap)을 기준으로 한다면 삽입과 삭제에는 O(logn), 우선순위가 가장 높은 요소를 탐색할 때는 O(1)만큼의 시간 복잡도를 가진다.
3. 원형 큐 (Circular Queue)
- 원형 큐는 선형 큐 (Linear Queue)의 단점을 보완하기 위해 나왔습니다.
- 큐는 사이즈가 고정되어있고 데이터의 삽입과 삭제시 나머지 요소들은 이동하지 않습니다.
- 따라서 데이터의 삽입과 삭제가 반복되면 언젠가 Rear는 큐의 마지막 인덱스를 가르키게 되고 이전에 삭제 작업을 진행하여 앞에 빈 공간이 있더라도 활용하지 못하게 됩니다.
- 따라서 선형 큐는 빈 공간을 활용하기 위해 현재 요소들을 앞으로 재배치하는 별도의 작업이 필요합니다.
- 하지만 원형큐의 경우 Front와 Rear가 아래 그림처럼 순환하기 때문에 빈 공간을 사용하기 위한 별도의 작업이 필요하지 않습니다.
- 위의 사진에서 Front와 Rear의 움직임을 보면 Front와 Rear가 계속해서 돌고 있는 모습을 볼 수 있습니다.
- 이러한 움직임을 만들어내기 위해서 원형 큐에서는 Enqueue 및 Dequeue시에 아래와 같은 작업을 합니다.
function enqueue() {
// ...
rear = (rear + 1) % queue_size;
}
function dequeue() {
// ...
front = (front + 1) % queue_size;
}- 예를 들어, 큐의 전체 사이즈가 5이고 현재 Rear가 마지막 인덱스인 4를 가르키고 있다고 가정해보겠습니다.
- 여기서 Enqueue를 하게되면 Rear의 인덱스는 5가 될텐데 여기에 큐의 전체사이즈를 나눈 나머지를 구합니다.
- 5 % 5 = 0이므로 이 값을 Rear에 할당하여 인덱스가 다시 0을 가르킬 수 있도록 합니다.
- 이렇게 하면 정렬과정 없이 Front와 Rear가 순환하는 형태를 만들 수 있습니다.
4. 덱 (Deque, Double-ended Queue)
- 덱은 큐 (Queue) 2개를 겹쳐 놓은 것과 같기 때문에 Double ended Queue라고 부르며 Deque이라는 명칭은 이를 축약형으로 부르는 것입니다.
- 이 자료구조는 이름처럼 양쪽에서 데이터의 입, 출력이 모두 가능한 자료구조입니다.
- JS에서는 배열의 내장메소드로 모두 구현되어있으며
- 스택, 큐와 마찬가지로 front와 rear라는 포인터가 있으며 이들은 각각 가장 앞, 뒤에 있는 데이터를 가르킵니다.
- 다만, 스택과 큐의 Rear는 다음 요소가 삽입 될 위치를 가르키는 반면
- 덱의 Rear는 마지막 요소를 가리키고 있게 됩니다.
- 스택, 큐와 같이 데이터의 삽입과 삭제에 O(1)의 시간 복잡도를 가집니다.
예제 (deque)
💡 1부터 N까지 차례대로 줄을 섰을 때, 맨 앞에 선 사람만 들여보내주고 그 다음 순서인 사람은 제일 뒤로 보내는 특이한 줄서기가 있습니다.
예를 들어 N=6인 경우, 123456 이 순서대로 줄을 서있을 것입니다. 이때 제일 먼저 1이 입장하고 남은 순서는 23456이 됩니다. 2는 두 번째 순서이므로 제일 뒤로 보내서 34562가 됩니다. 다시 3이 입장하여 4562가 되고, 4가 두 번째 순서이므로 5624가 되빈다. 5가 입장하고 246, 2가 입장하고 64, 6이 입장하여 4, 마지막으로 4가 입장하게 됩니다.
N이 주어질 때 제일 마지막으로 입장하는 숫자를 계산하는 프로그램을 작성하세요.# prac.py
from collections import deque
def test_problem_queue(n):
deq = deque([i for i in range(1, num + 1)])
while len(deq) > 1: # 요소가 2개 이상 남아있는 동안 (하나 남을 때 까지)
deq.popleft() # deque의 앞에서 꺼낸다.
deq.append(deq.popleft()) # 두번째는 앞에서 꺼내서 맨뒤에 붙인다.
return deq.popleft()
# test.py
assert test_problem_queue(2) == 2
assert test_problem_queue(3) == 2
assert test_problem_queue(4) == 4
assert test_problem_queue(5) == 2
assert test_problem_queue(6) == 4
assert test_problem_queue(7) == 6
반응형
'Computer Science > 자료구조, 알고리즘' 카테고리의 다른 글
| 최단 경로 문제 - 다익스트라(Dijkstra) 알고리즘 (0) | 2024.07.11 |
|---|---|
| 동적계획법 - DP (Dynamic Programming) (0) | 2024.07.11 |
| 파이썬 - 리스트, 집합, 딕셔너리 시간복잡도 정리 (0) | 2024.07.11 |
| 자료구조 - 해시 테이블, 트리, 힙, 그래프 정리 (0) | 2024.07.10 |
| 탐색 알고리즘 - DFS와 BFS (1) | 2023.08.14 |