데이터, 자료구조 그리고 알고리즘

지난 글에서는 자료구조에 대해 훝어봤다. 하지만 개념 하나하나를 구글링으로 검색하며 공부했기 때문인지 전반적인 흐름을 파악하는 데 아쉬움을 느껴서 이번 주에는 책방을 들러 자료구조 관련 책을 여러 권 살펴보았다. 많은 책이 있었지만 내가 고른 것은 "그림으로 배우는 알고리즘"이란 책이다. 많은 자료구조 책이 자료구조의 종류에 대해 깊게 설명하거나 많은 예시를 통해 다양한 학습을 유도하는 스타일로 이루어져있는데, 내가 원하는 것은 디테일이 아닌 전반적인 흐름을 파악하는 것이었다. 그리고 내가 고른 이 책이 데이터-자료구조-알고리즘의 구성으로 프로그래밍 기초의 흐름을 쉽게 설명해주고 있었기에 많은 공부가 되었다.

오늘은 이 책을 읽으면서 느낀 점과 익힌 내용을 정리해보려한다.

 

---

데이터, 자료구조 그리고 알고리즘이란 무엇이며 왜 필요로 하는가

 

사실 컴퓨터로 프로그램을 개발하고 완성된 프로그램을 사용자에게 제공한다는 행위는 현실 세계에서 요리를 하여 타인에게 제공하는 행위와 동일하다.(요리뿐만이 아니라 만들어서 제공하는 무엇이든 상관없다) 

 

요리에 있어서

우리는 요리를 할 때 재료들을 구매하고 각 재료들을 사용하기 좋게 분류해놓으며 레시피를 이용하여 쉽고 빠르게 맛있는 요리를 만들어낸다.

그렇지만 우리는 재료들을 구매해서 반드시 사용하기 쉽게 보관하지 않아도 된다. 조미료들과 채소 그리고 주방도구까지 그냥 한 서랍에 박아놓고 필요한 것은 그 때 그 때 뒤적여서 찾아 사용하면 되기 때문이다.

또한 특정 요리를 만들기 위해 꼭 레시피가 필요한 것은 아니다. 레시피없이 어떻게든 그 맛을 내기 위한 여러 과정을 거쳐 특정 요리를 만들어낼 수 있을 것이다.

어쨌든 내가 원하는 요리는 어떻게든 만들어 낼 수 있을 것이다. 

 

자 그러나 우리는 요리를 할 때 특정 레시피를 만들어놓고 이를 활용하며 또한 재료는 분류에 맞게 구분해놓고 어떻게 사용할 것인지 규칙을 만들어 놓는다.(예를 들어 먼저 사온 것들은 맨 앞에 배치해두고 나중에 사온 것은 뒤에다 놓는 것 처럼 말이다.) 

왜 그런것일까? 이유는 단순하다. 그게 편하니깐. 질 높은 요리를 빠르고 정확하게 만들어 낼 수 있으니깐!

 

개발에 있어서
개발도 마찬가지이다. 데이터는 요리의 재료로 비유할 수 있으며 자료구조는 각 재료들을 분류해놓고 사용하기 쉽게 보관해놓는 작업이고, 알고리즘은 요리 레시피로써 기능을 만들기 위해 가장 효율적인 루트를 알려주는 것이다.

 

사실 자료구조의 종류를 몰라도 된다. 그냥 데이터들을 그 때 그 때 분류하고 정리해서 필요할 때마다 쓰면 된다.

알고리즘이 무엇이 있는지 몰라도 된다. 어떻게든 데이터들만 있으면 그걸 내 맘대로 엮어서 어찌되었든 원하는 결과를 낼 수 있긴 하다. 

어쨌든 내가 원하는 기능을 어떻게든 만들어 낼 수 있을 것이다.

 

그러나 그럼에도 왜 많은 개발자들이 자료구조와 알고리즘을 공부할까? 그 이유는 요리와 똑같다. 질 높은 프로그램을 빠르고 정확하게 만들어 낼 수 있으니깐!

