Python 코딩테스트 01: 스택, 큐, 우선순위 큐, 트리

스택, 큐, 우선순위 큐, 트리 - 자료구조 이해하기

코딩 테스트를 준비할 때, 다양한 자료구조를 이해하는 것이 중요하다.

이번에는 스택(Stack), 큐(Queue), 우선순위 큐(Priority Queue), 트리(Tree)에 대해 쉽게 설명하고, 예시 문제를 통해 더 자세히 알아볼게요.

---

스택(Stack)

개념 설명 스택은 물건을 쌓아 올리듯 데이터를 세로로 쌓는 자료구조입니다. 이 구조에서는 쌓인 물건을 아래에서부터 꺼낼 수 없고, 가장 위에 있는 물건부터 차례로 꺼낼 수 있어요.

이를 'LIFO(Last In, First Out)'라고 하며, 마지막에 들어온 데이터가 가장 먼저 나가는 특성을 가지고 있습니다.

특징

• Push: 데이터를 스택에 넣는 연산.
• Pop: 데이터를 스택에서 꺼내는 연산.
• Top/Peek: 스택의 가장 상단에 있는 데이터를 조회하는 연산.

예시

스택의 초기 상태: []
Push 1: [1]
Push 2: [1, 2]
Pop: 2가 빠짐, [1]
Push 3: [1, 3]

예시 문제

문제: 스택을 이용하여 괄호가 올바르게 닫혀 있는지 확인하는 프로그램을 작성하세요. 입력된 괄호 문자열이 올바른지 확인하여 올바르면 True, 그렇지 않으면 False를 반환합니다.

def validate_brackets(expression):
    stack = []
    for char in expression:
        if char == '(':
            stack.append(char)
        elif char == ')':
            if not stack:
                return False
            stack.pop()
    return len(stack) == 0

# 예시 실행
print(validate_brackets("((()))"))  # True
print(validate_brackets("(()"))  # False

---

큐(Queue)

개념 설명

큐는 놀이공원에서 줄 서서 기다리는 것과 비슷한 자료구조에요.

먼저 온 사람이 먼저 놀이기구를 타듯이, 큐에서도 먼저 들어온 데이터가 먼저 나가는 구조를 가지고 있어요.

이를 'FIFO(First In, First Out)'라고 해요.

특징

• Enqueue: 데이터를 큐에 넣는 것.
• Dequeue: 데이터를 큐에서 빼는 것.

예시

큐의 초기 상태: []
Enqueue 1: [1]
Enqueue 2: [1, 2]
Dequeue: 1이 빠짐, [2]
Enqueue 3: [2, 3]

예시 문제

문제: 큐를 이용하여 프린터 작업 순서를 관리해보세요. 프린터는 먼저 요청된 작업을 먼저 처리합니다. 입력된 작업 순서대로 작업을 처리하는 프로그램을 작성하세요.

from collections import deque

def printer_queue(jobs):
    queue = deque(jobs)
    while queue:
        current_job = queue.popleft()
        print(f"Processing job: {current_job}")

# 예시 실행
printer_queue(["job1", "job2", "job3"])

---

우선순위 큐(Priority Queue)

개념 설명

우선순위 큐는 조금 특별한 큐로, 데이터를 넣을 때 각각의 중요도(우선순위)를 매기면, 높은 우선순위를 가진 데이터가 먼저 나오는 방식으로 작동해요. 예를 들어, 응급실에서 환자를 치료할 때 중증 환자를 먼저 보는 것과 비슷해요.

특징

• Enqueue: 데이터와 우선순위를 큐에 넣는 것.
• Dequeue: 우선순위가 높은 데이터를 큐에서 빼는 것.

예시

우선순위 큐의 초기 상태: []
Enqueue (2, "task2"): [(2, "task2")]
Enqueue (1, "task1"): [(1, "task1"), (2, "task2")]
Dequeue: "task1"이 빠짐, [(2, "task2")]

 

예시 문제

문제: 우선순위 큐를 이용하여 응급실의 환자 진료 순서를 관리해보세요. 응급도가 높은 환자부터 진료하는 프로그램을 작성하세요.

