자료구조를 공부하기 위한 5가지 단계

프로그래밍 언어를 어느정도 배우고 나면 그 다음엔 보통 자료구조를 공부하게 된다. 어떤 공부를 하든 마찬가지겠지만 자료구조를 공부하면서도 어디서부터 어떻게, 얼마나 공부해야 자료구조를 '공부했다'라고 할 수 있는지 고민하는 경우가 많다. 이 포스트에서는 자료구조를 공부를 다섯단계로 나누어 설명하고 자료구조를 공부하기위한 템플릿을 제공하도록 한다.

참고! 이 포스트는 자바를 기준으로 작성되었다.

목차

• 1단계 : 자료구조의 목적과 이론 이해
• 2단계 : 자료구조의 구현 로직 따라가기
• 3단계 : 자료구조의 형태와 오퍼레이션 직접 구현하기
• 4단계 : 라이브러리를 이용해 자료구조 사용하기
• 5단계 : 자료구조를 적용하여 문제 해결하기

1단계 : 자료구조의 목적과 이론 이해

컴퓨터 공학의 주된 목적은 문제를 해결하는 것이라고 했다. 자료구조도 마찬가지로 문제를 해결하기 위해 만들어졌다. 따라서 이 자료구조가 해결하고자 하는 문제가 무엇인지(목적) 이해하고, 어떻게 해결하는지(이론), 또 메모리상에서 이 자료구조가 어떻게 존재하는지 등을 처음으로 공부하게 될것이다. 예를들어 링크드 리스트를 보자.

대부분의 자료구조 책이나 인터넷 사이트들은 독자의 자료구조 이해를 돕기위해 위와 같은 다이어그램을 사용한다. 우리의 목표는 해당 다이어그램의 요소들이 의미하는것을 이해하는 것이다. 또한 위와 같은 자료가 어떤 문제를 어떻게 해결하는지 숙지해야 한다. 이는 대부분 자료구조의 오퍼레이션 성능과 관련이 있다. 예를들어 삽입 오퍼레이션의 시간 복잡도는 O(1), 검색 오퍼레이션의 시간 복잡도는 O(n)이다. 따라서 삽입이 많이 요구되는 문제를 해결해야 하는 경우 적절하다는 결론을 내릴 수 있다. 이 단계에서는 오퍼레이션의 복잡도와 구현이 글로 설명되어 있다. 예를들어서, 삽입의 경우 '헤드에 삽입하는 경우 새 노드를 헤드로 지정하고 이전 헤드를 연결 해 주면 되므로 시간 복잡도는 O(1)이다.'정도의 줄 글로 된 설명이 나온다. 복잡한 오퍼레이션의 경우 바로 구현으로  넘어갈 수도 있지만 이 단계에서는 구현에 대해 자세히 생각하지 않아도 된다. 자료구조의 목적과, 다이어그램과, 오퍼레이션을 이해하면 된다.  

- 이 자료구조는 어떻게 생겼나?

- 이 자료구조에는 어떤 오퍼레이션이 있는가?

- 이 자료구조는 언제 사용하는가? (성능 관점에서)

2단계 : 자료구조의 구현 로직 따라가기

두번째 단계에서는 해당 자료구조의 구현 로직을 따라가는 연습을 하는 것이다. 이 단계에서는 종이와 펜이 반드시 필요하다. 링크드 리스트의 예를 계속 들어보겠다. 이 단계에서는 책이나 인터넷에 있는 자료구조의 구현로직을 공부할 것이다.

public class SinglyLinkedList {
    Node head;
    
    class Node {
        int data;
        Node next;

        Node(int d) { data = d; }
    }
}

예를들어서 위의 SinglyLinkedList의 구현을 보자. 이제 이 구현부분과 위에서 본 다이어그램을 연결시켜 이해해야 한다.

위 처럼 구현부분과 다이어그램을 연결시켜 이해했다면 오퍼레이션 부분으로 넘어가도 좋다.

public class SinglyLinkedList {
    Node head;

    class Node {
        int data;
        Node next;

        Node(int d) { data = d; }
    }

    public void insert(int data) {
        Node newHead = new Node(data);
        if (head == null) {
            head = newHead;
            return;
        }
        newHead.next = head;
        head = newHead;
    }
}

위는 insert 오퍼레이션을 구현한 것이다. 내가 구현한 것이므로 인터넷에 있는것과 다를 수 있다. 큰 상관은 없다 인터넷에 있는 괜찮은 구현 아무거나 사용해도 된다. 이제 위에서 말했단 종이와 펜을 꺼낸다. 그리고 임의의 자료를 생각해낸다. 여기서는 1, 3, 5를 순서대로 삽입한다고 하자. 각 과정이 어떻게 실행 되는지 종이에 적어 내려가고 시간 복잡도와 공간 복잡도에 대해 생각하라.

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.insert(1);
        list.insert(3);
        list.insert(5);
    }
}

이제 컴퓨터가 세번의 insert를 수행하는 과정을 종이에 적는다.

