대부분의 대학 컴퓨터관련 학과에서 2학년에 배우는 과목 중에 가장 중요한 과목은 자료구조 (Data structure) 혹은 데이터구조이다. 아래는 미국 명문 스탠포드 대학교 (Stanford university)의 컴퓨터과학과 (Department of computer science)에 편성된 전공필수과목인 "Data structures and Algorithms"과목에 대한 설명이다. 이 과목이 바로 데이터구조 과목인 것이다.
2. 데이터구조, 기술면접의 핵심
데이터구조 과목에서 배우게 되는 것들이 요즘 취업면접과정에서 흔히 기술면접과정에서 흔히 나온다. 예를 들어 숫자정렬, sorting이라는 것이 있다. 10, 6, 4, 1, 45, ... 와 같이 무작위 순서로 숫자들이 주어졌을 때 이들 숫자를 오름차순 혹은 내림차순으로 정렬하는 것을 sorting이라고 한다. Sorting하는 방법은 크게 4가지가 있는데, 기술면접에서는 이들 중에서 한 가지를 직접 구현해 보도록 시키는 경우가 많다고 한다. 물론 이 정도 문제는 난이도가 쉬운 편에 속한다. 기술면접 문제의 대부분은 이 데이터 구조에서 나온다.
미국의 구글, 페이스북, 마이크로소프트 같은 회사들은 오래 전부터 직원채용 면접을 할 때 코딩면접을 시행해 왔는데, 여기에서 데이터구조의 내용을 많이 물어본다고 한다. 면접이 진행되는 방식은 다음과 같다. 면접은 작은 회의실 같은 곳에 진행되는 데, 거기에는 화이트보드, 즉 칠판이 하나 있다. 면접자가 문제를 주면, 피면접자는 화이트 보드에 문제를 풀기위한 핵심코드나 아이디어를 써 가면서 설명해야 한다.
3. 핵심개념: 데이터는 컴퓨터가 처리할 수 있는 모든 것이다.
컴퓨터 영역에서 데이터는 무엇이든 될 수 있다. 회사의 재정정보를 나타내는 숫자일 수도 있고, 개인이 운영하는 블로그의 글이 될 수도 있고, 유튜브 같은 곳에서 서비스하는 동영상이 될 수도 있고, 멜론에서 보내주는 음원이 될 수도 있다. 또는 정류장의 버스 도착정보가 될 수도 있다.
4. 핵심개념: 데이터구조는 데이터를 어떻게 배치할 것인가에 대한 것이다.
데이터구조는 사실 두 단어의 합성이다. 즉 데이터 + 구조 이다. 순 우리말로는 자료구조, 순 영어로는 data structure. 영어의 data와 우리 말의 구조를 합쳐서 데이터 구조라고 한 것이다. 물론 자료구조라고 해도 되고, data structure라고 해도 된다.
데이터구조를 비유를 통해 설명해 보자. 교실 안에 학생들이 있다고 하자. 이 때 학생들은 데이터가 된다. 마침 수업이 토론수업이면 4명씩 서로 마주보면서 앉는 것이 수업하기에 편할 것이다. 그렇지 않고, 선생님이 설명하는 강의라면 줄을 지어 앉는 것이 효율적일 것이다. 점심배식을 할 때는 한 줄로 늘어서서 식판에 밥을 받아가는 것이 좋을 것이다. 이렇듯 데이터구조는 데이터의 배치형태를 말한다. 이러한 배치형태는 굉장히 많기 때문에 매우 다양한 데이터구조들이 가능하다. 하지만 필요와 상황에 따른 적절한 데이터구조는 판단할 수 있을 것이다. 예를 들어, 토론수업시간에 학생들이 일렬로 줄지어 서는 것보다는, 4명씩 짝지어 마주 보고 앉는 것이 더 바람직한 것처럼 말이다.
이미 유용하다고 알려진 데이터구조들이 많다. 그래서 데이터구조 과목에서는 이러한 것들을 배우게 된다. 그런데 이런 데이터구조들 각각은 레고조각과 같아서, 서로 다른 구조들을 합성해서 또 다른 구조들을 만들어낼 수도 있다.
5. 핵심개념: 알고리즘은 컴퓨터가 어떤 문제를 처리하기 위한 절차, 순서를 말한다.
컴퓨터에게 다음과 같은 일을 시킨다고 가정하자. 숫자 10개를 주고 짝수에는 모두 1씩 더해서 홀수로 만들고, 홀수는 2를 곱해서 짝수로 만든다고 하자. 과연 컴퓨터에게는 이 일을 어떻게 지시해야 할까? 사실 컴퓨터에게 일을 시킬 때에는 아주 구체적으로, 세세히 단계단계 설명해 줘야 한다. 예를 들어 다음과 같다.
1단계: 숫자를 읽는다.
2단계: 1단계에서 읽은 숫자가 짝수이면, 그 숫자에 1을 더한다. 4단계로 간다.
3단계: 1단계에서 읽은 숫자가 홀수이면, 그 숫자를 두 배한다.
4단계: 10개 숫자를 모두 읽어서 처리를 끝냈으면 일을 끝낸다. 아니면 1단계부터 다시 반복한다.
위에서 설명한 1~4단계와 같이 컴퓨터가 일을 처리하는 절차를 정의한 것을 알고리즘이라고 한다. 이 알고리즘은 주어진 문제 (10개 숫자를 짝수와 홀수에 따라 변환)를 처리하기 위한 절차이다. 문제가 간단하기 때문에 알고리즘이 매우 간단했다. 보다 복잡한 문제라면 알고리즘도 복잡해 질 것이다. 정리하자면, 알고리즘은 주어진 문제를 해결하기 위해 컴퓨터가 수행해야 하는 절차를 규정한 것을 말한다.
6. 알고리즘의 표현: 글, pseudo code, 순서도
알고리즘을 표현하는 방법은 크게 세 가지라고 할 수 있다. 첫 번째 방법은 그냥 글로 쓰는 것이다. 위에서 1~4단계도 글로 표현한 예가 되겠다. 이렇게 했을 때 단점은 군더더기가 많아진다는 것이다. 그래서 나온 것이 pseudo code이다. Pseudo는 "수도"라고 읽는다. P가 묵음이다. 뜻은 "의사"인데, '비스무리 하나, 그것은 아님', 혹은 '사이비' '비슷한 것'이다. 즉, 프로그래밍 언어로 코딩한 것 처럼 보이는데, 코드는 아닌 것을 말한다. 얼핏보면 프로그래밍해 놓은 것처럼 보이는데, 자세히 보면 문법에 맞지 않는 엉성한 코딩이다. 비록 프로그램은 아니지만 의도한 바를 깔끔하게 표현할 수 있는 장점이 있다. 마지막 방법은 순서도이다. 그림으로 그리는 것이다. 화살표와 네모 등을 이용한다. 네모는 각 단계, 화살표는 단계 간의 이동을 나타낸다. 그림이니까 접근하기 쉽다는 장점이 있다.
7. 어느 알고리즘이 좋은가? 시간 복잡도와 공간 복잡도 - 설렁탕집 비유
우선 시간복잡도와 공간복잡도라는 생소한 용어부터 설명해보도록 하겠습니다.
시간복잡도를 비유를 통해 설명하면 이렇습니다. 설렁탕 집이 하나 있다고 합시다. 거기가서 설렁탕 한 그릇을 주문문했을 때, 설렁탕이 나올 때까지 걸리는 시간은 손님이 몇 명있느냐에 따라 다를 겁니다. 상식적으로 생각했을 때 손님 수에 비례적으로 시간이 길어지는게 당연합니다. 이렇게 손님 수에 따라 음식나오는 시간이 어느 정도 길어지는지를 이 설렁탕집의 시간복잡도라고 합니다.
설렁탕집 마다 시간복잡도는 다를 수 있습니다. 여기 두 개의 설렁탕집이 있다고 합시다. 하나는 "똑똑 설렁탕집"이고, 다른 하나는 "정성 설렁탕집"이라고 합시다. "똑똑 설렁탕집"은 큰 가마에 설렁탕 국물을 많이 끓여 놓았다가 그릇에 담아 내는 방식으로 하고, "정성 설렁탕집"은 주문을 받으면, 그 때부터 사골넣어서 끓여 낸다고 합시다. 자 이제 두 설렁탕집에 점심시간이 되어 손님들이 들이 닥치기 시작했다고 합시다. 어느 설렁탕집에 가는 것이 기다리는 시간이 짧을까요? 당연히 똑똑 설렁탕집이겠지요. 유식한 말로 하자면, 똑똑설렁탕집은 시간복잡도가 낮고, 정성설렁탕집은 시간복잡도가 높다고 합니다.
알고리즘의 시간복잡도는 입력되는 데이터 크기 (개수)에 따라 낮다, 높다 라고 말합니다. 데이터 개수가 많아질 수도록 수행되는 데 시간이 많이 길어지면 시간복잡도는 높은 것입니다. 반대로 개수에 상관없이 시간이 일정하거나, 조금만 늘어나면 시간복잡도는 낮은 것입니다. 시간복잡도는 낮을수록 좋은 겁니다.
공간복잡도도 비유를 통해서 설명해 보면 이렇습니다. 또 설렁탕 집을 예로 듭시다. 똑똑 설렁탕 집은 테이블에 모르는 사람들도 같이 앉아서 먹도록 했고, 정성 설렁탕 집은 한 사람이 테이블을 차지하고 여유 자리가 있어도, 그 테이블에는 다른 사람을 앉히지 않는다고 합시다. 점심시간에 두 설렁탕집에 모두 똑같이 100명의 손님이 들이닥쳤다고 합니다. 이 손님들을 모두 한 번에 앉히기 위해서, 어느 설렁탕 집에 더 많은 테이블이 필요할까요? 당연히 정성 설렁탕집입니다. 즉, 정성설렁탕집은 손님이 많이 오면 올수록 필요한 테이블 수가 똑똑 설렁탕집보다 많을 겁니다. 이를 유식한 말로, 똑똑설렁탕집은 공간복잡도가 낮고, 정성설렁탕집은 공간복잡도가 높다고 합니다.
알고리즘의 공간복잡도는 입력되는 데이터의 크기 (개수)가 늘어날 때 필요한 저장공간이 늘어나는 정도를 말합니다. 공간복잡도가 낮은 알고리즘은 높은 알고리즘보다 필요공간이 더 느리게 늘어납니다. 공간복잡도도 시간복잡도처럼 낮을수록 좋은 겁니다.
물론, 설렁탕집 손님입장에서는 똑똑설렁탕집 보다는 정성설렁탕집을 선호하는 사람들이 있을수도 있겠지만요.
참, 시간복잡도는 영어로 time complexity, 공간복잡도는 space complexity라고 합니다. 시간과 공간에 해당하는 단어는 쉬운데, 복잡도가 조금 그렇지요. 복잡도는 complexity라는 단어를 씁니다.
8. 네이버지식인과 시간복잡도/공간복잡도: 회사 기술면접 기출문제
시간/공간 복잡도 개념이 머리속에 잘 자리잡도록 아래 문제를 생각해 봅시다. 실제로 모회사의 기술면접에서 나온 문제입니다. 뭔가 긴장이 되죠..
네이버지식인 서비스를 잘 알겁니다. 자 문제 나갑니다. "네이버지식인 서비스를 제공하는 회사 입장과 이를 사용하는 유저 입장에서 시간복잡도와 공간복잡도를 논하시오." 정답은 없습니다. 이 문제의 의도는 시간복잡도와 공간복잡도 개념을 제대로 이해하고 있는지를 평가하기 위한 것입니다.
정답은 아니겠지만, 하나의 답을 만들어보자면 이렇습니다. 유저입장에서는 시간복잡도가 훨씬 중요합니다. 공간복잡도는 신경쓸 필요도 없지요. 예를 들어, 시간복잡도가 높으면, 동시접속 유저 수가 많아짐에 따라 검색결과를 얻을 때까지 기다려야 하는 시간이 길어진다는 것입니다. 유저들은 동시접속이 아무리 많더라도 상관없이 빠른 시간에 결과를 보기를 원하는 것이 당연합니다. 따라서, 유저입장에서는 시간복잡도가 낮은 것이 중요합니다. 공간복잡도가 높으면, 동시접속 수가 많을 수록 저장공간 (메모리, 디스크)이 더 많이 필요하다는 것인데, 그건 회사가 돈을 들여 해결할 문제이고, 유저의 문제는 아닙니다. 회사입장에서는 어떨까요? 회사도 시간복잡도가 공간복잡도보다 중요할 겁니다. 동시접속이 많아졌다고 검색시간이 길어지면 유저들은 더 이상 이 서비스를 사용하지 않게 되기 때문입니다. 그렇다고 공간복잡도를 무시할 수는 없습니다. 메모리, 디스크를 더 많이 사용하면 그게 다 돈이 드는 것이기 때문입니다. 그렇지만, 하드웨어 가격이 빠르게 하락한다는 점을 고려하면, 회사는 공간복잡도를 개선하기 보다는 시간복잡도를 개선하여, 더 많은 유저들을 서비스에 끌어모으는 것이 좋을 겁니다. 포털같은 서비스에서는 "사람이 돈"이기 때문입니다.
9. 구글에 입사하고 싶은가? 그러면 시간/공간 복잡도를 손에서 놓지 말게.
해외회사는 물론 요즘은 국내회사들도 개발자를 채용할 때, 프로그래밍 면접을 봅니다. 그 면접에서 프로그램을 완성해서 문제를 푸는 것도 중요하지만, 진짜 핵심은 완성된 프로그램의 시간/공간 복잡도를 평가, 분석할 수 있고, 그것을 개선할 수 있는 여지를 찾아내어 프로그램을 수정하는 능력까지 보여줘야 하는 것입니다. 그러니, 앞으로는 프로그램을 짰다 하고, 거기서 끝낼 것이 아니라 복잡도가 어떤지 생각해보고, 더 좋은 방법은 없는지 생각해 봐야 할 것입니다.
시간복잡도를 보자면
같은 것도 있다.