Chapter 03. 배열(Array)

00. 개요

데이터를 나열하고, 각 데이터를 index에 대응하도록 구성한 데이터 구조이다.

python에서는 List Data type이 배열 기능을 제공하지만, 더 많은 기능을 가지고 있기 때문에 단순히 List 만으로는 배열을 이해하기 어렵다.

참고자료

• 배열은 동일한 데이터 타입의 데이터만 인수로 가질 수 있다.

• 가장 기초적인 세 가지는 1) index는 0부터 시작한다. 2) 배열의 길이는 인수의 갯수와 같다. 3) index를 통해 해당 데이터 값에 접근할 수 있다.

• 배열의 기본 작업: Traverse, Insertion(by index), Deletion(by index), Search(by index or by value), Update(by index)

• python에서 활용하려면, array module을 import해야 한다.

  arrayName = array(typecode, [Initializers])

• 배열의 데이터에 접근하기: arrayName[index]

• 배열에 데이터 삽입하기: arrayName.insert(index, newValue)

• 배열의 데이터 삭제하기: arrayName.remove(value)

• 배열의 데이터 검색하기: arrayName.index(value) -> 해당 데이터 값이 존재하지 않으면, Error를 발생시킨다.

• 배열의 데이터 수정하기: arrayName[index] = newValue

• Two dimensional array is an array within an array. It is an array of arrays.

01. 배열은 왜 필요할까?

배열은 같은 종류의 데이터, 즉, 연관된 데이터를 효율적으로 관리할 수 있게 해준다. 같은 종류의 데이터를 순차적으로 연결된 저장 공간에 저장하기 때문이다.

연관되어 연결된 데이터의 경우(예시: 문자열 'String')에는 연결된 저장 공간 속에서 순차적으로 저장하는 것이 더 효율적이고, 배열의 각 저장 공간을 index 번호를 활용해 직접적으로 접근할 수 있기 때문에 배열을 활용한다.

02. 배열의 장점과 단점

배열의 장점

• 빠른 접근이 가능하다.
  - index를 활용해 각 저장 공간에 저장된 데이터에 직접적으로 빠르게 접근할 수 있다.
• 첫 데이터의 위치에서 상대적으로 데이터에 접근할 수 있다.

배열의 단점

• 사전에 데이터의 최대 크기를 지정해야 하기에 이후 데이터를 추가하기 어렵다.
  - 새롭게 데이터를 입력할 크기에 맞는 저장 공간을 부여하여 배열을 새로 작성해야 한다.
• 연관된 가변 데이터의 수정, 삭제로 인해 저장 공간의 공백이 발생하는 경우, 뒤쪽 데이터를 옮겨줘야 하는 문제가 발생할 수 있다.
• 배열을 선언할 때 사전에 'size'를 지정하고, 데이터를 삽입해야 한다.
• 선형 검색(Linear Search)을 활용하기 때문에 Search operation에서 시간이 오래 걸릴 수 있다.
• 삽입, 삭제의 경우 배열의 끝에 하는 것은 쉽게 할 수 있지만, 중간이나 맨 처음에 삽입, 삭제할 때는 배열을 움직여주어야 하기 때문에 오래 걸릴 수 있다.

Binary Search는 sorted Array에서만 활용할 수 있다. 정렬된 배열은 새로운 데이터의 추가, 삭제가 정렬되지 않은 배열보다 오래걸린다. 그러나 이진 검색을 도입하면 정렬된 배열에서의 검색 속도는 상상 이상으로 빨라질 수 있게 된다.(이진 검색의 경우 매 단계마다 배열의 절반만 고려하기 때문이다.)

03. python과 C의 배열 예제

C 예시

영어 단어 저장 예시

• C언어의 경우 배열을 사용할 때 'size'를 우선 설정하고, 해당 데이터를 삽입한다. 따라서 데이터를 추가하려면, 변수를 재지정해야 한다.

#include <stdio.h>

int main(int argc, char * argv[])
{
    char country[3] = "US";
    printf ("%c%c\n", country[0], country[1]);
    printf ("%s\n", country);    
    return 0;
}

