[알고리즘] 자료구조

배열과 문자열

---

배열에 대한 질문이나 문자열에 대한 질문들은 서로 바꿀 수 있습니다. 다시 말해, 배열에 관한 것들은 문자열에 대한 문제로 바꿔 출제할 수도 있으며, 그 반대도 가능합니다.

해시 테이블

해시 테이블은 효율적인 탐색을 위한 자료구조로서 키(Key)를 값(Value)에 대응시킵니다. 해시 테이블을 아주 간단히 구현하는 경우, 배열과 해시 함수만 있으면 됩니다. 객체와 키를 해시 테이블에 넣게 되면 우선 해시 함수가 키를 정수값으로 대응시키는데, 이 정수값이 배열의 인덱스로 쓰입니다. 객체는 배열의 해당 인덱스 위치에 저장됩니다.

하지만 이렇게 구현해서는 제대로 동작하지 않을 것입니다. 모든 가능한 키에 대해서 해시 함수가 계산해 내는 정수값이 유일해야 하기 때문입니다. 유일성이 보장되지 않을 경우 데이터가 덮어쓰기 되는 일이 생길 것입니다. 그런 충돌(collision)을 피하려면 가능한 모든 키 값을 전부 고려해서 배열을 극도로 크게 만들어야 합니다.

그렇게 큰 배열을 할당하고 객체를 hash(key) 위치에 저장하는 대신, 배열은 더 작게 만들고 객체는 hash(key)%array_length 위치에 연결 리스트(linked list) 형태로 저장하는 방법을 쓸 수도 있습니다. 그 경우, 특정한 키 값을 갖는 객체를 찾아내려면, 해당 키에 대한 연결 리스트를 탐색해야 합니다.

대신, 이진 탐색 트리(binary search tree)를 사용해 해시 테이블을 구현할 수도 있습니다. 그렇게 하면 O(log n) 시간 안에 탐색이 완료되도록 보장할 수 있습니다. 트리의 균형(balance)을 유지할 수 있기 때문입니다. 처음에 배열을 크게 잡아둘 필요도 없기 때문에 저장 공간도 절약됩니다.

면접 전에, 해시 테이블 구현과 사용에 익숙해지도록 연습할 것을 권합니다. 면접 때 가장 보편적으로 물어보는 자료구조이므로, 실제 면접 때에도 관련된 질문을 받을 확률이 높습니다.

public HashMap<integer, student> buildMap(Student[] students) {
    HashMap<integer, student> map = new HashMap<integer, student>();
    for (Student s : students) map.put(s.getId(), s);
    return map;
}

때로 해시 테이블을 사용하라고 명시하는 경우도 있긴 하지만, 대체적으로는 주어진 문제를 풀기 위해 해시 테이블이 필요할지를 알아내는 것은 문제를 푸는 사람이 하는 일입니다.

ArrayList(동적으로 크기가 조정되는 배열)

ArrayList는 동적으로 크기가 조정되는 배열로서, 그러면서도 O(1)의 접근시간(access time)을 유지합니다. 통상적으로 배열이 가득 차는 경우, 그 크기가 두배 늘어나도록 구현됩니다. 크기를 두배로 늘리는 시간은 O(n)이지만 자주 일어나는 일이 아니라서 대체적으로 O(1) 시간이 유지된다고 보는 것이 올습니다.

public ArrayList<String> merge(String[] words, String[] more) {
    ArrayList<String> sentence = new ArrayList<String>();
    for(String w : words) sentence.add(w);
    for(String w : more) sentence.add(w);
    return sentence;
}

StringBuffer

아래의 코드와 같이 문자열 배열을 하나로 합치려 한다고 생각해봐야합니다. 이 코드의 실행 시간은 어떨 것 같을까요? 간단하게 그냥 문자열 길이는 전부 x로 똑같고, 문자열 개수는 n이라고 가정해보겠습니다.

