[자료구조] 자료구조 이론 / 배열 / 큐

자료구조 : 데이터 구조, data structure

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

대표적은 자료구조

- 배열, 스택, 큐, 링크드리스트, 해쉬테이블, 힙 등

 

알고리즘 : 어떤 문제를 풀기위한 절차/방법

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

 

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

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

 

 

01. 배열 (Array)

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

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

 

1. 배열은 왜 필요할까?

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

같은 종류의 데이터를 순차적으로 저장

 

장점

- 빠른 접근 가능

     - 첫 데이터의 위치에서 상대적인 위치로 데이터 접근(인덱스 번호로 접근)

 

단점

- 데이터 추가/삭제의 어려움(가운데 데이터를 추가하거나 삭제 한 경우 뒤의 데이터들이 영향(인덱스 변경)을 받을 수 있다.

삭제 한 경우는 뒤에 데이터들을 당겨야 되고 추가한 경우는 새로운 공간을 위해 배열을 새로 만들어 줘야한다.)

     - 미리 최대 길이를 지정해야 함

 

C 언어인 경우 배열을 사용할 때 미리 최대 길이를 지정해주어야 하지만 파이썬은 리스트로 배열 구현 가능해서 따로 최대 길이를 지정해주지 않아도 된다.

 

 

02.큐 (Queue)

1. 큐 구조

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

- 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일

- FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대이다.

 

2. 알아둘 용어

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

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

 

3. 파이썬 queue 라이브러리 활용해서 큐 자료 구조 사용.

Queue(), LifoQueue(), PriorityQueue() 등이 있다.

일반적인 큐, 나중에 넣은 것을 먼저 빼는 큐, 데이터 마다 우선 순위를 넣어주는 큐(우선순위가 높은 순(번호가 낮은 순)으로 추출)

 

 

참고 : 큐가 많이 쓰이는 곳

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

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