import heapq

def emergency_room(patients):
    heapq.heapify(patients)
    while patients:
        priority, patient = heapq.heappop(patients)
        print(f"Treating patient: {patient} with priority {priority}")

# 예시 실행
emergency_room([(2, "patient2"), (1, "patient1"), (3, "patient3")])

---

트리(Tree)

개념 설명

트리는 계층적인 구조를 표현하는 나무를 거꾸로 뒤집어 놓은 것 같은 모양의 자료구조로, 각 요소들이 노드 형태로 이루어져 있고, 노드들이 에지(간선)으로 연결되어 있는 비순환 그래픽 구조입니다.

트리는 정보를 계층적으로 관리할 때 사용됩니다.

예를 들어, 가족 관계도, 조직도, 파일 시스템 등에서 쓰일 수 있어요.

 

트리는 한 개 이상의 노드(데이터)로 구성되어 있으며, 하나의 루트 노드와 0개 이상의 자식 노드로 나뉘어져 있어요.

트리는 파일 시스템의 구조를 표현하거나, 데이터베이스에서 효율적인 검색과 정렬을 위해 사용됩니다. 또한, 의사 결정 트리(decision tree) 같은 알고리즘에서도 중요한 역할을 합니다.

 

트리는 다음과 같은 구성 요소로 이루어져 있습니다:

특징

• 루트 노드: 트리의 최상위 노드.
• 자식 노드: 루트 노드를 제외한 모든 노드.
• 부모 노드: 자식 노드를 가지는 노드.

예시

      A
     / \
    B   C
   / \
  D   E

예시 문제

문제: 트리를 이용하여 조직도를 만들고, 특정 노드에서부터 모든 자식 노드를 출력하는 프로그램을 작성하세요.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

def print_subtree(node, level=0):
    print("  " * level + node.value)
    for child in node.children:
        print_subtree(child, level + 1)

# 예시 트리 생성
root = TreeNode("CEO")
cfo = TreeNode("CFO")
cto = TreeNode("CTO")
root.children.extend([cfo, cto])
cfo.children.append(TreeNode("Finance Manager"))
cto.children.extend([TreeNode("Tech Lead"), TreeNode("Developer")])

# 서브트리 출력
print_subtree(root)

 

 

이 코드는 "트리" 자료구조를 사용하여 조직도를 나타내는 간단한 예제입니다. 트리는 부모-자식 관계로 이루어진 계층적인 구조를 가지며, 이를 통해 조직도와 같은 계층적 데이터를 효율적으로 관리할 수 있습니다.

1. TreeNode 클래스:
   • TreeNode 클래스는 트리의 각 노드를 나타냅니다. 각 노드는 value (노드의 값, 여기서는 직책의 이름)와 children (해당 노드의 자식 노드들을 저장하는 리스트)을 속성으로 가집니다.
   • 생성자 __init__에서는 노드의 값을 초기화하고, 자식 리스트를 비어 있는 리스트로 설정합니다.
2. print_subtree 함수:
   • print_subtree 함수는 특정 노드로부터 시작해 그 노드와 그 자식들을 재귀적으로 출력합니다. 이때, 각 레벨에 따라 적절한 인덴트(공백)를 추가하여 계층적인 구조를 시각적으로 표현합니다.
   • level 매개변수는 현재 노드의 깊이(레벨)를 나타내며, 이를 통해 인덴트의 크기를 조절합니다.
3. 트리 생성 및 출력:
   • root, cfo, cto와 같이 트리의 각 노드를 생성하고, 이들 사이의 부모-자식 관계를 설정합니다. 이 예에서는 CEO가 루트 노드이며 CFO와 CTO가 CEO의 자식입니다.
   • print_subtree(root)를 호출하면, CEO부터 시작하여 전체 조직도가 계층적으로 출력됩니다.

이 코드는 조직의 구조를 트리로 표현하고, 트리를 통해 각 직책과 그 하위 직책들을 출력하는 방법을 보여줍니다. 이러한 방식은 실제 조직도 뿐만 아니라 다양한 계층적 데이터를 관리하는 데 유용하게 사용될 수 있습니다.