위처럼 다이어그램, 코드, 글을 적당히 활용하여 수행 과정을 종이에 적어내려갈 수 있어야 한다. 또 다른 예로 print 메서드를 보자.

public void print() {
    Node node = head;
    while(node != null) {
        System.out.println(node.data);
        node = node.next;
    }
}

print는 검색 오퍼레이션과 매우 비슷할 것이다. 지금은 편의를 위해 print로 하였으나 여러분이 자료구조를 공부 할 때는 검색 오퍼레이션을 가지고 이 단계를 진행 하게 될 것이다. 위에서 삽입한 5 -> 3 -> 1을 출력한다고 하자. 위의 구현 로직을 따라 메모리가 어떻게 변하는지, 뭘 출력하는지 하나하나 적어 내려가 본다.

이 작업을 마친 후 해당 구현의 시간복잡도와 공간복잡도를 계산하라. 계산 후 실제 시간복잡도, 공간복잡도와 정답은 맞춰 보아라. 이 과정을 통해 여러분은 코드의 복잡도를 계산하는 방법을 연습하게 될 것이다.

물론 모든 오퍼레이션을 이렇게 공부할 필요는 없다. 코딩 머슬이 늘면 그냥 코드를 읽어내려가기만 해도 머릿속에서 충분히 로직을 따라갈 수 있다. 하지만 그게 어렵다면 위처럼 종이에 적어 로직을 차근차근 따라하는 연습을 하는것이 좋다. 하다보면 나중에 그냥 머릿속에서 자동으로 된다. 이렇게 해서 누군가의 자료구조와 오퍼레이션의 구현을 이해하고 로직을 따라갈 수 있다는건 해당 구현을 이해하고 있다는 뜻이다.

3단계 : 자료구조의 형태와 오퍼레이션 직접 구현하기

이 단계에서는 공부했던 로직을 직접 구현해 보는 단계이다. 위에서 이미 누가 구현한 걸 다 봤는데 그럼 베낀것이나 다름 없지 않은가? 그렇지 않다. 분명히 2단계를 하고 있을 땐 여러분이 해당 로직을 암기했고 구현 할 수 있을 것 같지만, 책을 덮고 또는 사이트를 끄고 직접 구현하려 해 보면 기억이 잘 나지 않을 것이다. 그리고 기억이 나면 기억이 나는대로 그냥 구현하라. 어차피 암기한 구현은 이해하지 못했다면 나중에 절대 완벽히 기억나지 않는다. 로직을 이해하고 있어야만 암기를 하더라도 나중에 완벽히 구현할 수 있다. 그리고 본인이 100% 창조해낸 코드가 아니어도 상관 없다. 세상에 100% 자기 힘으로 창조된 코드는 별로 없고, 대부분 누군가의 코드를 참고해 수정하는 경우가 많기 때문이다. 아무튼 이제 각 자료구조와 오퍼레이션을 구현하라. 잘 모르겠으면 인터넷에 검색해 다른사람이 만든 것을 조금씩 봐도 괜찮다. 다른사람이 만든 것을 본 경우, 다 만든 후, 지우고 다시 만들어라. 다른 사람이 만든 것을 보지 않아도 될 때 까지 다 만들고, 지우고 다시 만들어라. 

2번째 단계는 [구현 -> 다이어그램]을 이해하고 만들어내는 단계라면 이 단계는 반대로 [다이어그램 -> 구현]을 하는 단계이다. 다이어그램을 그리고 그 다이어그램을 코드로 어떻게 구현할지 디자인한다. 이 단계는 매우 중요하다. 이 단계는 꼭 자료구조에만 해당되는게 아니기 때문이다. 프로젝트를 하든 알고리즘 문제를 풀든 대부분의 경우 우리는 다이어그램을 그리고 그 다이어그램을 구현하는 순서로 작업을 진행하게 된다. 자료구조를 공부하며 연습한다고 생각하면 된다.

위와 같은 다이어그램을 코드로 만들려면 어떻게 해야하는가? 아래와 같은 구조를 생각해 볼 수 있다.

public class Node {
    String data;
    Node next;

    Node(String d) { data = d; }
}

위처럼 데이터를 저장하기 위한 Node 자료구조와, 아래처럼 오퍼레이션과 리스트의 헤드를 가지고 있을 SinglyLinkedList를 만들 수 있다.  

public class SinglyLinkedList {
    Node head;

    public void insert(String data) {
        Node newHead = new Node(data);
        if (head == null) {
            head = newHead;
            return;
        }
        newHead.next = head;
        head = newHead;
    }

    public void print() {
        Node node = head;
        while(node != null) {
            System.out.println(node.data);
            node = node.next;
        }
    }
}

모든 오퍼레이션을 다 구현할 필요는 없지만 대표적으로 삽입, 검색, 삭제, traverse오퍼레이션을 구현하고 넘어가는것이 좋다.

4단계 : 라이브러리를 이용해 자료구조 사용하기

