자료구조, 알고리즘, 배열, 스택, 큐

자료구조

대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미

대표적인 자료구조 : 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등

---

알고리즘 

어떤 문제에 대해, 특정한 '입력'을 넣으면, 원하는 '출력'을 얻을 수 있도록 만드는 프로그래밍

얼마나 시간이 걸리느냐, 얼마나 메모리를 차지하느냐가 주 요소

따라서 코드를 짰을 때 얼마나 메모리를 차지하고 얼마나 시간이 걸렸는지 알고 있어야 한다.

---

자료구조와 알고리즘이 중요한 이유 

어떤 자료구조와 알고리즘을 쓰느냐에 따라, 성능이 천지차이이다.

---

배열(Array)

데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조

유사한 데이터를 연결된 데이터 공간에 넣을 수 있다.

파이썬에서는 리스트 타입이 배열의 기능을 제공한다.

---

배열이 필요한 이유 

같은 종류의 데이터를 효율적으로 관리하기 위해서, 같은 종류의 데이터를 순차적으로 저장하기 위해서이다.

 

장점 : 인덱스 번호가 있어서 데이터를 찾기가 편하다.

단점 : 추가 / 삭제가 쉽지 않다. 미리 최대 길이를 지정해야 한다.

 

그러나 파이썬의 배열은 C의 배열과 다르다.

C언어의 배열은 미리 사이즈를 정해서 만든다.

파이썬의 리스트는 미리 사이즈를 지정하지 않는다.

country = 'US'
country = country + 'A'
print(country)
# USA

---

전체 이름 안에 M이라는 대문자가 몇 번 들어가 있는지 측정하기

m_count = 0
for data in dataset:
    for index in range(len(data)):
        print(data[index])
# 개별적인 문자 하나를 가져온다.

 

m_count = 0
for data in dataset:
    for index in range(len(data)):
        if data[index] == 'M':
            m_count += 1

---

큐 (Queue)

가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 

• 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일
• FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대

---

알아둘 용어

Enqueue : 큐에 데이터를 넣는 기능

Dequeue : 큐에서 데이터를 꺼내는 기능

---

queue 라이브러리

• queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공
  
  1. Queue(): 가장 일반적인 큐 자료 구조
  2. LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨)
  3. PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

---

Queue()로 기본적인 큐 만들기 (FIFO)

import queue
data_queue = queue.Queue()
# 라이브러리.클래스

data_queue.put("swc")
data_queue.put(1)

data_queue.qsize()
# 2

data_queue.get()
# swc

data_queue.qsize()
# 1

data_queue.get()
# 1

data_queue.qsize()
# 0

---

LifoQueue() 로 큐 만들기 (Last-in-First-Out)

import queue
data_queue = queue.LifoQueue()

data_queue.put("swc")
data_queue.put(1)

# 마지막에 넣은 것이 먼저 출력된다.
data_queue.get()
# 1

data_queue.get()
# swc

---

PriorityQueue() 로 큐 만들기

우선순위큐

import queue
data_queue = queue.PriorityQueue()

# 데이터를 넣을 때 우선순위도 매겨서 넣어야 한다.
data_queue.put((10, "korea"))
data_queue.put((5, 1))
data_queue.put((15, "Disaster"))

data_queue.qsize()
# 3

data_queue.get()
# (5, 1) 
# 우선순위가 높은 1이 먼저 출력된다.

data_queue.get()
# (10, "korea")

---

어디에 큐가 많이 쓰일까?

멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨 (운영체제 참조)

큐의 경우에는 장단점 보다는 (특별히 언급되는 장단점이 없음), 큐의 활용 예로 프로세스 스케쥴링 방식을 함께 이해해두는 것이 좋음

---

문제 : 리스트로 큐를 다루는 enqueue, dequeue 만들기

queue_list = list()

def enqueue(data):
    queue_list.append(data)

def dequeue():
    data = queue_list[0]
    del queue_list[0] # 데이터 삭제
    return data

 

for index in range(10):
    enqueue(index)

len(queue_list)
# 10

dequeue()
# 0
dequeue()
# 1

---

스택 (Stack)

데이터를 제한적으로 접근할 수 있는 구조

한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조

가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조

 

• 큐: FIFO 정책
• 스택: LIFO 정책

---

스택 구조

스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름

• LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
• FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책

---

대표적인 스택의 활용

• 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• 컴퓨터 프로세스 스택에 많이 쓰인다.

---

주요 기능

• push(): 데이터를 스택에 넣기
• pop(): 데이터를 스택에서 꺼내기

def recursive(data):
    if data < 0:
        print("ended")
    else :
        print(data)
        recursive(data - 1)
        print("returned", data)

recursive(4)
# 4
# 3
# 2
# 1
# 0
# ended
# returned 0
# returned 1
# returned 2
# returned 3
# returned 4

 

스택과 마찬가지로 재귀함수도 이렇게 쌓여진다.

맨위의 함수가 끝나면 맨위의 함수부터 삭제가 된다.

함수 위의 함수가 호출되면 스택과 같은 구조로 쌓인다!

returned 4 가 되면 함수가 끝이 난다.

 

 

장점

• 구조가 단순해서, 구현이 쉽다. (위에서부터 데이터를 꺼내는 방식이므로)
• 데이터 저장/읽기 속도가 빠르다.

 

단점 (일반적인 스택 구현시) 

• 데이터 최대 갯수를 미리 정해야 한다. (최대로 쌓아질 스택을 확보를 해놓아야 한다.)
  • 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능함
    
    
• 저장 공간의 낭비가 발생할 수 있음
  • 미리 최대 갯수만큼 저장 공간을 확보해야 함

 

스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적임. 이 경우, 위에서 열거한 단점이 있을 수 있음

 

---

파이썬 리스트 기능에서 제공하는 메서드로 스택 사용해보기

append(push), pop 이용

 

data_stack = list()

data_stack.append(1)
data_stack.append(2)
print(data_stack)
# [1,2]
data_stack.pop()
# 2

---

스택 연습 : pop, push 함수 사용하지 않고, 기능 구현해보기

stack_list = list()

def push(data):
    stack_list.append(data)

def pop():
    data = stack_list[-1] # 인덱스 맨 뒤에거 지칭하는 법
    del stack_list[-1]
    return(data)

for index in range(10):
    push(index)

pop()
# 9