자료구조 - 배열, 연결리스트, 스택, 큐 정리

자료구조에 대해 알아보자.

배열

• 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 순서대로 저장하는 자료구조
• 데이터 조회에서 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 : 팰린드롬인지 확인하는 함수는 어떻게 만들까?

1. 연결리스트를 리스트로 만든 후,
2. 리스트의 첫번째 요소와 마지막 요소를 꺼내서 같은 지를 확인한다.

#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