public String joinWords(String[] words) {
    String sentence = "";
    for (String w : words) {
        sentence = sentence + w;
    }
    return sentence;
}

문자열을 연결할 때마다 새로운 문자열 객체가 만들어지고, 연결할 문자열의 값이 문자 단위로 복사됩니다. 그러므로 첫 루프에서는 x개의 문자가 복사될 것이고, 두 번째 루프에서는 2x, 세 번째 루프에서는 3x개의 문자열이 복사됩니다. 이런식으로 하다 보면 결국 소요되는 시간은 O(x + 2x + ... + nx)가 될 것이니, 최종적으로는 O(xn^2)만큼의 시간이 걸리리라는 결론을 내릴 수 있습니다.

StringBuffer는 이런 문제를 피할 수 있도록 해줍니다. 간단히 말하자면 StringBuffer는 모든 문자열의 배열을 만들어 두고, 문자열 객체로의 복사는 필요할 때만 수행합니다.

public String joinWords(String[] words) {
    StringBuffer sentence = new StringBuffer();
    for (String w : words) {
        sentence.append(w);
    }
    return sentence.toString();
}

문자열과 배열 그리고 일반적인 자료구조를 연습해보는 좋은 방법은 스스로 StringBuffer 클래스를 한번 구현해 보는 것입니다.

연결 리스트(Linked List)

---

보관된 원소를 상수 시간에 접근할 수 있는 방법이 없고 재귀 호출이 빈번하다는 점 때문에, 연결 리스트에 관한 질문들은 많은 지원자들을 당황하게 합니다. 하지만 다행스럽게도 연결 리스트에 관한 질문들은 대개 엇비슷하며, 상당수는 기출문제들의 단순한 변형에 불과합니다.

연결 리스트 관련 문제들은 기본 개념에 아주 충실하므로, 연결 리스트를 바닥부터 만들 수 있는 능력을 갖추는 것이 중요합니다.

연결 리스트 생성

아래의 코드는 아주 기본적인 단방향 연결 리스트를 구현한 것입니다.

