자료구조를 공부하는 첫번째 단계
리스트, 정렬, 스택과 큐!
자료구조와 알고리즘
이 두가지 주제는 프로그래밍을 시작한 이후로 가끔씩 미뤄둔 방학숙제처럼 내 마음을 부담스럽게 짓누르던 과제였다. 그리고 많은 사람들, 나보다 더 많이 공부한 사람들도 나처럼 생각하고 있다는 것을 최근에 알게되었다. 자료구조, 데이터, 데이터스트럭쳐, 알고리즘, 스택, 큐, 리스트 ... 데이터들의 관계를 정의하기 위해 붙여놓은 이러한 이름들을 마치 거창한 실체를 가진 무언가처럼 느껴 아예 시작할 엄두를 못내고 있는 것이다.
최근 회사에서 <자료구조와 함께 배우는 알고리즘 입문> 을 건네받았고, 오늘 다섯시간 정도 공부를 했다. 조금 먼저 시작한 입장에서, 혹시 나처럼 지레 겁을 먹고 있는 누군가에게 자료구조를 처음 공부할 때 머릿속에 먼저 그려두어야할 밑그림에 대해 말해주고자 한다.
첫번째,
자료(데이터) 는 그 자체로 구조이다.
a라는 변수데이터를 선언하고 1이라는 정수를 담으면 데이터는 그 자체로 구조를 갖는다. 자료구조에는 단순구조, 선형구조, 비선형구조, 파일구조 라는 네가지 형태가 있는데, 그중 단순구조의 자료형들에 대해서는 우리는 이미 아주 잘 알고 있다. 정수, 실수, 문자, 문자열이 여기에 해당한다. 모든 정수, 실수, 문자, 문자열은 자료이다. 파이썬에만 한정된 것인지는 잘 모르겠지만, 파이썬에서 id 를 검색하면 모든 자료들은 고유의 식별번호를 가지고 있다. 변수에 그 자료를 담으면, 변수도 같은 식별번호를 공유하게 된다. 실제로는 좀더 긴 식별번호들을 갖지만 예를 들어, id(1) = 100 , id(2) = 200 라면 'a = 1' 이라고 선언했을 때에는 id(a) = 100 이 된다. 'a = 2' 라고 선언하면 id(a) = 200 이다. 즉, 개별 숫자와 문자들은 고유의 아이디를 가진 자료이다. 어딘가에 다른 집합 혹은 알고리즘 안에 섞여들어가 다른 자료와 관계를 맺을 운명인 것이다.
더 복잡한 자료구조들과 마찬가지로 단순구조 형태의 자료들 역시 그 자체로 구조를 갖는다. 하지만 우리는 하나의 문자열이나 1부터 10까지의 정수들을 관리할 방법을 고민하지는 않는다. 자료구조의 관리에 대한 고민은 자료들이 여러개가 모이면서부터 시작된다.
두번째,
임시로 저장할 자료인지, 오랫동안 보관할 자료인지에 따라 효율적인 관리방법을 정하는 것이 자료구조의 핵심이다.
여러개의 단순구조 자료들은 보통 배열에 담아 관리한다. 나는 여기서 '배열' 이라는 단어를 엄밀한 의미로 사용하기 보다는, 조금 모호하게 '여러 자료들이 나열된 집합' 이라는 의미로 사용할 것이다. 혹시 이 부분을 읽으면서 머릿속에 기다란 숫자의 나열 ([1,2,3,4,5,6,7,8,9,10,11 ... ]) , 문자와 숫자들이 나열된 모습([1, 2, 3, 'abc' ... ]), 문자와 숫자와 리스트들이 쭉 늘어선 모습([1, 2, 3, 'a', 'b', '['a','b','c','d'] ...]) 과 같은 리스트 형태를 그렸다면 그 그림을 이어서 그려나가면 된다. 나는 처음 프로그래밍을 공부하면서 '배열' 이 괄호의 모양(소괄호, 중괄호, 대괄호)에 따라 여러가지 종류로 나눠진다는 것을 알고 충격을 받았었다. 배열이라고 하면 자연스럽게 연상되는 '단순히 길게 늘어지는 집합'의 모습을 애써 지워야만 해서 머리가 복잡했었다. 그러나 자료구조에 있어서 만큼은 배열을 조금 단순하게 바라볼 필요가 있다고 생각하게 되었다. 왜냐하면 자료구조를 활용함에 있어서, 특히 공부 초반이라면 대부분의 자료들을 대괄호로 이루어진 리스트에 넣고, 빼고, 정리할 것이기 때문이다.
선형구조의 자료구조를 대할 때 핵심은 임시보관함과, 최종적으로 자료가 도착할 영구보관함을 구분하는 일이다. 100만명의 유저데이터가 있을 때, 이들 중 상품을 구매한 유저들, 환불을 요청한 유저들, 등등 각각의 유저들을 관리하기 위한 목적에 맞는 보관함이 있을 것이다. 무수히 많은 유저데이터를 모든 보관함에 동일하게 담는다면 자원이 낭비될 것이고, 별도의 함수를 만들지 않고 사람이 하나하나 원시적으로 골라내어 각각의 보관함에 넣는다면 중간에 유실되어 죽은데이터가 되는 자료들이 생길 것이다. 우리는 결코 실수하지 않는 컴퓨터에게 이 분류하고, 빼내고, 저장하는 일을 맡기기 위해 알고리즘을 만든다. 이때 한 보관함에서 다른 보관함으로 모든 자료들이 한방에 이동하기 어려울 수도 있다. 이럴 때 임시보관함을 만든다. 드디어 스택과 큐가 등장하는 것이다.
줄서기를 뜻하는 큐(Queue) 의 경우, 정해진 용량을 다 채우면 가장 먼저 들어간 자료가 가장 먼저 나간다. 반대로 스택(Stack)은 가장 늦게 들어간 자료가 먼저 나간다. 입구가 하나뿐인 좁은 방을 생각하면 이해가 쉽다. 리스트와 달리 스택과 큐는 데이터 자체보다는 데이터가 차지하는 메모리 관리를 위해 활용하는 자료구조인 것 같다. 리스트로만 자료를 관리하면, 리스트가 빠져나간 자리가 비게 되고, 그러면 쓸데없이 비는 공간이 생기기 때문에 그러한 낭비를 막기 위해 임시 보관함에 해당하는 스택과 큐라는 자료구조가 선형구조 안에 만들어진 것이라고 생각하자.
세번째,
자료를 관리하기 위한 알고리즘은 효율적으로 넣고, 검색하고, 빼내는 절차이다.
알고리즘이란 '문제를 해결하기 위한 절차'라는 포괄적인 의미를 가진다. 효율적인 자료관리를 위한 방법도 알고리즘으로 구현할 수 있고, 이때 자료구조와 그 안에 있는 자료형들의 특성을 고려해 좋은 알고리즘을 구현하는 것이 자료구조와 알고리즘 공부의 최종적인 목표라고 할 수 있다.
내가 보는 책에서는 리스트를 정렬하는 정형화된 알고리즘 여덟개가 상당히 많은 지면에 걸쳐서 소개된다. 그리고 뒷부분에 가면 리스트의 종류에 대해서도 자세하게 구분한다. 비선형 자료구조에 해당하는 트리구조 이야기는 맨 뒷부분에 두 챕터에 걸쳐서 소개된다. 그만큼 우리가 다루는 자료구조에서 리스트가 중요하다는 의미일 것이다. 리스트와 정렬 알고리즘을 다양하게 파악하고 익숙해져있으면, 어떤 자료를 만나든지 효율적으로 핸들링할 수 있을 것이다.
프론트엔드 개발자로서, 데이터를 다룰 때 선형구조 말고 다른 자료구조를 활용할 일이 과연 있을까 싶다.
하지만 최근 회사에서 쇼핑몰 데이터를 핸들링하면서 상상도 못한 복잡함에 당황했던 걸 생각하면, 나의 이런 생각을 부숴줄 복잡한 자료구조를 만날 일이 있을 지도 모르겠다. 내심 설레기도 하고.
다음주 주말에는 리스트와 정렬 알고리즘에 대한 글로 돌아올 것이다. 반드시!
Photo by Halacious on Unsplash
