[코딩인터뷰] 자료구조

해시테이블

효율적인 탐색을 위한 자료구조로서 키(key)를 값(value)에 대응시킨다.

 

간단한 해시테이블을 구현하기 위해선, 연결리스트와 해시 코드 함수만 있으면 된다. 최악의 경우 수행 시간은 O(N)이 된다. 충돌을 최소화 한 경우 O(1)이다.

 

또 다른 구현법으로는 균형 이진 탐색 트리를 사용하는 방법이 있다. 이 경우 탐색 시간은 O(logN)이 된다.

ArrayList와 가변 크기 배열

ArrayList 는 필요에 따라 크기를 변화시킬 수 있으면서도 O(1)의 접근 시간을 유지한다.

배열이 가득차면 통상적으로 배열을 크기를 두배로 늘리고, 이 시간은 O(n)이지만, 자주 발생하는 일이 아니라서 상환 입력 시간으로 계산했을 때 여전히 O(1)이 된다.

StringBuilder

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

문자열을 이어붙일 때마다 두 개의 문자열을 읽어 들인 뒤 문자를 하나하나 새로운 문자열에 복사해야 한다.

O(xn^2) → 1+2+...+n = n(n+1)/2

 

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

연결리스트

차례로 연결된 노드를 표현해주는 자료구조이다.

단방향 연결리스트

단방향 연결리스트는 각 노드는 다음 노드를 가리킨다.

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;
    }
};

Runner 기법

Runner(부가포인터)라고 한다.

 

연결리스트를 순회할 때 두 개의 포인터를 동시에 사용하는 것이다. 이때 한 포인터가 다른 포인터보다 앞서도록 한다. 앞선 포인터가 따라오는 포인터보다 항상 지정된 개수만큼을 앞서도록 할 수도 있고, 아니면 따라오는 포인터를 여러 노드를 한 번에 뛰어넘도록 설정할 수도 있다.

재귀문제

재귀 호출 깊이가 n이 될 경우, 해당 재귀 알고리즘이 적어도 O(n) 만큼의 공간을 사용한다. 모든 재귀 알고리즘은 반복적 형대로도 구현될 수 있긴 하지만 반복적 형태로 구현하면 한층 복잡해질 수 있다.

스택과 큐

스택

LIFO(Last-In-First-Out). 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.

스택이 유용한 경우는 재귀 알고리즘을 사용할 때.

큐

FIFO(First-In-First-Out). 큐에 저장되는 항목들은 큐에 추가되는 순서대로 제거된다.

큐는 너비 우선 탐색이나 캐시를 구현하는 경우에 종종 사용된다.

트리와 그래프

트리

트리는 노드로 이루어진 자료구조다.

• 트리는 하나의 루트 노드를 갖는다.
• 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
• 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

트리에는 사이클이 존재할 수 없다.

이진트리

각 노드가 최대 두 개의 자식을 갖는 트리를 말한다.

이진탐색트리 (모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들, 속성은 모든 노드 n에 대해서 반드시 참이어야 한다.)

균형 vs 비균형

완전 이진 트리

트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리

 

전 이진 트리

모든 노드의 자식이 없거나 정확히 두 개 있는 경우

 

포화 이진 트리

전 이진 트리이면서 완전 이진 트리인 경우. 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 단계에서 노드의 개수가 최대가 되어야 한다.

이진 트리 순회

// 중위 순회
void inOrderTraversal(TreeNode node)
{
    if (node != null)
    {
        inOrderTraversal(node.left);
        visit(node);
        inOrderTraversal(node.right);
    }
}
 
// 전위 순회
void preOrderTraversal(TreeNode node)
{
    if (node != null)
    {
        visit(node);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}
 
// 후위 순회
void postOrderTraversal(TreeNode node)
{
    if (node != null)
    {
        postOrderTraversal(node.left);
        postOrderTraversal(node.right);
        visit(node);
    }
}

 

이진 힙(최소힙과 최대힙)

최소힙은 트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있다는 점에서 완전 이진 트리이며, 각 노드의 원소가 자식들의 원소보다 작다는 특성이 있다. 따라서 루트는 전체에서 가장 작은 원소가 된다.

 

최대힙은 원소가 내림차순으로 정렬되어 있다는 점만 다를 뿐, 최소힙과 완전히 같다.

그래프

트리는 사이클이 없는 하나의 연결 그래프이다. 

 

그래프는 단순히 노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 것과 같다.

인접 리스트

그래프를 표현할 때 사용되는 가장 일반적인 방법. 모든 정점(혹은 노드)을 인접 리스트에 저장한다.

무방향 그래프에서 간선은 두 번 저장된다.

인접 행렬

NxN 불린 행렬(boolean matrix)로써 matrix[i][j] 가 true라면 i에서 j로의 간선이 있다는 뜻이다. (N : 노드의 갯수)

무방향 그래프를 인접 행렬로 표현한다면 이 행렬은 대칭행렬(symmetric matrix) 이 된다. 방향 그래프는 대칭행렬이 안 될 수도 있다.

그래프 탐색

깊이 우선 탐색(depth first search) : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법.

 

너비 우선 탐색(breadth first search) : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.