네카라쿠배 프론트엔드 취업완성 스쿨 2기 2차 테스트 6일차 학습

자료구조란?

• 자료구조, 데이터 구조, data structure
• 대량의 데이터를 효율적으로 관리할 수 있는 데이터 구조를 의미
• 코드상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라 체계적으로 데이터를 구조화해야 함
  • 어떤 데이터 구조를 사용하느냐에 따라, 코드 효율이 달라짐

대표적인 자료구조

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

알고리즘이란?

• 어떤 문제를 풀기 위한 절차/방법
• 어떤 문제에 대해, 특정한 '입력'을 넣으면, 원하는 '출력'을 얻을 수 있도록 만드는 프로그래밍

anaconda란?

• 파이썬 컴파일러
• 파이썬 주요 라이브러리들을 포함하고 있음.
• jupyter notebook 등 유용한 툴
• 데이터 사이선스 작업에 자주 사용하는 패키지를 간단하게 설치할 수 있고. 여러 프로젝트에서 작업할 때마다 다른 가상환경을 만들 수 있다.

컴파일러란? : 프로그래밍 언어로 작성된 코드를 컴퓨터가 실행할 수 있는 코드로 변환하는 프로그램

파이썬은 다양한 라이브러리가 큰 장점이다.

jupyter notebook 이란?

• 한줄 한줄 코드 실행 결과 확인이 쉽다.
• 문서와 코드를 함께 작성/저장 할 수 있다.
• 복잡한 자료구조/ 알고리즘을 보다 쉽게 정리하고 , 익히기 위해 사용한다.

jupyer notebook은 코드의 실행 결과를 바로바로 보여주고 거기에 필기등을 함께 작성할 수 있다.

New 버튼을 눌러 새로 파일을 만들 수 있다.

jupyter의 주요단축키

해당 input 창 내에 파이썬 코드를 작성할 수 있다.

코드를 작성하고

간혹 실행중에 In[] 사이가 숫자가 아닌 * 표시로 뜨는 경우가 있는데 이는 코드가 실행중이라는 의미임.

linux 처럼 2가지의 모드가 있는데

Command mod : 셀에

[ a ] : 위로 셀 추가

[ b ] : 아래로 셀 추가

[ dd ] : 선택 셀 삭제

[ c ] : 선택 셀 복사

[ p ] : 선택 셀 붙여넣기

[ x ] : 선택 셀 잘라내기

[ Enter ] : 선택 셀의 입력모드

Edit mode

[ Shift + Enter ] : 파이썬 코드 실행

[ Ctrl + a ] : 선택 셀의 전체 코드 선택

[ Ctrl + z ] : 선택 셀 내 실행 취소

[ Ctrl+ / ] : 커서 위치 라인 주석 처리

[ Ctrl + s ] : 파일 저장

배열 (Array)

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

배열이 필요한 이유

• 같은 종류의 데이터를 효율적으로 관리하기 위해 사용한다.
• 같은 종류의 데이터를 순차적으로 제공한다.

배열의 장점

• 인덱스를 통해 빠른 접근이 가능하다.
• 같은 종류의 데이터를 순차적으로 저장

배열의 단점

• 미리 최대 길이를 지정해야한다.
• 데이터가 가변적이라면 데이터의 추가와 삭제의 오버헤드가 크다.

C언어에서는 배열을 초기에 최대 길이를 지정해야한다.

하지만 python의 list에서는

country = 'US'
print(country)

country += 'A'
print(country)

문자열도 하나의 리스트인데. 추가 삭제가 자유롭고 최대 길이를 지정할 필요가 없다.

1차원 배열 : 리스트로 구현

data = [1,2,3,4]
print(data)

출력 : [1, 2, 3, 4]

[ ] 괄호를 사용해서 요소들을 나열한다.

2차원 배열 : 리스트로 구현

data = [[1,2,3],[4,5,6],[7,8,9]]
print(data)
print(data[0])
print(len(data))
print(data[0][0])

2중리스트는 [] 안에 []를 추가해서 구현한다.