자료구조는 대량의 데이터들을 효과적으로 운용할 수 있도록 미리 정리해놓은 것이다. 보통 데이터는 한 개만으로는 활용할 수 있는 것은 아무것도 없다. 수많은 데이터들이 뭉쳐서 유의미한 값을 만들어내곤하는데 이 때 데이터들을 어떤 기준으로 모으고 또 어떤 식으로 사용하는지에 대해 오랫동안 고민하고 활용하다보니 특정 형태가 아주 유용하게 쓰이는 것을 알게 된 것이다. 이것이 바로 자료들의 구조인 자료구조이다. 대표적인 자료구조로써 배열은 우리가 매우 흔하게 사용한다. 배열은 같은 종류의 데이터들을 대량으로 한 곳에 모아둔 것이다. 같은 데이터의 유형을 모아놓고, 이들을 일렬로 나열해놓았으며, 각각 순서대로 빈틈없이 나열된 데이터들이라는 배열의 특징을 이용해서 우리는 많은 기능을 쉽게 구현하기도 한다. 이렇게 이미 정의되어 있는 자료구조 덕분에 우리는 쉽고 효율적이게 데이터를 운용할 수 있게 된다. 

알고리즘은 그럼 무엇일까? 백과에서는 알고리즘은 수학과 컴퓨터과학에서 사용되는, 문제 해결 방법을 정의한 '일련의 단계적 절차'이자 어떠한 문제를 해결하기 위한 '동작들의 모임'이라 정의한다. 즉 하나의 문제를 풀기 위한 방법론이라 할 수 있다. 문제를 풀기 위해서는 다양한 방법론이 존재한다. 아무리 정석풀이가 존재해도 우리는 아주 기똥찬 과정을 거쳐 문제를 풀어내기도 한다. 즉, 사실 문제가 있으면 "어떻게든" 문제를 풀 수는 있다. 하지만 문제를 푸는데 많은 시간이 걸리면 뭘 완성할 수가 없다. 이것저것 시도해보느라 오래걸리고 또 완성했다 하더라도 그것이 어떻게 쓰일지 모르기에 예외 상황을 마주칠 우려도 있으며 또 타인이 내 문제풀이를 이해하기 위해 추가적인 노력을 들이기도 해야한다. 우리에게 주어진 시간과 자원은 유한하다. 그렇기에 우리는 이미 오랫동안 사용되어와서 그 사용성이 증명된 알고리즘을 공부한다. 그리고 비슷한 상황이 나오면 해당 알고리즘을 통해 문제를 쉽고 빠르게 풀어내며 타인이 봤을 때도 이미 공유하고 있는 지식이기에 이해하기 훨씬 빠르다. 반대의 상황에서도 한 문제에 대한 동일한 해결법을 공유하고 있다면 내가 타인의 코드를 볼 때 쉽게 이해하고 파악할 수 있을 것이다. 

 

이것이 내가 자료구조와 알고리즘을 공부해야하고 필요하다 생각하는 이유이다.(데이터는 워낙 당연하고 기초적이라 그 필요성에 대해서는 논할 이유가 없다 생각해 생략했다) 

위와 같은 생각을 정리하며 프로그램을 만든다는 것은 현실에서 무언가 만드는 것이랑 정말 똑같다는 것을 새삼 다시 되새겼다. 개발 용어는 죄다 영어기도 하고 쉽게 와닿지 않는 경우가 많은데 앞으로 이를 현실과 결부하여 정의하면 친근하게 익힐 수 있단 생각도 하게 되었다. 컴퓨터 세계는 현실을 투영한 가상세계라고들 하는데, 그렇다는건 결국 컴퓨터 세계와 현실 세계는 1:1 관계인 것 아닐까?

여하튼, 오늘은 책을 읽으며 저번 시간에 아쉽게 느껴졌던 전반적인 흐름을 생각하고 정의할 수 있게 되었다. 마지막으로 책에서 배운 자료구조와 알고리즘을 아래에 정리해보며 오늘 글을 마치려 한다.

 

 

자료구조와 알고리즘 정리

 

■ 자료구조

 

1. 배열

데이터를 빈틈없이 나열한 자료구조. 배열은 일직선 상에 빈틈없이 데이터를 나열한 1차원 배열 그리고 사각형을 가로세로 빈틈없이 데이터를 나열한 2차원 배열, 직육면체처럼 가로, 세로, 높이에 빈틈없이 데이터를 나열한 3차원 배열 등이 있다. 

 1) 링버퍼

