알고리즘 / 기술면접 스터디 공부 - 자료구조 이론(1)

1. 배열(Array) 

(1) 배열(Array) 이란 ?

- 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 만들어진 구조

- 파이썬에서는 리스트 타입이 배열 기능을 제공함

 

(2) 배열의 장단점

- 장점 : 같은 종류의 데이터를 효율적으로 저장할 수 있음, 순차적으로 접근 가능

- 단점 : 연관된 데이터의 추가 및 삭제가 어려움, 미리 최대의 길이를 지정해야 함

 

 

2. 큐(Queue)

 

(1) 큐 구조란 ?

- 줄을 서는 행위와 유사

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

  (FIFO, LIFO) 방식으로 스택과 꺼내는 순서와 반대임 !

- 멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현하기 위해 (운영체제에서)

 

LIFO 원리

 

(2) 알아둘 용어

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

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

 

(3) 파이썬 queue 라이브러리 활용해서 큐 자료구조 사용하기

- queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공

 

(3-1) Queue()로 큐 만들기

import queue

data_queue = queue.Queue()

#데이터를 넣음
data_queue.put("funcoding")
data_queue.put(1)

#데이터 사이즈 확인
data_queue.qsize()

data_queue.get() #funcoding이 출력됨
data_queue.qsize() #1이 출력됨

 

(3-2) LifoQueue()로 큐 만들기

import queue

data_queue = queue.LifoQueue()
data_queue.put("funcoding")
data_queue.put(1)

data_queue.qsize #2가 출력됨
data_queue.get() #1이 출력됨

 

(3-3) PriorityQueue()로 큐 만들기

- 우선순위에 따라서 뽑아냄

import queue

data_queue = queue.PriorityQueue()
data_queue.put((10,"korea")) #데이터가 하나인데, 튜플 형태로 들어감
data_queue.put((5,1))
data_queue.put((15,"china"))

data_queue.qsize() #3이 출력됨
data_queue.get() #(5,1)이 출력됨
data_queue.get() #(10,"korea")이 출력됨

 

 

3. 스택 (Stack)

 

(1) 스택 구조란 ?

- 데이터를 제한적으로 접근할 수 있음 (한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조)

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

  ☞ 큐 : FIFO 정책

  ☞ 스택 : LIFO 정책 (ex. 책을 위로 쌓았을 때, 가장 먼저 책을 꺼낼 수 있음)

 

 

(2) 알아둘 용어

- push() : 데이터를 스택에 넣는 기능

- pop() : 데이터를 스택에서 꺼내는 기능

 

 

(3) 스택의 장단점

- 장점 : 구조가 단순해서, 구현이 쉬움

- 단점 : 데이터의 최대 갯수를 미리 정해야 함, 저장 공간 낭비가 발생할 수 있음

 

 

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

data_stack = list()

data_stack.append(1)
data_stack.append(2)


data_stack   #[1, 2]가 출력됨
data_stack.pop() #2가 출력됨

 

(5) 리스트 변수로 스택을 다루는 pop, push 기능 구현

stack_list = list()

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

def pop():
    data = stack_list[-1]
    del stack_list[-1]
    return data

 

 

4. 링크드 리스트 (Linked List)

(1) 링크드 리스트란 ?

- 연결 리스트라고도 함
- 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
- 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조

- 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원

 

 

 

 

(2) 알아둘 용어

- 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성
- 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

 

 

(3) 간단한 링크드 링스트 예

- 보통 파이썬에서 링크드 리스트 구현 시, 파이썬 클래스를 활용함 !

 

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

 

Node와 Node 연결하기 (포인터 활용)

node1 = Node(1)
node2 = Node(2)
node1.next = node2
head = node1

 

링크드 리스트로 데이터 추가하기

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

def add(data):
    node = head
    while node.next:
        node = node.next
    node.next = Node(data)

 

(4) 링크드 리스트의 장단점

- 장점 : 미리 데이터 공간을 미리 할당하지 않아도 됨

- 단점 : 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음

연결 정보를 찾는 시간이 필요함으로 접근 속도가 느림

중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요