자료구조 모음

자료구조

• 코드상에서 "효율적으로" 데이터를 처리하기 위해 데이터의 특징에 따라 체계적으로 구조화하여 저장
• 대표적인 자료구조는 배열, 스택, 링크드리스트, 해쉬테이블, 힙 등...

1. 배열

• 데이터 나열하고 각 데이터를 인덱스에 대응하도록 구성한 자료구조
• 파이썬 리스트 타입은 배열 기능 제공함

1-1. 배열이 필요한 이유

같은 종류의 데이터를 효율적으로 관리하기 위해 사용합니다!
같은 종류의 데이터를 순차적으로 저장
빠른 접근이 가능(인덱스 번호로 접근시)

1-2. 배열의 단점

데이터의 추가/삭제가 어려움
미리 최대 길이를 설정해야 함

# 1차원 배열: 리스트로 구현
arr_list = [1, 2, 3, 4, 5]
print(arr_list)

# 2차원 배열: 리스트로 구현
arr_list = [[1,2,3],[4,5,6],[7,8,9]]
print(arr_list)

문제

# dataset 배열에서 전체 이름안에 'M'이 몇번 나왔는지 빈도수를 측정해보자
dataset = ['Braund, Mr. Owen Harris',
'Cumings, Mrs. John Bradley (Florence Briggs Thayer)',
'Heikkinen, Miss. Laina',
'Futrelle, Mrs. Jacques Heath (Lily May Peel)',
'Allen, Mr. William Henry',
'Moran, Mr. James',
'McCarthy, Mr. Timothy J',
'Palsson, Master. Gosta Leonard',
'Johnson, Mrs. Oscar W (Elisabeth Vilhelmina Berg)',
'Nasser, Mrs. Nicholas (Adele Achem)',
'Sandstrom, Miss. Marguerite Rut',
'Bonnell, Miss. Elizabeth',
'Saundercock, Mr. William Henry',
'Andersson, Mr. Anders Johan',
'Vestrom, Miss. Hulda Amanda Adolfina',
'Hewlett, Mrs. (Mary D Kingcome) ',
'Rice, Master. Eugene',
'Williams, Mr. Charles Eugene',
'Vander Planke, Mrs. Julius (Emelia Maria Vandemoortele)',
'Masselmani, Mrs. Fatima',
'Fynney, Mr. Joseph J',
'Beesley, Mr. Lawrence',
'McGowan, Miss. Anna "Annie"',
'Sloper, Mr. William Thompson',
'Palsson, Miss. Torborg Danira',
'Asplund, Mrs. Carl Oscar (Selma Augusta Emilia Johansson)',
'Emir, Mr. Farred Chehab',
'Fortune, Mr. Charles Alexander',
'Dwyer, Miss. Ellen "Nellie"',
'Todoroff, Mr. Lalio']

방법1

count = 0;
for i in dataset:
  m =i.count('M')
  count+=m
print(count)

방법2

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

print(m_count)

큐(Queue)

• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
• FIFO(First-In, First-Out)
• 줄을 서는 행위와 유사

1-1. 큐의 사용

멀티테스킹을 위한 프로세스 스케쥴링 방식을 구현(운영체제)
( 푸시메시지 = notification , 운영체제 프로그램...)

1-2. 큐의 용어

Enqueue: 큐에 데이터를 넣는 기능
Dequeue: 큐에 데이터를 꺼내는 기능
// 링크: https://visualgo.net/en/list

1-3. queue 라이브러리 활용

Queue(): 가장 일반적인 큐 자료구조 생성
LifoQueue(): ~=stack 나중에 입력된 데이터가 먼저 출력되는 구조
priorityQueue(): 데이터마다 우선순위를 넣어서 우선순위가 높은 순으로 데이터 출력

사용법

import queue

data_queue = queue.Queue() # 일반적인 큐
data_queue.put('apple') # Enqueue
print(data_queue) 			# <queue.Queue object at 0x7f9138c55f40>
print(data_queue.qsize()) 	#1
data_queue.put('banana')
print(data_queue.qsize()) 	#2
print(data_queue.get()) 	#apple
print(data_queue.qsize())	#1
print(data_queue.get())		#banana
print(data_queue.qsize())	#0

• 한 큐에 다른 타입을 넣을 수 있다✨ (ex)김사과, apple, 160.5, True

스택

링크드리스트

해쉬테이블

힙