[ ] 내의 [1,2,3]이 하나의 요소이고 이것에 data[0] 을통해 접근할 수 있다.

그리고 이 2차원리스트의 요소에는 data[0][0]을 통해 접근가능하다.

print(data[0][0])
print(data[0][1])
print(data[1][2])

이렇게 배열의 원하는 요소에 접근할 수 있다.

여기에서 9, 8, 7 에 각각 접근해보는 연습을 해보자

index는 0번부터 시작하는것을 잊지 않아야한다.

# 정답
print(data[2][2])
print(data[2][1])
print(data[2][0])

이번에는

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']

이 dataset이라는 리스트에있는 대문자 M이 몇개인지 세어보는 코드를 작성해보자.

시작하기전에 알아두자면 문자열은 리스트처럼 사용가능하다.

test = 'hello'
print(test[0])
print(test[1])

즉 인덱싱이가능하다는 뜻이다.

그렇다면 이중 for문을 사용해서 2중리스트로 구성 돼 있는 dataset에 접근할 수 있을 것이다.

count = 0
for data in dataset:
    for idx in range(len(data)):
        if data[idx] == 'M':
            count += 1
print(count)

range 내장 함수로 리스트의 갯수만큼 순회하며 각 리스트의 index길이만큼 다시 순회하면서 M을 찾아 count를 늘려주면된다.

문자열은 이터러블 객체다. iterable 이란 반복이 가능한 객체라는 뜻인데 문자열, 리스트, 딕셔너리, 세트가 있다. 여러개의 요소가 있고 한 번에 하나씩 꺼낼 수 있다.

즉

count = 0
for data in dataset:
    for word in data:
        if word == 'M':
            count += 1
print(count)

이런식의 접근도 가능하다.

큐 (queue)

큐의 구조

• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
• FIFO(First-in, First-out) 또는 LILO(Last-in, Last-Out) 방식으로 스택과 꺼내는 순서가 반대
• 줄을 섰을 때 먼저 줄 선사람이 먼저 입장하는 것과 동일

Enqueue : 큐에 데이터를 넣기

Dequeue : 큐에서 데이터를 빼기

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

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

일반적으로는 FIFO 방식을 사용하지만 다양한 정책이 적용된 큐들이 있다.