python 예시

영어 단어 저장 예시

• python의 경우 데이터를 추가하더라도, 단순한 연산자를 활용해 가능하고, 변수를 재지정할 필요는 없다.

country = 'US'
print(country)

country = country + 'A'
print(country)

US
USA

04. python의 배열(Array)

python에서는 List data type으로 1차원, 2차원 배열을 구현할 수 있다.

1차원 배열

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

print(data_list)

[1, 2, 3, 4, 5]

1차원 배열은 index로 해당 위치의 데이터 값을 출력할 수 있다.

data_list[2]

3

2차원 배열

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

print(data_list)

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

2차원 배열도 list 내부에 list로 구현할 수 있고, index를 두 번 활용해서 해당 위치의 데이터 값을 출력할 수 있다.

data_list[0][0]
data_list[0][2]
data_list[1][1]
data_list[2][0]
data_list[2][1]

1
3
5
7
8

05. 연습하기

해당 name_set 내에 이름에서 'M', 'r', 's'가 몇 번 나왔는지 빈도수를 출력하라.

name_set = ['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']

count = 0

for i in name_set:
	for j in i:
    	count += j.count('M')

print(count)

38

참고

• range 함수
• range(stop)
• range(start, stop)
• range(start, stop, step)

Chapter 04. 큐(Queue)

01. 큐(Queue) 자료 구조

• 일종의 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
  • 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일하다.
  • 'FIFO(First-In, First-Out, 선입선출)' 또는 'LILO(Last-In, Last-Out, 후입후출)' 방식의 정책을 갖고 있다.
  • 자료 구조 스택(Stack)과 꺼내는 순서가 반대이다.
  • 중복을 허용하지 않기 때문에, 큐 자료 구조에 동일한 데이터를 삽입할 수 없다.

큐 자료 구조에 데이터를 삽입하면, 지정된 저장공간에 뒤쪽부터 데이터를 삽입한다. 이후 데이터를 단순히 출력하는 명령을 하면, 특정 데이터나 특정 데이터의 위치(즉, index)를 지정하지 않고, 단순히 가장 먼저 삽입된 데이터를 출력하고, 삽입되어 있는 데이터가 다시 뒤쪽으로 이동된다.(즉, First-in, First-out)

02. 알아둘 용어

• FIFO: First-In, First-Out, 선입선출 방식
• Enqueue: 큐에 데이터를 넣는 기능(데이터 입력)
• Dequeue: 큐에서 데이터를 꺼내는 기능(데이터 출력)
• Visualgo 사이트에서 시연해보며 이해하기: https://visualgo.net/en/list

03. python Queue 라이브러리 활용해서 큐 자료 구조 사용하기

보통 프로그래밍 언어에서는 이러한 자료 구조를 활용하기 위한 함수, 라이브러리 등을 제공한다.

• queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공
• 프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용
  • Queue(): 가장 일반적인 큐 자료 구조
  • LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨)
  • PriorityQueue(): 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력

일반적인 큐 외에 다양한 정책이 적용된 큐들이 있음

'Queue( )': 가장 일반적인 큐, FIFO(First-In, First-Out)

# 라이브러리 불러오기

import queue

# Queue 생성하기

data_queue = queue.Queue()    # 일반적인 FIFO Queue가 생성된다.

print(data_queue, type(data_queue))

<queue.Queue object at 0x0000024DF812F760> <class 'queue.Queue'>

# Queue에 데이터 삽입하기

data_queue.put("첫번째로 삽입한 데이터")    # Data type 상관 없음.
data_queue.put(2)
data_queue.put("마지막으로 삽입한 데이터")

# Queue의 사이즈 확인하기

data_queue.qsize()

3

# Queue의 데이터 출력하기

data_queue.get()

'첫번째로 삽입한 데이터'

# Queue의 사이즈 확인하기

data_queue.qsize()

2

# Queue의 다음 데이터 출력하기

data_queue.get()

2

'LifoQueue( )': LIFO(Last-In, First-Out), 후입선출 방식

# 라이브러리 불러오기

import queue

