Today, I learned: Data Structure (Array/Queue/Stack)

작성동기

코딩테스트 자료를 정리하는 도중에, 자료구조에 대해서 정리를 하면 좋을 것 같다는 생각이 들어서 작성했습니다.

데이터 구조가 필요한 이유

자료구조라고 하면 뭔가 느낌이 바로 안오지 않나요? 나만그런가? 그래서 데이터 구조라고 하는 것이 뭔가 느낌이 데이터를 어떻게 구성해야하겠다라는 느낌이 옵니다. 어째든 데이터구조라는 것이 왜 필요할까요?

데이터가 모여서 하나의 구조를 이룬다. 그러한 구조들이 동작하면서, 애플리케이션이 구성된다. 그러면 데이터를 모으는 방식에 대해서 효율적으로 구성한다면, 효율적으로 동작할 것이고, 그것은 효율적으로 애플리케이션이 동작할 것이다.

이런 논리로 필요하다고 생각합니다. 다른 좋은 예시도 있어서 가져와봅니다.

모래성을 쌓는다면, 그냥 모래를 대충 모으기만 하면 완성된다. 하지만 63빌딩을 짓는다고 해도, 아무런 구조적 고민 없이 지어도 괜찮을까? 구조적으로 고민하지 않은 구조체는 분명 부실공사로 이어질 수 밖에 없다.

제가 생각하는 데이터 구조는 아래와 같습니다.

데이터 구조는 결국, 상황을 고려해볼 때, 가장 효율적으로 Input 하고 Output하는 구조이다.

• 위에서보면, 전제를 깔았죠. "상황을 고려해볼 때"
• 맥락에 따라서 가장 효율적인 데이터 구조가 있고, 그것에 맞게 선택하여 사용하면 된다고 봅니다.

그러면 어떤 것들이 데이터 구조일까요?

1. 배열

"배열하다" 동사뜻은, "일렬로 줄세워 무언가를 놓는다." 입니다. 데이터를 일렬로 줄을 세우는 데이터 구조입니다. 일렬로 세우면 어떤 장점이 있을까요? 바로 일렬로 선 줄에서 2 번째, 3 번째, 제일 마지막 이런식으로 부를 수 있습니다. 왜냐하면, 배열자체에 이미 선형성 성질을 가지고 있기에, 한쪽방향으로 흐르고 있고, 그것들에는 각각의 순서가 부여되어 있습니다. 그러므로 앞에서부터 2 번째, 이런식으로 접근이 가능하죠. 데이터도 마찬가지입니다.

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

이런식으로 10 개의 데이터를 만들었다면, 제일 앞에 데이터에 접근하기 위해서는 간단하게 index만 넣어주면 접근이 가능하죠.

print(data[0])
# 1

배열의 장점은 인덱스를 통한 데이터 접근입니다. 이것을 "Random access" 라고 한 단어로 설명할 수 있겠네요. 참고로 반대 말은 "Sequential access" 입니다. 순차적으로 접근해야한다는 뜻입니다. 그러먼 어째서 배열은 이것이 가능한 것일까요?

인덱스	0	1	2	3
요소	"uno"	"kim"	"moya"	"kim"

이런식으로 배열이 저장되어있다고 가정해봅시다. 배열에서 예를들어 data[2] 라고 접근할 때, 바로 "moya" 로 이동하는 것이 아니라, 시작점에서 부터 몇 번째 저장되어 있는지를 확인하는 순서로 데이터에 접근합니다. 즉, data[0] 이 저장된 메모리 주소로 이동하고, 그 이후에 그것으로부터 2칸 떨어진 곳으로 한 번에 jump 하는 것이죠. 그러므로 Random access 가 가능합니다. 그리고 끝으로도 한 번에 접근 가능한 이유가 배열은 크기가 고정되어 있습니다.(물론 여러 언어에서 추가되는 것처럼 보이지만, 실제로는 복사해서 새로운 배열을 생성하는 경우일겁니다.maybe) 그렇기에 제일 마지막이 어딘지 정보를 저장하고 있습니다. (C 언어에 마지막에 꼭 특정 값이 저장되고 있죠. 그 덕분에 endpoint인지 바로 알 수 있구요.) 그러므로 장점은 '빠른 접근' 입니다.
그러면 단점도 있겠죠. 단점은 "최대길이를 미리 정해두어야 한다" 그리고 "추가와 삭제에 리소스가 크다" 는 점 입니다. 먼저 최대 길이를 정한다는 것은, 배열을 처음에 선언하고 초기화 할 때, "이 배열은 5 칸을 가지고 있어." 이런식으로 결정해주어야 합니다. C 언어에서 구현하면 바로 알 수 있죠.

