6.24 Dev.Feedback (자료구조 / 알고리즘)

자료구조란?

여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것

 

자료구조를 설명하기 전, data에 대해 먼저 정리해보면, 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다. 하지만, Data 그 자체만으로 어떤 정보를 나타내기는 힘들다. 나이라는 데이터가 있다고 해서 그 나이가 어떤 사람, 동물 혹은 식물의 나이인지 지칭을 할 수 없다는 것을 예시로 들 수 있다.

즉 어떤 데이터의 정보를 정확하게 알려면 먼저 분석하고 정리를 해야만 한다.

 

위의 말처럼 우리가 데이터의 정보를 정확하게 알게 됐다면, 이제 분류를 해야한다.

결국 데이터는 우리가 사용하려는 목적에 따라 형태를 구분하고 분류하여 그 목적을 이루게 도와주는 자료이기 때문이다. 따라서 우리가 어떤 데이터를 정확하게 사용하기 위한 분류를 위해선 우리가 분석한 데이터가 어떤 목적에 쓰이는지 정확하게 파악할 필요가 있다. 그리고 각 목적에 맞게 체계적으로 정리하여 저장을 하는 것이 데이터를 활용하는데 있어 훨씬 유리하다.

 

이런 분류들을 정확하게 하기 위해 그리고 체계적으로 정리하여 적재적소에 데이터들을 사용하기 위해 효율적인 방안들을 고안해낸 것이 바로 자료구조이다.

 

수 많은 자료구조가 있지만, 그 중 가장 흔하게 쓰이고, 알고리즘 테스트에도 자주 등장하는 네 가지를 정리해보려 한다.

(다른 자료구조들도 검색을 해서 알아보자)

 

Stack, Queue, Tree, Graph

각각의 자료구조들을 사용하기 위해 4가지의 단계를 거쳐 학습하려 한다.

• 각 자료구조가 가진 특징을 학습한다.
• 각 자료구조를 사용하기 적합한 상황을 이해한다.
• 다른 자료구조와의 차이점을 이해하기 위해 자료구조 내부를 직접 구현한다.
• 자료구조를 구현하며, 자료구조의 동작원리를 이해한다.

각 부분들에 대해서 최대한 기록을 남기면서 정리하는 것이 좋을 것 같다.

Stack

데이터를 순서대로 쌓는 자료구조

특징은 위의 정의 그대로 차곡 차곡 쌓이는 구조이다 보니 입력과 출력이 하나의 방향으로 이루어지게 되고, 자료에 접근하는 방법이 제한적이다. 이런 Stack 자료구조의 정책을 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부르기도 한다.

 

ex) 1자로 이뤄진 실린더에 먹으려고 하는 동일한 크기의 영양제를 하나씩 넣는다. 차곡 차곡 하나씩 넣다가, 먹으려는 순서에 맞지 않게 넣었다는 사실을 깨닫는다. 하지만, 결국 넣은 순서대로 꺼내야 하기때문에 뒤에서부터 하나씩 다시 꺼내야하는 상황이 벌어진다.

 

Stack의 실사용 예제

대표적인 상황으로는 우리가 사용하는 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 사용된다.

 

브라우저에서 자료구조 Stack이 사용될 때에는 다음과 같은 순서를 거친다.

 

1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관한다.

2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.

3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는, Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.

4. 마지막으로 현재 페이지를 Prev Stack에 보관한다.

Queue

 

데이터가 줄을 서서 기다리는 대기 행렬 구조

Stack과 반대되는 개념이다. 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징으로 가지고 있다.

이해가 가장 쉬운 비유로는 톨게이트를 생각하는 것이 좋다.

여기서 톨게이트를 Queue 자료구조로, 자동차를 data로 생각하면 된다.

즉 톨게이트처럼 순서대로 진입한 데이터들을 순서대로 인식하여 처리한다는 것이고, 즉 Queue 자료구조는 데이터가 입력된 순서대로 처리할 때 주로 사용된다.

 

Queue의 실사용 예제

 

대표적인 상황으로는 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄할 때를 생각해보면 된다.

 

1. 우리가 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 (임시 기억 장치의) Queue에 들어간다.
2. 프린터는 인쇄 작업 Queue에 들어온 문서를 출력 버튼을 눌러 들어온 데이터의 순서대로 인쇄한다.

컴퓨터(출력 버튼) - (임시 기억 장치의) Queue에 하나씩 들어옴 - Queue에 들어온 문서를 순서대로 인쇄

 

위 예시에서 볼 수 있듯, 컴퓨터 장치들 사이에서 data를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용한다.

 

위의 작업 전체를 통틀어 Buffer라고 한다.

대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생한다. 
이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖는다. 
불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용한다.

좌측이 CPU가 이벤트를 규칙적으로 처리한다는 것을 보여주는 그래프

우측은 CPU를 제외한 다른 컴퓨터 장치에서의 이벤트 처리를 보여주는 그래프

 

• 일반적으로 프린터는 속도가 느리다.
• CPU는 프린터와 비교하여, 데이터를 처리하는 속도가 빠르다.
• 따라서, CPU는 빠른 속도로 인쇄에 필요한 데이터(data)를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행한다.
• 프린터는 인쇄 작업 Queue에서 데이터(data)를 받아 일정한 속도로 인쇄

즉, Buffering은 느리고 불안정한 컴퓨터 장치의 상태를 인정하고 CPU에서 전달한 작업을 최대한 안정적으로 실행하기 위해 Queue 자료구조에 각 데이터를 순서대로 저장하는 작업이다. 정말 특별한 경우가 아니라면, 버퍼링 작업이 끝나기 전에는 어떤 작업이 바로 수행되지 않는다.

 

 

우리가 인터넷에서 영상을 볼 때, 버퍼링이 걸리는 이유는 Queue 자료구조에 다운로드 된 데이터가 영상을 재생하기에 충분하지 않아서, Queue 자료구조에 데이터를 저장하는데 시간이 더 필요해서였다!!!! 이제서야 깨닫게 된다...