시작과 끝이 있는 1차원 배열의 1번째 요소와 마지막 요소를 합쳐서 '배열 마지막 요소의 다음에도 요소가 존재한다'고 만드는 자료구조. 실제로 배열 마지막 요소의 다음에는 배열 요소가 존재하지 않지만 배열의 마지막 요소를 배열 1번째 요소로 삼음으로써 원형모양으로 만들어버리는 구조이다. 

 

2. 리스트

배열처럼 순서가 있는 데이터를 관리할 때 사용하는 구조로, 배열과 비슷하나 차이점으로 배열은 데이터들이 차례대로 빈틈없이 나열되어있으나 리스트는 데이터들이 서로 연결되어있는 구조이기에 데이터들끼리 떨어져도 다음 데이터가 무엇인지 알 수 있는 구조이다. 

< 배열과 리스트 >
특정 위치의 요소를 조회하는 것이 빠른 것은 배열이 효율적이고 데이터의 삽입,삭제가 빠른것은 리스트이다. 

1) 단방향 리스트

앞쪽에서 뒷쪽을 가리키는 방향성을 가진 끈으로 순서가 있는 데이터를 연결하는 방식. 각 요소는 데이터, 다음 요소를 가리키는 포인터를 가지고 있다.

2) 양방향 리스트

앞에서 뒤를 가리키는 끈과 뒤에서 앞을 가리키는 끈 2개를 사용하여 순서가 있는 데이터들을 연결하는 방법이다. 각 요소는 데이터, 다음 요소를 가리키는 포인터, 이전 요소를 가리키는 포인터를 가지고 있다.

3) 이진트리

다음 요소를 가리키는 포인터를 최대 2개 가진 단방향 리스트의 일종이다.

4) 힙

부모 노드의 값이 항상 하위 노드의 값보다 작은 이진 트리를 나타낸다. 자식 노드끼리는 어느 쪽이 커도 상관없다. 최소값을 구하는데 효율적이다.

5) 해시 테이블

루트 배열이 있고 배열의 각 요소들이 리스트를 이루고 있는 자료구조이다. 

 

3. 스택

스택(stack)은 쌓다라는 뜻으로, 그 의미대로 데이터를 쌓아서 관리하는 방식이다. 데이터를 맨 아래부터 순서대로 쌓기 시작하고 특정 데이터를 빼고 싶다면 가장 마지막으로 쌓은 데이터를 빼면서 지울 데이터까지 접근해야할 것이다. 

이처럼 마지막에 입력된 데이터가 먼저 출력되는 특징을 갖는 데이터 관리 방식을 LIFO 또는 FILO라고 부른다.

 

4. 큐

큐(queue)는 대기 행렬이라는 뜻으로, 먼저 입력한 데이터가 먼저 출력되는 특징을 가졌다. 흔히 드는 예시로 순서를 기다리는 대기줄이 있다. 새로운 대기자는 줄의 가장 끝에 서고 대기열의 가장 앞쪽에 있는 사람부터 업무를 처리해준다. 중간에 새치기를 하는 것은 용납될 수 없는 것이다. 

이처럼 먼저 입력된 데이터가 먼저 출력되는 특징을 갖는 데이터 관리 방식을 FIFO 또는 LILO라고 부른다.

 

5. 그래프

2개 이상의 항목이 어떤 관계를 맺고 있는지에 주목하고 그 관계를 그림으로 표현한 것이다. 표현하는 항목을 정점(노드)라 부르고 각 항목들의 관계를 표현하는 선을 간선이라고 부른다. 

 

 

■ 알고리즘

세상에 문제를 어마무시하게 많고 그 문제를 푼 해답도 어마무시하게 많다. 이 뜻은 여기서 알고리즘의 종류를 나열하는 것은 무의미하다는 것이다.

책에서는 반복 처리 알고리즘, 시간 관련 알고리즘, 정렬 알고리즘, 검색 알고리즘 다양하게 나열되어있는데 이는 시간을 들여 천천히 공부해야할 것이라 생각해 여기서는 정리하지 않고 넘어가도록 하겠다.

다만 알고리즘을 왜 공부해야하는지 알고나니깐 얼른 공부해서 실제 개발에 적용해보고 싶다!!