# LIFO Queue 생성하기

data_queue = queue.LifoQueue()    # LIFO 방식의 Queue가 생성된다.

print(data_queue, type(data_queue))

<queue.LifoQueue object at 0x0000024DF80E5280> <class 'queue.LifoQueue'>

# Queue에 데이터 삽입하기

data_queue.put("첫번째로 삽입한 데이터")
data_queue.put(2)
data_queue.put("마지막으로 삽입한 데이터")

# Queue의 사이즈 확인하기

data_queue.qsize()

3

# Queue의 데이터 출력하기

data_queue.get()    # FIFO와 다르게 뒤에 삽입한 '마지막으로 삽입한 데이터'가 출력된다.

'마지막으로 삽입한 데이터'

'PriorityQueue()'

• 각각의 삽입된 데이터마다, 우선순위를 부여하는 Queue로, 데이터를 출력할 때마다 가장 우선순위가 높은 데이터를 출력하는 Queue 자료 구조이다.
• 우선순위 숫자가 낮을수록, 먼저 출력된다.

# 라이브러리 불러오기

import queue

# Priority Queue 생성하기

data_queue = queue.PriorityQueue()    # Priority Queue가 생성된다.

print(data_queue, type(data_queue))

<queue.PriorityQueue object at 0x0000024DF81AEAC0> <class 'queue.PriorityQueue'>

# Queue에 데이터 삽입하기(우선순위 포함)

data_queue.put((10, "첫번째로 삽입한 데이터, 우선순위 2등"))    # tuple(우선순위, 데이터) 형식으로 삽입
data_queue.put((5, '2, 우선순위 1등'))
data_queue.put((15, "마지막으로 삽입한 데이터, 우선순위 3등"))

# Queue의 사이즈 확인하기

data_queue.qsize()

3

# Queue의 데이터 출력하기

data_queue.get()

(5, '2, 우선순위 1등')

# Queue의 다음 데이터 출력하기

data_queue.get()

(10, '첫번째로 삽입한 데이터, 우선순위 2등')

참고: 어디에 큐가 많이 쓰일까?

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

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

04. 연습하기

리스트 변수로 큐를 다루는 enqueue, dequeue 기능 구현

# 빈 List 선언

q_list = list()

# enqueue 함수 구현

def enqueue(x):
    q_list.append(x)

# dequeue 함수 구현
    
def dequeue():    # FIFO
    data = q_list[0]
    del q_list[0]
    return data

# q_list 데이터 삽입하기

for i in range(1, 11):
    enqueue(i)

print(q_list)

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

# q_list 사이즈 확인하기

len(q_list)

10

# q_list 데이터 출력하기

dequeue()

1

# q_list 데이터 출력하기

dequeue()

2

# q_list 데이터 출력하기

dequeue()

3

# q_list 사이즈 확인하기

len(q_list)

7

Chapter 05. 스택 (Stack)

00. 개요

• 많이 사용되는 핵심적인 자료 구조 중 하나

• 데이터를 제한적으로 접근할 수 있는 구조(큐(Queue)와 유사)

  • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조

• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조(큐(Queue)와 차이)

  • 큐(Queue): FIFO(First in, First Out) 정책 - 줄 세우기와 유사
  • 스택(Stack): LIFO(Last in, First Out) 정책 - 책 쌓기와 유사

01. 스택(Stack) 구조

• 스택(Stack)은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따른다.

  • LIFO(Last in, First Out): 마지막에 넣은 데이터를 가장 먼저 출력하는 데이터 관리 정책
  • FILO(First in, Last Out): 처음에 넣은 데이터를 가장 마지막에 출력하는 데이터 관리 정책

• 대표적인 스택의 활용

  • 컴퓨터 내부의 프로세스(프로그램) 구조에 포함되어 있는 함수 동작 방식에 활용된다.

• 주요 기능 keyword

  • push(): 데이터를 스택(Stack)에 넣기
  • pop(): 데이터를 스택(Stack)에서 꺼내기

• Visualgo 사이트에서 시연해보며 이해하기: https://visualgo.net/en/list
  
  
  