class Node {
    Node next = null;
    int data;

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

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

면접시에 연결 리스트에 대한 질문을 받을 때에는, 단방향 연결 리스트인지 양방향 연결 리스트인지를 확실히 해야 합니다.

단방향 연결 리스트에서의 노드 삭제

연결 리스트에서 노드를 삭제하는 연산은 직관적입니다. 노드 n이 주어지면, 그 이전 노드 prev를 찾아 prev.next를 n.next와 같도록 설정합니다. 리스트가 양방향 연결리스트인 경우에는 n.next가 가리키는 노드를 갱신하여 n.next.prev가 n.prev와 같도록 설정해야 합니다. 유의해야 할 것은 널 포인터 검사는 반드시 해야하며 필요하다면 head와 tail 포인터도 갱신해야 한다는 점입니다.

또한, C나 C++처럼 메모리 관리가 필요한 언어를 사용해 구현하는 경우에는 삭제한 노드에 할당되었던 메모리가 반환되는지 주의해야 합니다.

Node deleteNode(Node head, int d) {
    Node n = head;

    if (n.data == d) {
        return head.next; /* head가 변경된다 */
    }

    while (n.next != null) {
        if (n.next.data == d) {
            n.next = n.next.next;
            return head; /* head는 바뀌지 않는다 */
        }
        n = n.next;
    }

    return head;
}

"Runner" 기법

"Runner"(부가 포인터라고도 한다) 기법은 연결 리스트 문제에서 많이 활용됩니다. 연결 리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것입니다. 이때 한 포인터가 다른 포인터보다 앞서도록 합니다. 앞선 포인터가 따라오는 포인터보다 항상 지정된 개수만큼을 앞서도록 할 수도 있고, 아니면 여러 노드를 한 번에 뛰어넘도록 할 수도 있습니다.

예를 들어, 연결리스트 a1→a2→...→an→b1→b2→...→bn이 있다고 하겠습니다. 그리고 이리스트를 a1→b1→a2→b2→...→an→bn과 같이 재정렬하고 싶다고 하겠습니다. 이 연결 리스트의 길이는 모르지만, 길이가 짝수라는 정보는 알고 있다고 가정하면,

이때 포인터 p1(앞선 포인터)을 두고, 따라오는 포인터 p2가 한번 움직일 때마다 두 번 움직이도록 하는 방법을 사용할 수 있습니다. p1이 연결 리스트 끝에 도달하면 p2는 가운데 지점에 있게 될 것입니다. 그 상태에서 p1을 다시 맨 앞으로 옮긴 다음 p2로 하여금 원소를 재배열하도록 만들 수 있습니다. 즉, 매번 루프가 실행될 때마다 p2가 가리키는 원소를 p1 뒤로 옮기는 것입니다.

재귀 문제

연결 리스트 관련 문제 가운데 상당수는 재귀 호출에 의존합니다. 연결 리스트 문제를 푸는데 어려움을 겪는다면, 재귀적 접근법이 통할지 살펴봐야 합니다. 여기서 재귀적 접근법에 대해 깊게 다루지는 않을 것인데, 나중에 따로 한 장을 할애해 다룰 것이기 때문입니다.

하지만 재귀 호출 깊이가 n이 될 경우, 해당 재귀 알고리즘이 적어도 O(n)만큼의 공간을 필요로 할 것임은 기억하자. 모든 재귀 알고리즘은 반복적(interative) 형태로도 구현될 수 있긴 하지만, 한층 복잡해집니다.

스택과 큐

---

연결 리스트에 관한 문제들과 마찬가지로, 스택과 큐에 관한 질문들도 자료구조를 속속들이 알고 있다면 풀어내가 쉬울 것입니다. 그렇더라도 면접에서 마주치는 문제들은 꽤 까다로울 수 있습니다. 어떤 문제들은 기존 자료구조를 간단히 수정하는 것만으로도 해결 가능하지만, 어떤 문제들은 그보다 훨씬 더 도전적입니다.

스택의 구현

스택이 LIFO(Last-In-First-Out)에 따라 자료들을 배열한다는 사실을 기억해 두어야 합니다. 다시 말해 접시를 쌓아둘때와 마찬가지로, 가장 최근에 스택에 추가한 항목이 가장 먼저 제거할 항목이 된다는 것입니다. 아래는 간단한 스택 예제입니다.

public class Stack {
    private class Node {
        private Object data;
        private Node next;
        public Node(Object data) {
            this.data = data;
            this.next = null;
        }
    }
    
    Node top;
    
    public Object pop() {
        if(top != null) {
            Object item = top.data;
            top = top.next;
            return item;
        }
        return null;
    }
    
    public void push(Object item) {
        Node t = new Node(item);
        t.next = top;
        top = t;
    }
    
    Node peek() {
        return top;
    }
}

큐의 구현

큐는 FIFO(First-In-First-Out) 순서를 따릅니다. 매표소 앞에 서 있는 사람들이 움직이는 형태와 같이, 큐에 저장되는 항목들은 큐에 추가되는 순서대로 제거됩니다. 큐는 연결 리스트로 구현될 수도 있습니다. 이때 새 항목들은 연결리스트 꼬리에 추가됩니다.

public class Queue {
    private class Node {
        private Object data;
        private Node next;
        public Node(Object input) {
            this.data = input;
            this.next = null;
        }
        public String toString() {
            return String.valueOf(data);
        }
    }
    
    Node first, last;
    
    public void enqueue(Object item) {
        if(null != first) {
            last = new Node(item);
            first = last;
        } else {
            last.next = new Node(item);
            last = last.next;
        }
    }
    
    public Object dequeue(Node n) {
        if(null != first) {
            Object item = first.data;
            first = first.next;
            return item;
        }
        return null;
    }
}