💡 자료구조, 왜 공부해야 할까요? : 사용할 수 있는 컴퓨팅 리소스가 제한되어 있기 때문!
컴퓨터를 구성하는 핵심 요소는 4가지로 CPU(중앙처리장치), 메모리(주기억장치), 보조기억장치, 입출력 장치로 구성되어 있습니다. 이 핵심 요소 중 데이터는 보통 보조기억장치에 저장되는데 보조기억장치에 저장된 어떤 프로그램을 실행하면 보조기억장치에 저장된 데이터는 메모리로 옮겨지게 되고, 메모리에 로드된 데이터를 CPU가 가져와 프로그램을 실행하게 됩니다. 즉, 보조기억장치에서 주기억장치, 주기억장치에서 CPU로 데이터가 전송되는 것입니다. 이때 메모리는 프로그램의 실행 속도를 결정하게 됩니다. 메모리를 효율적으로 사용하지 않는다면 프로그램의 실행 속도는 느려질 것이고, 메모리를 효율적으로 사용한다면 프로그램은 빠르게 실행될 것입니다. 이를 위해서는 프로그램에 알맞은 자료구조를 사용하는 것이 필수적이고, 자료구조를 명확히 이해한 후 적절히 사용하는 것이 중요합니다. 파스칼을 개발한 컴퓨터 과학자 니클라우스 비르트는 '알고리즘 + 자료구조 = 프로그램'이라는 말을 남겼습니다. 프로그래밍이란 알고리즘을 잘 작성하고, 그에 맞는 자료구조를 잘 선택하는 것으로, 자료구조와 알고리즘을 잘하면 좋은 개발자로 성장할 수 있다고 합니다.
자료구조는 크게 단순 자료구조와 복합 자료구조로 나눌 수 있습니다. `단순 자료구조`는 정수(int, double, long), 실수(float), 문자(char), 문자열(string) 등이 있습니다. 이는 프로그래밍 시 사용되는 기본적인 데이터 타입입니다. `복합 자료구조`는 단순 자료구조를 기반으로 만들어낸 배열, 스택, 트리 등과 같은 자료구조를 의미합니다. 복합 자료구조는 선형 자료구조와 비선형 자료구조로 나뉘는데요, 이름에서 알 수 있듯이 선형 자료구조는 자료를 구성하는 원소를 하나씩 순차적으로 나열시킨 자료구조입니다. 즉, 선형 자료구조는 하나의 자료 뒤에 하나의 자료가 존재하는 형태입니다. 반면 비선형 자료구조는 하나의 자료 뒤에 여러 개의 자료가 존재하는 형태로 앞뒤 자료들은 1:N, N:N의 관계를 가지게 됩니다.
2️⃣ 선형 자료구조
하나의 자료 뒤에 하나의 자료가 존재하는 자료구조로, 배열, Linked List, 스택, 큐가 있습니다. 이 네 가지는 정적 자료구조와 동적 자료구조로 나눌 수 있는데, 정적 자료구조는 크기가 고정되어 있는 자료구조이고, 동적 자료구조는 크기가 바뀔 수 있는 자료구조를 뜻합니다.
1) 정적 자료구조 (Static Data Structure)
✅ 배열 (Array)
구성: element (요소) = index (순서대로 번호 부여) + value (각 요소의 값)
💡 deque란? : double-ended queue의 줄임말로, 앞과 뒤에서 데이터를 처리할 수 있는 양방향 queue 자료구조이다. deque ❘ 출처: https://blog.naver.com/sooftware/221516440423 - collections.deque 모듈을 사용한다 (dq = deque()) - append(x): deque의 마지막에 요소를 삽입 - appendleft(x): deque의 앞쪽에 요소를 삽입 - pop(): deque의 마지막에서 제거 및 반환 - popleft(): deque의 앞쪽 요소를 제거 및 반환 - rotate(): deque의 요소들을 하나씩 회전시킴
3️⃣ 비선형 자료구조
비선형 자료구조는 하나의 자료 뒤에 여러 개의 자료가 오는 형태로 트리와 그래프가 있습니다.
✅트리 (Tree)
구성
노드(Node): 데이터를 저장하는 기본 요소
간선(Edge): 노드를 연결하는 선
루트 노드(Root Node): 트리의 시작점
자식 노드(Child Node), 부모 노드(Parent Node): 계층 구조에서 연결된 노드
# input: 명령의 수 n / n줄에 걸쳐 명령이 하나씩 주어짐
# output: 명령에 맞는 수 출력
import sys
stack = [] # list를 사용해 stack 생성
n = int(sys.stdin.readline()) # 명령의 개수 n 입력 받기
for i in range(n):
command = sys.stdin.readline().split() # push의 경우 2가지를 입력받아야 하기 때문에 readline으로 받은 뒤 split
if command[0] == 'push':
stack.append(command[1])
elif command[0] == 'pop':
if len(stack) != 0: # stack이 emtpy가 아닐 때만 요소 삭제
temp = stack.pop()
print(temp)
else:
print(-1)
elif command[0] == 'size':
print(len(stack))
elif command[0] == 'empty':
if len(stack) == 0: # stack이 empty면
print(1)
else:
print(0)
elif command[0] == 'top':
if len(stack) != 0: # stack이 emtpy가 아닐 때만 top 출력
print(stack[-1])
else:
print(-1)
collections.deque를 사용해 양방향으로 데이터를 처리할 수 있는 queue를 사용
queue는 선입선출(FIFO)
# input: 명령의 수 n / n개의 명령
# output: 명령에 맞는 수 출력
from collections import deque
import sys
queue = deque() # deque 모듈을 사용해 queue 생성
n = int(sys.stdin.readline())
for i in range(n):
command = sys.stdin.readline().split()
if command[0] == 'push':
queue.append(command[1])
elif command[0] == 'pop':
if len(queue) != 0:
temp = queue.popleft() # 왼쪽에 있는 요소 pop
print(temp)
else:
print(-1)
elif command[0] == 'size':
print(len(queue))
elif command[0] == 'empty':
if len(queue) == 0:
print(1)
else:
print(0)
elif command[0] == 'front':
if len(queue) != 0:
print(queue[0]) # 제일 앞에 있는 요소 출력
else:
print(-1)
elif command[0] == 'back':
if len(queue) != 0:
print(queue[-1]) # 맨 뒤에 있는 요소 출력
else:
print(-1)