스택(Stack) 자료 구조는 하단, 바닥과 상단이 존재하는데, push() 명령어를 통해 데이터를 삽입하면 최하단부터 데이터가 쌓이게 된다. 또한, 큐(Queue)와 동일하게, pop() 명령어는 index가 없이 최상단에 있는 데이터, 즉 가장 마지막/최근에 삽입한 데이터를 출력하게 된다.

02. 스택(Stack) 구조와 프로세스 스택(Stack)

• 컴퓨터에서 가장 스택(Stack) 구조가 가장 많이 활용되는 부분은 운영체제의 프로세스의 함수 처리 과정에서의 동작 방식이다.
• 스택 구조는 프로세스 실행 구조의 가장 기본
  • 함수 호출시 프로세스 실행 구조를 스택과 비교해서 이해 필요

함수의 동작 방식이 스택(Stack) 자료 구조와 유사하다. 즉, 이러한 스택(Stack) 자료 구조가 많이 활용되는 곳은 프로세스 함수 동작 방식에서 자주 활용된다. 프로세스 스택이 스택(Stack) 자료 구조를 기반으로 만들어진 것이다.

[예시]

# 재귀 함수 선언하기

def recursive(data):
    if data < 0:
        print ("ended")
        
    else:
        print(data)
        recursive(data - 1)    # 함수 내에서 자신의 함수를 다시 호출하는 형식으로 재귀 함수 형식 완성.
        print("returned", data)

recursive(4)

4
3
2
1
0
ended
returned 0
returned 1
returned 2
returned 3
returned 4

• recursive() 함수를 활용하면, else구문에 의해 recursive(data)의 값이 스택(Stack)처럼 쌓인다.
• ended 출력 이후 함수가 종료되는데, 이때 data = 0이 삽입되어 만들어진 recursive(-1)이 종료되면서, 제거되고, print('retured', data)가 실행된다.
• 결국 다시 data = 4인 경우까지 제거되고 returned가 출력된다.

03. 자료 구조 스택(Stack)의 장단점

• 장점
  • 구조가 단순하고 익숙하기 때문에 구현이 쉽다.
  • 데이터 저장 속도와 데이터 읽기 속도가 빠르다. -> 함수가 스택(Stack) 자료 구조와 유사한 이유.

• 단점 (일반적인 스택 구현시)
  • 데이터 최대 갯수를 미리 정해야 한다.(최대의 저장 공간을 미리 확보하고, 지정해야 하기 때문)
    • 파이썬의 경우 재귀 함수는 '1000번'까지만 호출이 가능함(즉, 최대 저장 공간을 1000으로 확보했기 때문이다.)
      
  • 저장 공간의 낭비가 발생할 수 있다.
    • 미리 최대 갯수만큼 저장 공간을 확보해야 하기 때문에 불필요한 낭비가 존재한다.
    • 평소 활용하는 저장 공간만큼이 아니라 최대의 저장 공간을 포함해야 하기 때문이다.

스택(Stack)은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적이다. 이 경우, 위에서 열거한 단점이 발생할 수 있다.

04. python List 기능에서 제공하는 메서드로 스택 사용해보기

• List에서 append(= push), pop 메서드를 활용해서 스택(Stack) 자료 구조의 정책을 그대로 적용할 수 있다.

# List 생성 및 데이터 삽입하기

data_stack = list()

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

print(data_stack)    # 먼저 삽입한 데이터가 가장 앞에서부터 쌓인다.

[1, 2]

# 데이터 삭제하기

data_stack.pop()    # 가장 나중에 삽입한 데이터가 출력된다.

2

# 데이터 삭제하기

data_stack.pop()    # 가장 나중에 삽입한 데이터가 출력된다.

1

05. 연습하기

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

# pop, push 함수 정의하기

stack_list = list()

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

# stack_list 생성 후 데이터 삽입하기

for i in range(1, 11):
    push(i)

print(stack_list)

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

# 데이터 삭제하기

pop()
pop()
pop()

10
9
8

print(stack_list)

[1, 2, 3, 4, 5, 6, 7]