여러분은 이제 자료구조의 목적과 다이어그램을 이해하고, 다이어그램을 코드로 구현할 수 있다. 그러나 아쉽게도 그게 끝이 아니다. 여러분이 사회에 나가면 자료구조를 만들어서 쓰는 일보다 라이브러리가 제공하는 자료구조를 사용할 확률이 훨씬 높다. 라이브러리는 검증된 코드를 제공하고, 여러 개발자들 사이에서 사용되므로 호환 가능성이 높다. 예를들어 우리 코드에서는 내가 만든 리스트를 쓰고 다른 팀 코드에서는 걔네가 만든 리스트를 쓴다면 우리 코드의 리스트를 다른 팀 코드에 전송할 때 마다 그 팀의 구조에 맞게 변경(transform)해야 할 것이다. 그래서 대부분은 검증되고 보편적으로 쓰이는 라이브러리의 자료구조를 사용한다. 본인이 공부하고 있는 언어가 제공하는 자료구조를 어떻게 사용하는지, 공부했던 오퍼레이션을 어떻게 사용하는지 공부하라. 예를들어 링크드리스트를 다시 보자.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(3);
        list.add(5);

        System.out.println(list.toString());
    }
}

자바의 java.util패키지는 Generic으로 구현된 여러가지 자료구조를 제공한다. 따라서 자바로 자료구조를 공부했다면 java.util패키지가 제공하는 자료구조 클래스의 사용법을 익히는 것이 좋다.

5단계 : 자료구조를 적용하여 문제 해결하기

마지막 단계로는 이 자료구조를 사용하는 연습을 하는것이다. 리트코드같은 코딩 연습 사이트는 대부분 자료구조 카테고리별로 연습문제를 제공한다. 예를들어 리트코드에서 링크드 리스트 관련 문제는 https://leetcode.com/tag/linked-list/ 여기서 찾을 수 있다. 리트코드 뿐만 아니라 해커랭크, 백준, 알고스팟 등 다양한 사이트에서 자료구조 카테고리 별 문제를 제공한다. 이 단계에서는 본인 공부하고있는 자료구조가 보통 어떤 문제를 해결하기 위해 사용되는지, 또 어떻게 사용하는지를 연습해 볼 수 있다. 예를들어 리스트의 순서를 거꾸로 하는 예제를 보자. (https://leetcode.com/problems/reverse-linked-list/)

Input : 5 -> 3 -> 1

Output : 1 -> 3 -> 5

이제 여러분은 위 사이트에서 말하는 ListNode가 뭘 뜻하는지 안다. 여러분이 직접 구현해 봤기 때문이다. 또한 리스트의 방향을 바꾸기 위해 여러분은 종이에 다이어그램을 그릴 것이다. 노드를 하나씩 지나면서 무슨일이 일어나는지 생각해 볼 것이다. 

이는 3단계에서 했던 작업과 매우 비슷하다. 이제 다이어그램 -> 구현으로 넘어가기만 하면 된다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode o_head = head;
        ListNode n_head = null;

        while(o_head != null) {
            ListNode node = o_head;
            o_head = o_head.next;

            node.next = n_head;
            n_head = node;
        }
        return n_head;
    }
}

어떤 문제들은 너무 쉬워 머릿속에서 바로 떠오르기도 한다. 그렇지 않은 문제는 종이에 적어가며 차근차근 풀어가면 된다. 그래도 모르겠으면 다른사람이 어떻게 풀었나 보면서 공부하면 된다. 자료구조를 공부하기 위한 5단계중 마지막 5단계는 자료구조에서 알고리즘 공부로 넘어가는 단계이다. 자료구조는 대부분 알고리즘과 함께 사용된다. 따라서 이 자료구조를 이용해 문제를 해결하면 몰랐던 알고리즘을 공부하게 될 수도 있고, 알고 있던 알고리즘이지만 생각하지 못했던 방법으로 문제를 해결하게 될 수도 있다. 이렇게 하고나면 이제 여러분은 이 자료구조를 안다, 공부했다라고 할 수 있다.

끝

이 포스트에서 설명한 5 단계를 축약해보면 [이론/디자인이해 -> 구현이해-> 직접구현 -> 라이브러리 사용 -> 문제해결]임을 알 수 있다. 이는 꼭 자료구조뿐만 아니라 알고리즘, 네트워크, 운영체제 등등 컴퓨터 공부의 전반에 걸쳐 사용될 수 있는 템플릿이다. 프로젝트를 할 때도 마찬가지이다. 일단 다른 사람들은 어떻게 디자인을 했나 비슷한 디자인을 찾아보고, 구현을 이해해보고, 그들이 사용하는 라이브러리를 사용해보고 그들의 디자인과 구현을 변형해 본인의 프로젝트에 적용(문제해결) 할 수 있다. 이러한 일련의 과정을 자료구조와 알고리즘을 공부하며 연습하다보면, 사회에 나가서도 비슷한 방법으로 여러가지 문제를 해결할 수 있게 될 것이다.