#include <stdio.h>

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

이렇게 3 칸을 확보하고 있습니다. 그런데 보면 분명히 A와 B만 넣었으면 2 칸일 것 같은데 3칸이죠. 그것은 마지막 칸은 배열이 끝났음을 표시하기위해서 1 칸을 더 할당해야합니다. 나머지 언어에서도 동일하게 동작하지만, '알아서' 해주고 있는 겁니다. 마지막 칸에 endpoint가 없으면 배열이 어디가 끝인지 컴퓨터는 알 수가 없겠죠. 그러면 배열의 장점도 가질 수 없는 겁니다. 메모리상에서 순차적으로 저장되어 있기때문에, 배열의 장점이 있는 것이니까요. 그리고 추가와 삭제가 어려운 부분인 이 원리에서 발생합니다. 이미 3 칸으로 고정되어 있는데, 이곳에 추가하게되면 칸이 넘치죠. 그렇게 되면, 내부적으로는 새로운 배열을 만들어서 추가합니다. 이 때 O(n) 의 리소스가 소비됩니다. 중간에 데이터를 삭제하게 되면, 하나씩 배열을 당겨야겠죠. 거기서도 O(n)의 리소스가 발생하구요. 이러한 점이 단점입니다.

2. 큐

큐(Queue) 라는 것은 "줄서다" 혹은 "줄" 의 의미를 가진 단어입니다. 스타벅스에서 커피를 구매하기 위해서 손님들이 줄을 서고 있죠. 줄을 설 대, 먼저 온 손님이 먼저 주문을 하죠. 나중에 온 손님이 먼저 주문을 하는 것은 사회적으로 용인되지 않습니다. 주문을 마친 손님은 줄에서 나가게 되죠. 이것과 동일한 성질을 가진 데이터 구조가 큐 입니다.
큐에 새로운 손님이 오는 행위를 큐에 새로운 데이터가 추가되었다고 비교해서 생각해볼 수 있을 겁니다. 이것을 "Enqueue" 라고 합니다. 그리고 주문을 마친 고객이 나가는 것을 "Dequeue" 라고 칭합니다. 마지막으로 먼저 온 손님이 먼저 주문하는 이러한 큐의 동작원리를 FIFO (First-In-Frist-Out) 이라고 부릅니다. 이와 반대되는 동작방식은 LIFO(Last-In-Frist-Out) 이라고 칭합니다.

코드로 구현하는 것은 간단합니다.

queue_list = list()

def enqueue(data):
  queue_list.append(data)
  
def dequeue():
  data = queue_list[0]
  del queue_list[0]
  return data

for index in range(10):
  enqueue(index)
  
dequeue()

• equeue의 경우 데이터를 입력받아서 list에 제일 뒤에 추가해주고 있습니다.

• dequeue의 경우 제일 앞에 데이터에 접근하여 element를 가져오고 해당 element를 배열에서 제거합니다. 최종적으로는 제거한 데이터를 리턴합니다.

• 여기서는 queue를 따로 객체로 구현하진 않았습니다. 추가로 데이터가 없는 경우에 대한 에러처리도 하진 않았습니다. (데이터구조 그 자체에 대해서만 작성할예정입니다.)

  큐의 장점은 순서를 부여한다는 점입니다. 순서를 부여할 일이 언제 있을까요 운영체제의 개념인 프로세스 스케쥴링에서 주로 사용됩니다.

프로세스 스케쥴링

프로세스 스케쥴링이라는 것은 CPU를 사용하려고하는 "프로세스" 의 순서를 컨트롤하는 것입니다. 이것을 사용하는 이유는 CPU가 노는시간 없이 일할 수 있도록 하기 위해서 입니다. 마치, 우리가 스케쥴을 짜지 않고 닥치는대로 일을 하다보면, 업무마다 중간중간 비는 시간이 생기기도하고 그러겠죠. 그것과 유사합니다. CPU가 노는시간 없이 일을 한다는 것을 "프로세스 처리율" 이라고 합니다. 단위시간당 작업처리량을 의미합니다.

1. 선입선처리 스케쥴링

   First Come First Served (= First In Frist Out) 라는 뜻으로, 먼저 요청한 프로세스가 먼저 자원을 제공받습니다. 나머지 프로세스는 그동안 대기하고 있습니다.

   프로세스	도착시간	실행시간
   P1	0	10
   P2	1	28
   P3	2	6
   P4	3	4
   P5	4	14

   • 이런 프로세스 5 개가 있다고 가정해봅시다. 선입선출 스케줄링은 들어온 순서대로 프로세스를 처리하므로 P1 -> P2 -> P3 -> P4 -> P5 순으로 처리됩니다.

