Data Structure - Array

* 해당 포스팅은 파이썬을 이용한 알고리즘 공부를 기록합니다. 

1. 자료구조와 알고리즘이란? 

- 자료구조(= data structure): 대량의 데이터를 효율적으로 관리할 수 있는 데이터구조를 의미한다. 

- 데이터의 특성과 구조에 따라 데이터를 효율적으로 처리하기 위해 필요한 코드가 달라진다. 

 

현실 속 데이터관리의 예시) 학년/반/학번, 우편번호, 전화번호, 주민등록번호 등등 

현실 속 자료구조의 예시) 전화번호부, 사전

대표적 자료구조) 배열, 스택, 큐, Linked List, Hash Table, Heap, etc

 

 

- 알고리즘(= algorithm): 어떤 문제를 풀기 위한 절차 또는 특정 입력에 따라 원하는 출력을 얻게하는 프로그래밍

- 프로그래밍에서 어떤 문제를 풀기 위한 방식이나 과정은 정해져 있지 않고 그 풀이법은 매우 다양하다. 하지만 알고리즘의 효율성을 기반으로 생각한다면 문제를 풀 때 걸리는 시간이 가장 짧은 것, 그리고 가장 적은 자원(저장공간)을 사용하는 것이 좋은 알고리즘이다. 

 

현실 속 알고리즘 예시) 수학공식, 음식 레시피 등등

 

즉, 어떤 자료구조와 알고리즘을 사용하냐에 따라 프로그램의 성능이 좌우된다. 

---

2. Array(배열)

- 배열이란, 같은 종류의 데이터를 순차적으로 저장 및 관리하기 위한 자료구조이다. 

- 각 데이터마다 인덱스가 부여되어 대응하도록 구성된 데이터 구조이다. 

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

 

[배열의 장점]  

- 인덱스를 이용한 데이터 검색이 편리하다.

 

[배열의 단점]

- 배열은 크기가 고정적이다.

→ 선언된 배열보다 더 큰 배열이 필요하다면 새로운 배열을 다시 선언해야 되므로 기존의 배열은 의미가 없어진다.

- 배열의 각 데이터는 인덱스를 부여받는다. 

→ 중간에 위치하는 데이터가 삭제되면 재정렬해야 한다. 

 

 

[파이썬에서 배열 만들기]

 

- 1차원 배열

data1 = [1,2,3,4,5]

 

- 2차원 배열

data2 = [ [1,2,3] , [4,5,6] , [7,8,9] ] 

 

예시)

 

[*Array와 함께 꼭 알아야 하는 range 함수] 

• range(stop): range(10)은 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• range(start, stop): range(1, 11)은 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
• range(start, stop, step): range(0, 20, 2)은 0, 2, 4, 6, 8, 10, 12, 14, 16, 18
  • start, stop, step은 음수로 지정 가능

---

3. Queue(큐) 

• 큐는 줄을 서는 것처럼 먼저 들어온 데이터가 먼저 나가는 규칙을 갖고있는 자료구조다.
• 규칙을 FIFO(First In, First Out) 또는 LILO(Last In, Last Out)라고 표현한다. 이러한 특성으로 인해 데이터 재정렬이 필요없다.
• 큐는 특별히 언급되는 장단점은 없고 활용의 예로 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용된다.(운영체제) 

 

[*Queue 사용 시 알아야 하는 함수] 

• Queue.put(): 큐에 데이터를 넣는 함수
• Queue.get(): 큐에서 데이터를 꺼내는 함수
• Queue.qsize(): 큐의 크기를 확인하는 함수
• Enqueue(엔큐): 큐에 데이터를 넣는 기능
• Dequeue(디큐): 큐에서 데이터를 꺼내는 기능 

 

[파이썬에서 큐 만들기]

- 파이썬에는 queue라이브러리를 이용하여 3가지 큐를 작성할 수 있다.

 

(1) Queue(): 가장 일반적인 큐 자료 구조

 

(2) LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조(스택과 동일)

 

(3) PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력
- PriorityQueue.put((우선순위, value)) 형식으로 키와 값을 쌍으로 갖게 된다. 1이 가장 높은 우선순위를 의미한다. 

 

(4) 리스트 변수를 이용하여 enqueue와 dequeue 기능 구현하기

---