Queue() 로 큐 만들기 ( 가장 일반적인 큐로 FIFO(First-In, First-Out )

import queue
data_queue = queue.Queue()
data_queue.put('hi')
data_queue.put(123)
data_queue.qsize()

queue.Queue 는 FIFO 큐의 생성자이다.()안에 maxsize를 지정할 수 있다. 이 maxsize는 큐에 배치할 수 있는 최대 항목 수를 설정하는 정수이다. maxsize는 기본적으로 0이고 0보다 작거나 같으면 큐의 크기는 무한하다.

Queue 라이브러리 에선 enqueue를 put 으로 dequeue를 get으로 사용하고 있다. 그래서 큐에 'hi'라는 넣기 위해 data_queue.put('hi')를 사용한다.

qsize라는 함수는 queue의 길이를 반환한다. hi와 123이 들어있으므로 2를 반환함.

data_queue.get()

get() 함수로 dequeue를 수행하면 FIFO 정책에 의해 먼저들어갔던 hi가 먼저 dequeue 되고

다시 qsize로 확인해보면 data_queue 의 길이가 1로 바뀌어 있을 것이다.

LifoQueue() 로 큐 만들기 (LIFO(Last-In, First-Out))

import queue
data_queue = queue.LifoQueue()
data_queue.put('hi')
data_queue.put(123)
data_queue.qsize()

queue.LifoQueue() 는 LIFO 큐의 생성자이다. maxsize 옵션은 Queue와 동일하다.

LIFO는 마지막에 넣은 요소를 먼저 출력한다.

data_queue.get()

따라서 dequeue를 수행하면 후에 넣은 123이 먼저 dequeue 된다.

PriorityQueue() 로 큐 만들기

PriorityQueue는 우선순위 큐이다. 각각의 요소를 enqueue 할 때 우선순위 번호를 함께 넣는다. 우선순위가 높은것은 가장 낮은 값을 가지고 이 값이 먼저 꺼내진다. 데이터를 넣는 순서에 따라 추출하는 것이아니라 우선순위에 따라 먼저 꺼냄.

import queue
data_queue = queue.PriorityQueue()
data_queue.put((10,'hi'))
data_queue.put((9,123))
data_queue.put((15,'python'))
data_queue.qsize() # 3

우선순위 큐의 경우 enqueue 때 우선순위와 데이터가 튜플형태로 들어가게된다.

앞에는 우선순위가 뒤에는 데이터가 들어감.

data_queue.get()

이상태로 get함수로 dequeue 하면 가장 낮을 값을가진 즉, 가장 높은 우선순위를 가진 (9, 123)를 꺼내게 된다.

큐는 어디에 많이 쓰이나

• 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현할 때 많이 사용됨

큐의 enqueue 와 dequeue를 직접 구현해보기

Qlist = list()
def enqueue(data):
    Qlist.append(data)
def dequeue():
    data = Qlist[0]
    del Qlist[0]
    return data
for index in range(10):
    enqueue(index)
print(len(Qlist))
print(Qlist)

enqueue 는 data를 append 하고 dequeue는 먼저 들어온 데이터를 먼저 추출, 삭제 과정을 거친다. 손쉽게 구현가능.

스택

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

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

구조

LIFO(Last In, First Out) 또는 FILO(First in, Last Out) 데이터관리 방식을 따름

• LIFO : 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
• FILO : 처음 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책
• 대표적인 스택의 활용
  • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식

Push : 데이터를 스택에 넣기

Pop : 데이터를 스택에서 꺼내기

스택 구조와 프로세스 스택

• 스택 구조는 프로세스 실행 구조의 가장 기본
• 함수 호출시 프로세스 실행 구조를 스택과 비교해서 이해 필요

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

재귀함수를 스택의 관점에서보면

data 매개변수가 0보다 클땐 1씩 줄여가며 자기 자신을 다시 호출한다.

#stack
-1(recursive(-1))
0 (recursive(0))
1 (recursive(1))
2 (recursive(2))
3 (recursive(3))
4 (recursive(4))

print(Returned, data)를 수행하기 전에 바로 자기자신을 호출하기 때문에 프로세스 스택이 저렇게 쌓이고. -1에서는 if 에서 걸리기 때문에 ended를 출력하고 스택에서 제거되고 그 아래의 0 에서도 print("Returned" ,data)를 마저 출력하고 제거되고 이과정을 거쳐 recursive(4)가 완료된다. 즉 먼저 스택에 먼저 들어간 데이터가 가장 마지막에 나오게 된다.

장점

• 구조가 단순, 구현이 쉽다.
• 데이터의 저장/읽기 속도가 빠르다

단점(일반적 스택에서)

• 데이터의 최대 갯수를 미리 정해야한다.
• 파이썬의 경우 최대 1000번의 재귀함수 호출이 가능하다.
• 저장공간의 낭비가 발생할 수 있다.

단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적.

data_stack = list()
data_stack.append(1)
data_stack.append(2)
data_stack

list로 데이터 스택을 구현해본다. append로 1,2를 차례로 넣으면

data_stack = [1,2] 가 될 것이다.

data_stack.pop()
data_stack

여기서 이제 stack.pop()으로 데이터를 꺼내면

2가 빠져나오고

data_stack에는 1만 남는다. 마지막에 들어갔던 2가 나오게되는 것.

스택 직접 구현하기

data_stack = list()
def push(data):
    data_stack.append(data)
def pop():
    data = data_stack[-1]
    del data_stack[-1]
    return data

for idx in range(10):
    push(idx)
pop()

먼저넣은것을 나중에에 빼기만 하면된다.

pop 에서는 스택의 가장 끝지점인 data_stack[-1] 을 추출하고 해당 요소를 지운뒤

추출한 값을 return 해준다.

그리고 0~9까지 순차적으로 push한뒤에 pop() 해보면 가장 마지막에 들어간 9가 반환된다.