프로세스	반환시간	대기시간
P1	10	0
P2	37(9+28)	9
P3	42(36+6)	36
P4	45(41+4)	41
P5	58(44+14)	44
평균	38.4	26

대기시간은 자원의 할당을 기다리는 시간입니다. 실행시간은, 프로세스를 처리하는 시간입니다. 반환시간은 작업을 완료하는데 걸린 전체 시간으로 대기시간+실행시간 입니다.
위 프로세스 P3, P4가 실행시간이 짧음에도 불구하고, 오랜시간을 대기하고 있습니다. 즉, 간단한 작업임에도 처리가 안되고 대기하고 있다는 뜻이죠. 비선점방식의 스케쥴링이므로 대화형 운영체제에는 부적합합니다.(시분할운영체제라고도 불리며, 이용자에게 즉각적인 피드백을 제공해주는 운영체제)

이 외에도 다양한 스케쥴링으로 최소작업 우선 스케줄링 / 우선순위 스케줄링 / 라운드 로빈 스케줄링 등이 있습니다. 자세한 건 따로 글을 작성하겠습니다.

다시 본론으로 돌아와서 Queue는 스케줄링에 사용되고, iOS Programming에서는 UITableView 혹은 UICollectionView dataSoure 프로토콜에서 구현하고 있는 메소드 중 cellForRowAt or cellForItemAt 메소드 내에서 cell을 생성하고 리턴할 때, queue가 사용됩니다.

Stack

팬케이크를 하나씩 쌓아올린다고 가정해봅시다. 아래 그림처럼 쌓일겁니다.


맨 아래층부터 먹을 수 있나요? 먹을라고하면 먹을 수는 있습니다만, 일반적으로 그렇지 않죠. 가장 마지막에 올라온 가장 따끈따끈한 케이크를 먼저 먹습니다. 이것이 스텍구조입니다. 가장 마지막에 추가된 데이터가 가장 먼저 방출됩니다. (Last-In-First-Out구조) 밑장빼기 불가능한 데이터구조...
주로 컴퓨터 내부에서 프로세스에서 함수를 동작시킬 때, 사용됩니다. 그렇게 되면, 가장 작은 단위에 있는 함수가 먼저 호출되고, 점점 해당 함수를 호출하고 있는 더 넓은 범위의 함수가 해당 함수를 호출할 수 있게되겠죠. 간단한 재귀함수 코드를 보겠습니다.

def recursive(data):
  # 탈출조건
  if data < 0:
    print("함수처리시작")
   else:
    recursive(data - 1)
    print("Pop: ", data)

recursive(4)

• 결과

함수처리시작
Pop:  0
Pop:  1
Pop:  2
Pop:  3
Pop:  4

호출은 아래와 같은 순서로 진행되었습니다.

recursive(4) -> recursive(3) -> recursive(2) -> recursive(1) -> recursive(0) -> recursive(-1)

그런데 가장 마지막에 추가된 recursive(-1 ) 이 먼저 동작하면서 "함수처리시작" 이 호출되었죠.

그리고 제일 먼저 추가된 recursive(4) 가 가장 마지막에 출력됩니다.

이런식으로 동작하는 데이터구조를 Stack 이라고 합니다.

직접 Stack을 구현하면 다음과 같습니다.

stack = list()

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

push(1) # [1]
push(2) # [1, 2]
push(3) # [1, 2, 3]

pop() # 3
pop() # 2
pop() # 1

스텍의 장점은 데이터의 추가와 읽기속도가 빠릅니다. 왜냐하면, 마지막에만 추가하므로 O(1) 읽는 것도 제일 마지막만 접근하므로 O(1) 입니다. 단점으로는 최대 갯수를 정해줘야합니다. 파이썬한정으로 1000번까지 가능합니다. 그리고 1000번까지 한정하게되면서 필요없는 공간을 차지해야하므로 공간상 낭비가 발생한다는 점 입니다.

스텍은 주로 재귀함수구현이나, Undo 관련기능 Backtracking, 문자열 역순배치 같은 곳에서 사용됩니다.

참고자료

• 프로세스 스케쥴링 개념 : https://reakwon.tistory.com/132

• 운영체제 개념 : https://bigpicture123.tistory.com/237