자료구조

• 자료구조란?
  • 자료구조란 데이터를 효율적으로 관리할 수 있는 데이터 구조를 의미한다.
  • 대표적인 자료구조
    • 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등
• 알고리즘이란?
  • 알고리즘이란 어떤 문제에 대해, 특정한 입력을 넣으면 기대하는 출력을 얻을 수 있도록 만드는 프로그래밍

어떤 자료구조와 알고리즘을 쓰느냐에 따라, 성능이 천지차이기 때문에 자료구조와 알고리즘은 매우 중요하다.

Array (배열)

• 데이터를 나열하고 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
• 파이썬에서는 리스트 타입이 배열 기능을 제공하고 있음

배열이 왜 필요할까?

같은 종류의 데이터를 순차적으로 정리해 효율적으로 관리하기 위해 사용

파이썬의 배열은 예외적으로 다양한 종류의 데이터 저장 가능

배열의 장단점

• 배열의 장점
  • 빠른 접근이 가능
    • 인덱스 번호를 통해서 바로 데이터에 접근할 수 있기 때문에 접근이 굉장히 빠르다.
• 배열의 단점
  • 미리 데이터의 최대 길이를 지정해놔야하기 때문에
  • 가변적인 데이터를 다룰 때 데이터 추가 또는 수정이 쉽지 않다.
    • 만약 배열의 길이를 추가하고 싶을 때, 배열을 하나 더 생성해 이어붙여야하는 상황이 발생할 수 있다.
    • 수정시 뒤의 데이터를 앞으로 당겨줘야한다.

Python vs C언어의 배열

#include <stdio.h>

int main(int argc, char *argv[])
{
    char country[3] = "US";
    printf("%c %c \n", country[0], country[1]);
    printf("%s\n", country[2]);
    
    return 0;
}

country='US'
print(country)

• Python의 배열은 원래 배열보다 추가적인 기능을 갖고 있다.
• 미리 배열의 길이를 지정해주지 않아도 된다.

파이썬의 배열

# 1차원 배열
data=[1,2,3,4,5]
print(data)

# 2차원 배열
data=[[1,2,3], [4,5,6], [7,8,9]]
print(data[0][0]) #1
print(data[0][1]) #2
print(data[2][0]) #7

큐 (Queue)

큐의 구조

큐란 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 자료구조이다.

• 음식점에서 줄을 서는 것과 동일
• FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과는 순서가 반대

큐의 활용

• 큐는 운영체제에서 멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현하기 위해 많이 사용됨

큐의 용어

• Enque
  • 큐에 데이터를 넣는 기능
• Deque
  • 큐에 데이터를 꺼내는 기능

파이썬 Queue 라이브러리

Queue()

import queue

# 일반적인 FIFO 정책
data_queue = queue.Queue()
data_queue.put("hi")
data_queue.put(3)
print(data_queue.qsize()) #2
print(data_queue.get())
print(data_queue.qsize()) #1

• 가장 일반적인 큐, FIFO
• put : enque
• qsize : 큐 사이즈
• get : deque

LifoQueue()

import queue

data_queue = queue.LifoQueue()
data_queue.put("hi")
print(data_queue.qsize())
data_queue.put("second")
print(data_queue.qsize())
print(data_queue.get()) #second

• LIFO (Last-In, First-Out)
  • 마지막으로 저장된 값이 가장 먼저 추출됨

PriorityQueue()

import queue

data_queue = queue.PriorityQueue()
data_queue.put((10, "ten"))
data_queue.put((3, 777))
data_queue.put((5, "five"))
print(data_queue.qsize())
print(data_queue.get()) #(3,777)

• 각 데이터마다 우선순위 번호가 부여되며, 그 번호의 순서에 따라 데이터가 추출됨
  • put(우선순위, 값)
• 우선순위가 가장 높은 값이 먼저 추출됨

Queue 구현

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

def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data

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

print(len(queue_list))
print(dequeue()) #0
print(dequeue()) #1

스택 (Stack)

• 스택은 한쪽 끝에서만 데이터를 넣거나 뺄 수 있는 구조이다
  • 데이터에 제한적으로 접근
• 가장 나중에 넣은 데이터를 가장 먼저 추출할 수 있는 데이터 구조
• 스택은 LIFO(Last-In, First-Out) 정책 또는 FILO 데이터 관리 방식을 따름
  • 큐 : FIFO

스택의 활용

• 스택은 컴퓨터 내부의 프로세스 구조의 함수 동작 방식에 활용된다

스택의 용어

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

스택의 장점과 단점

• 장점
  • 단순한 구조 -> 구현이 쉬움
  • 데이터의 저장과 읽기 속도가 빠르다
    • 빠른 프로세스 실행이 가능
• 단점 (일반적인 스택)
  • 데이터의 최대 갯수를 미리 정해야함
  • 따라서 데이터 저장 공간의 낭비가 발생할 수 있다
    • 미리 최대 갯수만큼 저장 공간을 확보해야함 (1000)

프로세스 스택 구현

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

recursive(4)

4
3
2
1
0
ended
0 returned
1 returned
2 returned
3 returned
4 returned

python 리스트 기능을 사용한 스택 구현

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

• append(push), pop 메서드 이용

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

def pop():
    data = stack_list[-1] # -1 : 맨끝 index
    print(data)
    del stack_list[-1]
    return data

for i in range(10):
    push(i)
    
pop() #9
pop() #8