Overview

이 장에서는 여러 Data Structure의 개념과 자바에서는 실제로 어떻게 구현되어 있는지 알아보도록 한다.

Linear Data Structure

Array

논리적 저장순서와 물리적 저장순서가 일치한다. 즉 메모리에서 연속적으로 데이터가 기록되는 자료구조이다. 이 특성 덕에, 특정 아이템을 인덱스를 알면 O(1)안에 접근이 가능하지만(random access), 아이템 삭제나 추가를 진행할 때, 연속성을 유지해야 하기 때문에 최대 O(n)의 시간복잡도가 발생한다.

보통 자바에서는 []를 통해서 Array를 생성하며, 아래와 같이 스택 영역에 Array의 레퍼런스를 저장하고 힙 영역의 메모리에 연속적으로 데이터를 할당하고 있다. 이 때, 메모리의 크기는 고정적이다. 또한 Array에서는 같은 클래스의 인스턴스를 가지도록 하며, 관련이 없는 클래스가 할당될 경우 IllegalArgumentException이 발생한다.

ArrayList in Java

위와 같이 []를 이용한 일반적인 Array는 선언과 동시에 배열의 크기가 정해진다. 따라서 만약 초기 선언된 크기보다 더 많은 데이터를 넣고 싶다면 문제가 발생한다. 이를 해결하기 위해서 Java에서는 배열의 크기를 변경할 수 있는 ArrayList 클래스가 존재한다.

ArrayList는 Array를 사용하며 만약 사용하던 Array의 capacity(용량)가 부족해지면 적절한 크기로 늘린 새로운 Array를 만들고 기존의 데이터를 복사한다. 다른 블로그에서는 대부분 2배로 Array를 늘린다고 되어 있지만, 실제로는 아래와 같이 ArraysSupport.newLength을 사용하여 최적화된 크기로 늘린다.

• Tip : Vector vs ArrayList결론부터 말하자면 Vector는 synchronized되어 있으며, ArrayList는 asynchronized되어 있다. 즉, Vector는 하나의 스레드만 접근이 가능하며 ArrayList는 여러 스레드가 동시에 접근이 가능하다. synchronized되어 있다는 것은 이를 위한 코드가 추가적으로 작성되어 있다는 뜻이기에, 일반적으로 ArrayList가 더 빠른 성능을 가지고 있다. 따라서 Thread-safe한 환경에서는 ArrayList를 사용하고 그렇지 않은 환경에서는 Vector나 Collection.synchronizedList를 사용하는 것이 옳다.
• 자바에서 Vector클래스를 들어본적이 있는가? 아마 대부분 들어본적이 없을 것이다. Vector는 자바의 초창기에 지금의 ArrayList기능을 위한 레거시 클래스이다. 그러나 현재는 List 인터페이스를 구현하기 위해서 Collection 프레임워크에 맞게 재구성되어있기 때문에 사용할 수 있다. 그렇다면 Vector 와 ArrayList의 차이점은 무엇일까?

Linked List

Linked List의 경우 Array와 달리 메모리에 연속적으로 저장되지 않으며, 각 아이템은 자기 다음의 아이템의 위치만을 가지고 있는 구조이다. 이를 통해서 메모리에 연속적으로 저장하지 않아도 리스트의 요구사항을 만족할 수 있어 삽입과 삭제에 O(1)의 시간복잡도가 요구된다. 그러나 원하는 부분에서 삽입과 삭제를 진행하기 위한 search 과정에서 최악의 경우 O(n)의 시간복잡도가 발생할 수 있기 때문에, 전체적인 시간복잡도는 O(n)이 될 수 있다.

Doubly-Linked List in Java

Doubly-linked list implementation of the Listand Dequeinterfaces. Implements all optional list operations, and permits all elements (including null). All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index. [2]

자바에서 어떻게 구현되어 있는지 살펴보자. 자바에서 사용하는 LinkeList는 기본적으로 Doubly-LinkeList이다. 이는 하나의 원소가 자기 다음의 원소 주소만 저장하는 것이 아니라 반대로 자기 이전의 주소 또한 저장하는 것이다. 이렇게 사용하는 이유는 효율성을 위해서이다. 예를 들어, 찾고자 하는 원소의 인덱스가 리스트의 마지막에 가깝다면, 처음에 가까이 있는 원소보다 시간이 많이 소요될 것이다. 자바에서는 이런 불균형을 방지하기 위해서 마지막에서부터 원소를 탐색을 시작할 수 있도록 하기 위해서 Doubly-Linked List를 사용하고 있다.

Stack

선형 자료구조의 일종으로 마지막으로 삽입된 원소가 처음 나오는 구조(LIFO, Last In First Out)를 가지고 있다. 대표적으로 사용자가 어떤 액션을 취하고 되돌아가기 위해 ctrl+z를 누르는데 이 때, 사용자의 액션이 저장되는 자료구조가 스택이다. 또한, 프로그램에서 스택은 함수의 호출 구조를 저장하는데 사용된다. 예를 들어, 사용자의 정보를 다운로드 하는 함수가 아래와 같이 수행된다고 하자. 그럼 getUserInfo → parse → download 순으로 메서드가 호출되고 이 순서대로 스택에 호출 정보가 저장된다. 그리고 메서드 처리가 완료될때마다, download → parse → getUserInfo 순으로 값이 반환된다. 이렇듯, 스택은 마지막으로 처리한 과정부터 역으로 진행이 필요한 프로세스에 사용되는 기본적인 자료구조이다.

function getUserInfo(){
	return parse(donwload())
}

Stack in Java

자바에서는 Stack 클래스를 이용해서 stack 자료구조를 구현하고 있다. 그 특성은 위에서 말한 Stack의 특성과 동일하며 재미있는 점은 아래와 같이 Vector를 super 클래스로 삼고 있다. Vector는 synchronized ArrayList라고 생각하면 된다(자세한 내용은 위의 “Tip : Vector vs ArrayList”를 참고). 따라서 Stack 또한 하나의 스레드만 접근가능한 synchronized가 적용되어 있어 Thread-safe하다.

//Stack's super class
java.lang.Object
	java.util.AbstractCollection<E>
		java.util.AbstractList<E>
			java.util.Vector<E>
				java.util.Stack<E>

Queue

Stack은 LIFO 구조라고 하였다. 그렇다면 반대로 처음 삽입된 원소가 마지막으로 나오는 (FIFO, First In First Out)구조도 필요하지 않을까? 그럴 때 사용되는 것이 Queue이다. 큐는 CS에서 사용하는 세마포어, 버퍼링 등 다양한 프로세스를 구현하기 위해서 사용된다.

Queue in Java

Stack과 달리 자바에서는 Queue를 위한 클래스가 따로 존재하지 않는다. 대신, LinkedList, PrioirtyQueue 등 Queue 인터페이스가 구현된 다른 클래스를 적절히 선택하는 것을 권장하고 있다.

Queue<String> queue= new LinkedList<String>()
Queue<String> queue= new PrioirtyQueue<String>()

예를 들어, 일반적인 순서를 가지는 큐를 구현하고 싶으면 LinkedList를 구현하면 되고, 데이터를 삽입할 때마다 정렬되는 큐를 만들고 싶다면 PrioirtyQueue를 사용하면 된다. 이외 에도, AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, 등등, 다양한 클래스를 자신의 적절한 환경에 사용할 수 있다.

Tree

지금까지 다룬, Array,List, Stack, Queue는 데이터를 순서대로 표현할 수 있는 선형 자료구조다. 이와 달리 Tree는 나뭇가지가 뻗어 나가듯 데이터가 나뉘어지는 비선형 구조를 가지고 있다.

Binary Tree

이진 트리는 각각의 노드가 최대 2개의 자식노드를 가질 수 있는 재귀적인 자료구조이다. 이진트리는 깊이에 따라 레벨이 정해져 있다. 루트노드가 레벨 0이며 깊이가 내려갈 수록 레벨이 증가한다. 또한 최고레벨을 가르켜 해당 트리의 height라고 한다.

Perfect Binary Tree(포화 이진 트리)

모든 레벨이 채워져있는 이진 트리

Complete Binary Tree(완전 이진 트리)

트리의 노드가 위에서 아래로, 왼쪽에서 오른쪽으로 차곡차곡 채워져있는 트리이다. 여러 알고리즘에서 자주 사용되는 트리 구조

Full Binary Tree(정 이진 트리)

모든 노드가 0 또는 2개의 자식 노드만을 가지고 있는 트리이다.

Binary Tree in Java(Array vs Recursive Class)

자바에서는 이진 트리를 위한 특정한 클래스가 존재하지 않는다. 대신, 이진트리는 Array를 이용해서 간단하게 구현할 수 있다. 루트노드는 1번째 노드라고 규정하고 노드의 내용을 1번째 인덱스에 저장 했을 때, n번째 노드의 왼쪽 자식노드는 n2 인덱스에 저장하며 오른쪽 자신 노드는 n2+1 인덱스에 저장하도록 하면 Array에 이진트리의 정보를 저장할 수 있다.

아래와 같이 Array 이외에도 노드가 노드를 참조하는 재귀적인 클래스를 생성하여 이진트리를 구현할 수 있다.

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }
}

이제 Array로 작성한 이진 트리와 클래스를 사용한 이진트리의 장단점을 구별해보자. 첫 번째로, 노드의 데이터를 가져올 때 Array는 인덱스를 통해서 상수시간내에 접근이 가능하지만, 클래스에서는 O(logn)의 검색시간이 발생한다. 따라서 삽입, 삭제, 업데이트 시에도 클래스로 구현한 이진트리에서 더 많은 시간이 소요된다. 두 번째로, 메모리 관점에서 바라볼때 클래스는 내용 이외에 자식노드의 인스턴스까지 참조해야 하기 때문에, Array에 비해서 많은 메모리가 필요하다. 그러나, 완전 이진트리가 아닌 이진트리의 경우 Array는 저장해야할 내용보다 많은 메모리가 필요하지만 클래스는 저장해야만 하는 노드를 구현하기 때문에 메모리를 절감할 수 있다.

Binary Search Tree

이진 트리를 사용해서 데이터를 검색하기 효율적인 자료구조를 만들 수 있다. 아래와 같은 규칙을 정렬된 데이터를 트리 형식으로 구현해보자.

• 규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
• 규칙 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
• 규칙 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
• 규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

그리고 루트노드 부터 임의의 저장된 숫자를 검색한다고 했을 때, 마주치는 노드를 기준으로 왼쪽 자식노드로 검색할 지, 오른쪽 자식노드로 검색할 지 비교를 통해 결정할 수 있다. 트리가 완전 이진트리로 균형 잡혀 생성된 경우, 검색을 할 때마다, 비교해야 할 데이터가 절반씩 줄어들기 때문에 O(logN)=O(height)의 시간복잡도가 발생하여 큰 데이터 일 수록 매우 빠르게 검색할 수 있다.

그러나 만약 이진 탐색 트리가 왼쪽이나 오른쪽을 치우쳐 있을 경우, Worst Case 가 발생하며, 검색하는데 O(n)의 시간복잡도가 필요하다.

Red Black Tree

앞서 말했듯, 위와 같은 Binary Tree는 Worst Case의 경우 O(n)의 시간복잡도가 발생한다. 이런 경우를 대비하기 위해서 자료구조에는 Binary Tree가 균형잡인 트리로 유지하기 위한 Red Balck Tree가 존재한다. (구현하기 위한 알고리즘은 복잡하므로 생략한다.)

Red Balck Tree in Java

대표적으로 TreeMap이 Red Black Tree 구조를 사용하여 구현되어 있다. Map에서는 키의 유무 또는 위치를 검색하는게 중요한다. 이 때, 키를 저장하는 자료구조가 Red Black Tree이다.

Binary Heap

Complete Binary Tree 구조이며, 부모 노드의 값이 자식노드보다 항상 크다면 Max Heap, 부모 노드의 값이 자식노드보다 항상 작다면 Min Heap이라고 부른다. 이 자료구조는 저장된 데이터에서 최댓값이나 최솟값을 검색할 때 항상 O(1)의 시간복잡도를 보장하기에 최대,최소를 자주 찾는 프로세스에서 사용된다. 최대값을 pop할 경우 다시 저장된 데이터중 최댓값이나 최솟값이 루트노드에 존재해야 하기 때문에, heapify(맨 마지막 노드를 루트 노드에 대체시킨 후, 자식 노드와 비교하면서 데이터의 자리를 재위치 시키는 과정)를 진행하기에 O(logn)의 시간복잡도가 발생한다.

Binary Heap in Java

Priority queue represented as a balanced binary heap: the two children of queue[n] are queue[2n+1] and queue[2(n+1)]. The priority queue is ordered by comparator, or by the elements' natural ordering, if comparator is null: For each node n in the heap and each descendant d of n, n <= d. The element with the lowest value is in queue[0], assuming the queue is nonempty.

자바에서는 Heap을 구현하기 위해서 PriorityQueue 클래스를 사용한다. PriorityQueue는 Array를 이용해서 Complete Binary Tree를 구현하고 있으며, null을 포함한 non-Comparable한 데이터의 추가를 금지하고 있다. 또한, 동기성이 보장되고 있지 않아 여러 사용자가 동시에 접근하는 것은 안전하지 않으므로 이 경우, thread-safety가 보장된 PriorityBlockingQueue를 권장하고 있다.

Hash Table

Array에 데이터를 저장할 때 단순히 순서대로 저장하는 것이 아니라, 저장할 값을 기준으로 인덱스를 결정하여 저장하는 자료구조를 뜻한다. 이 때, 저장할 값을 기준으로 인덱스를 생성하는 방법을 hash method 또는 hash functiond이라고 하며 생성된 인덱스를 hashcode라고 한다. hash function이 좋지 못할 경우 서로 다른 값에서 동일한 인덱스가 생성될 수 있는데, 이 경우 동일한 인덱스에 여러개의 데이터가 존재할 수 있다. 이를 collision이라고 칭한다. hash function이 어떻게 작성되느냐에 따라, collision의 정도가 결정되는데, 항상 collision이 발생하지 않는것이 꼭 좋은 자료구조는 아니다. 오히려 적절한 collision이 발생하는 것이 좋은 성능의 Hash Table을 만들 수 있다.

HashTable in Java

자바에서는 HashTable을 사용할 때 기본적으로 키값과 저장할 내용, 두 가지를 입력한다. 키로 삽입되는 인스턴스는 Null이 아니며 hashCode()메서드가 구현되어 있어야 한다(HashMap은 Null값도 허용한다). 자바 개발자들은 Hashtable은 최근에 Java Collection에 포함된 대부분의 클래스와 달리 thread-safety가 보장되기 때문에 single programming에서 사용하는 경우 오버헤드가 발생하므로 thread-safety가 필요없는 경우 HashMap을 사용하는 것을 권장하고 있다. 또한 Hashtable은 레거시 클래스에 가깝기 때문에, thread-safety하고 고도의 동시성을 구현하기 위해서는 [ConcurrentHashMap](<https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html>) 을 사용하는 것을 권장하고 있다.[5]

1. Entry

이제 본격적인 구조에 대해서 알아보자. 해쉬 테이블의 데이터는 아래처럼 Entry 메서드에 저장된다. Entry는 Hashtable의 이너 클래스로, 이론적으론 하나의 버킷을 의미한다. [6]

private transient Entry<?,?>[] table;

내부 구조를 보면 알겠지만 LinkedList와 비슷한 구조를 가지고있다. 여기서 알 수 있는 점은, 같은 hashCode() 결과를 가져, 하나의 Entry에 포함된 원소들의 경우 검색하는데 선형적 시간복잡도가 걸린다는 것이다.

/**
 * Hashtable bucket collision list entry
 */
private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;
....

2. Put

이번엔 새로운 데이터를 추가하는 코드를 살펴보자. 우선 윈소의 값이 null인지 확인하고, 기존의 테이블의 길이와 hashCode()를 통해서 인덱스를 결정한다. 그리고 인덱스에 해당하는 엔트리를 가져와 링크드리스트를 탐색하듯 반복문을 진행하고 같은 키를 가지는 경우 기존의 원소값을 업데이트 한다. 같은 키가 없다면 addEntry를 통해서 새로운 값을 추가한다.

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        @SuppressWarnings("unchecked")
        Entry<K,V> entry = (Entry<K,V>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                V old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addEntry(hash, key, value, index);
        return null;
    }

Hashtable에서는 loadFactor라는 값이 있는데 기존의 테이블을 얼마나 채우는 것을 허용하는지 결정하는 변수이다. 보통 메모리와 처리시간을 고려하여 0.75로 정해져 있다. threshold는 loadFactor값에 현재의 엔트리 용량을 곱한 결과로 지금 테이블 용량에서 최대로 채울수 있는 엔트리의 길이를 의미한다. 그래서 테이블에 새로운 값을 추가할 때, 테이블의 갯수가 threshold를 넘을 경우 rehash()메서드를 호출하여 테이블의 크기가 두 배인 변수를 만들어 기존의 값을 전부 복사한다. 여기서 배울 수 있는 점은, 만약 Hashtable의 크기를 처음에 결정할 수 있다면, rehash()메서드의 호출을 줄이기 위해서 처음부터 크기를 알맞게 할당해야 한다는 것이다. 그 다음 과정은 새로운 엔트리를 생성하여 값을 추가하는 것이다.

private void addEntry(int hash, K key, V value, int index) {
        Entry<?,?> tab[] = table;
        if (count >= threshold) {
            // Rehash the table if the threshold is exceeded
            rehash();

            tab = table;
            hash = key.hashCode();
            index = (hash & 0x7FFFFFFF) % tab.length;
        }

        // Creates the new entry.
        @SuppressWarnings("unchecked")
        Entry<K,V> e = (Entry<K,V>) tab[index];
        tab[index] = new Entry<>(hash, key, value, e);
        count++;
        modCount++;
    }

3. get

Hashtable에서 put을 이해했다면 get은 매우 간단하다. hashCode를 통해서 인덱스를 구한 후, 이에 해당하는 엔트리를 가져와 LinkedList를 검색하듯 get을 진행하고 만약 찾지 못했다면 null을 반환한다.

public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

HashMap vs Hashtable in Java

Java Docs를 포함한 대부분의 포스트에서는 HashMap과 Hashtable의 차이를 Thread-safety와 키, 원소의 Null 허용 여부에 두고 있다. 그러나 내부 구조에서는 매우 큰 차이가 존재하는데 바로 Resolve Conflict관점에서 Hashtable은 Seperate Chaining방식에서 Linked List만을 사용하지만 Tree와 Linked List를 공용으로 사용한다. Linked List는 탐색을 위해서 선형적 시간복잡도가 발생하는데 만약 하나의 버킷에 많은 양의 링크드 리스트가 존재한다면 탐색시간이 크게 늘어난다. 따라서 크기가 8이상의 버킷에 대해선 Red-Black-Tree방식으로 자료구조를 변경하여 탐색에 O(logN)의 시간복잡도를 제공하도록 한다.[7]

Graph

그래프는 정점(Vertex,Node)와 두 개의 정점을 잇는 간선(Edge)의 집합이다. Edge그래프는 Edge의 종류에 따라 Undirected Graph와 Directed graph로 나뉘게 되는데, Undirected의 경우 Edge에 방향이 없고, Directed의 경우 하나의 노드에서 다른 노드를 가르키는 방향성이 존재한다. 이 때, Undirected Graph에서 정점 간 연결된 Edge의 갯수를 Degree라고 하며 Directed Graph에서는 방향성에 따라 Outdegree, Indegree 두 가지로 나누어 갯수를 센다. 또한 만약 Edge에 가중치가 존재하는 경우 Weight Graph라고 칭한다.

그래프는 보통 이해관계를 표현할 때 주로 사용된다. 예를 들어 장소와 장소의 관계를 연결된 도로나 다리로 표현하거나 사람과 사람간의 채무 관계 등을 표시할 때 사용된다. 이런 이해관계를 그래프 자료구조로 저장함으로써 장소간 최단거리를 구하는 등의 알고리즘을 구현할 수 있다.

트리 또한 그래프의 종류 중 하나이며, 트리는 그래프와 달리 사이클이 생성되지 않는 특징을 가지고 있다.

Implementation

그래프를 구현하는 방법에는 크게 두 가지가 존재한다.

Adjacent Matrix

인접 매트릭스의 경우 정점의 갯수만큼의 행과 열을 가진 배열을 만들고 row,col을 정점의 번호로 가정했을 때, A와 B를 잇는 간선이 존재하는 경우 matirx[A][B]에 간선의 여부 및 가중치의 값을 기록하여 그래프를 구현하는 방법이다.

Adjacent List

인접 리스트의 경우, 정점의 갯수만큼 Array를 생성한 다음 각 원소에는 LinkedList를 구현하여 정점 A와 B가 이어져 있는 경우 matrix[A].push(B)를 통해서 간선의 유무, 방향성을 표시한다. 이 때 가중치 그래프인 경우 가르키는 정점과 함께 가중치 값을 삽입하기도 한다(matrix[A].push([B,W])).

Search

그래프는 비정형 데이터이므로 인덱스를 통한 순차적 검색을 지원하지 않는다. 대신, Recursive based Class Tree처럼 정점과의 관계인 간선을 하나씩 이어나가면서 데이터를 탐색하는 방법이 있다. 여기에는 크게 깊이를 우선으로 탐색하냐, 너비를 우선으로 탐색하냐에 탐색법이 나뉘게 된다.

1. DFS (Depth First Search)

DFS는 임의의 한 정점에서 다른 정점으로 나아가는 것을 반복하는 것이다. 예를 들자면, A 정점이 B,C와 연결되고 B 정점이 D,E와 연결된다면 A→B→D 순서로 연결된 간선 중 순서가 빠른 간선으로 계속 전진하는 것이다. 만약 더 이상 전진할 간선이 없다면 이전의 정점으로 돌아가 남아있는 간선으로 탐색을 다시 진행한다. 이 구조는 Stack을 이용한 미로찾기와 같은 구조인데, 역시 DFS에서는 Stack을 이용하여 이를 구현하다.

1. BFS(Breath First Search)

BFS는 너비 우선 탐색으로, 주위에 있는 간선을 먼저 탐색하는 것이다. 위와 같은 예를 들때, BFS로 탐색하면 A→B→C→D→E 순서로 탐색하게 된다. 주위에 있는 정점을 모두 탐색했을 때, 이 후 탐색한 순서대로 또 다시 해당 정점에서 주위 탐색을 진행한다. “먼저 탐색한 정점이 또 먼저 탐색을 시작”하므로 FIFO 형태의 자료구조가 필요하므로 BFS에서는 Queue를 사용한다.

Reference

1. https://docs.oracle.com/javase/7/docs/technotes/guides/collections/overview.html
2. https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html
3. https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html
4. https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
5. https://docs.oracle.com/javase/8/docs/api/java/util/Hashtable.html
6. https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/Hashtable.java
7. https://github.com/AdoptOpenJDK/openjdk-jdk11/blob/master/src/java.base/share/classes/java/util/HashMap.java

들어가며

Github은 Git Remote Repository로 사용하는데 아주 대중적인 웹사이트다. Github에는 프로젝트 관리를 위한 다양한 기능을 가지고 있어서 이번 포스트에는 이를 우리 프로젝트에서 활용한 방법에 대해서 간략하게 소개하겠다. 

1. 선택이유

지난 포스트에서도 말했듯, PM(Project Management)를 위한 툴은 여러가지가 있다. 그러나 용도에 따라 서로 분산된 툴을 사용해야 하고 이를 연동하는 과정이 가벼운 프로젝트를 시작하는 사람들에게는 오히려 짐이 된다. 그런데 Github Repository에는 Issue, Milestone, Actions, Project, Wiki 등 다양한 프로젝트 관리 도구가 한 곳에 존재하기 때문에 따로 설정할 필요가 없어 편의성이 좋다. 물론, 더 복잡하고 큰 프로젝트를 관리하기 위해서는 부족한 기능이 몇 가지 있다. 하지만, 5명 정도의 팀원이 운영하기에는 충분한 기능을 제공하였기에 Github의 PM 기능을 선택하게 되었다.

2. 새로운 프로젝트 생성하기

새로운 Repository를 만들고 Github Project 기능에 들어간 후, 새로운 프로젝트 생성 버튼을 클릭하면 아래와 같은 창이 나온다. 

여기서 프로젝트에 관한 설명을 기록할 수 있고 Project Template를 정할 수 있는데 이 부분이 중요하다.

프로젝트는 기본적으로 칸반 형식을 제공하는데, Automated kanban을 사용하게 되면 프로젝트에 포함된 이슈를 닫거나, PR을 merge하게 되는 경우 자동으로 칸반의 상태를 변경한다. 예를 들어서, "버그 수정하기" 이슈를 프로젝트에서 TODO 상태로 정한 후, 버그 수정이 완료되어 이슈를 Close하면 자동으로 Done 상태로 이동 된다. 이러한 기능덕에 우리 프로젝트에서는 Automated kanban을 선택하여 지금까지 관리하고 있다.

프로젝트를 생성할 때는 Description에 해야할 내용을 간략하게 작성하여, 이 프로젝트에서 해야할 일을 정의한다. 아래의 경우, 3주차 스프린트에서 프론트엔드와 벡엔드에서 진행해야할 내용을 간단하게 서술한 예시이다.

프로젝트를 생성하고 들어가면, 처음에는 아래와 같이 Todo, In progress, Done 세 가지 형식의 Colum이 자동으로 생성될 것이다. 여기서 팀원들이 어떤 이슈를 해결중인지 파악할 수 있어 프로젝트 진행과정을 공유하기에 용이하다. 간혹, 이슈 상태를 업데이트 하지 않은 경우가 있는데, 이러면 이슈가 해결되었는지 파악할 수 없어 개발과정이 지체되는 경우가 있었으니 주의해야 한다.

여기에서 바로 이슈를 생성할 수도 있고, 이슈에서 연관된 프로젝트를 설정할 수도 있다. 아래 사진에서 우측 하단을 보면 프로젝트를 설정할 수 있는 것을 볼 수 있다.

또한 Pull Request에서 프로젝트와 관련있는 이슈를 연결했을 때, 프로젝트 보드에서 이슈와 Pull Request를 자동으로 묶어 보여주기 때문에 PR의 상태까지 한번에 확인 할 수 있다.

마치며

이 글을 쓰면서 이슈와 PR 활용법에 대해서도 적어야겠다는 생각이 들어, 조만간 작성할 예정이다. 왜냐하면 커밋 코드를 리뷰하거나, 링크를 통해서 간단하게 참조하는 법 등, 유용한 기능들이 아직 많이 남아있기 때문이다. 만약 본인이 팀원들과 새로운 프로젝트를 시작하는데 Jira, Confluence같은 툴을 사용하는데 어려움을 느낀다면 Github Project를 사용해보는 것을 적극적으로 권장한다.

들어가며

지난 포스트에는 개발방법론과 이를 실현하기 위한 툴들에 대한 내용을 작성하였다. 이번에는 새로운 프로젝트에서 문제를 정의한 과정에 대해서 알아보도록 하겠다.

1. 시작

교수님께서 소개해주신 스타트업 대표님과 개발팀장님께 자문을 받았을 때 가장 인상깊었던 말씀은 클라이언트, 팀원들 간의 생각 차이를 줄이는게 가장 중요하다는 것이었다. 자세히 말하면 같은 내용을 얘기하고 있어도 미묘하게 비즈니스 로직이나 유저 스토리에 대한 이해에 차이가 발생할수 있으며 이를 바로잡지 않으면 나중에 개발을 진행할 때 문제 정의로 회귀하여 다시 개발을 진행할 수도 있는 나비효과가 발생한다는 것이었다. 따라서 이번 프로젝트에서는 생각 차이를 줄이는데 집중하여 아래와 같이 3가지 문제정의 방법을 사용하고 검증했다.

2. User Story

가장 처음에는 영상의학과 교수님들과 대학원생 분들과의 미팅에서 구현되었으면 하는 요구사항을 정리하고자 User Story를 아래와 같이 작성했다.

각자의 User Story에는 개발 시 구현 방안을 간단하게 노트로 작성했고 구체적인 내용을 테스크로 정의하고 내부 페이지에 작성하였다.

3. 디자인

이 후에는 User Story를 바탕으로 디자인 초안을 작성했다. 이를 작성할 때는 Figma를 선택했는데, 그 이유는 Kakao oven, Sketch 등과 달리 Google에서 사용하는 다양한 Material UI Component를 무료로 이용할 수 있었기 때문이다. 그리고 Material UI Component를 사용한 이유는 향후 프론트 프레임워크를 React를 사용할 예정이었는데 React MUI 라이브러리에 이미 Material UI를 준수하는 Component들이 만들어져 있어 디자인보다 로직에 집중 할 수 있었기 때문이다. (실제로 1.0.0 버전의 프론트 코드에는 CSS와 관련된 코드가 거의 작성하지 않아 로직에 집중된 코드를 작성할 수 있었다.)

또한 디자인을 통해서 다시 클라이언트와 소통할 때, 잘못 이해한 User Story를 바로잡을 수 있었고 개발 방향을 다시 점검 할 수 있었다.

4. 비즈니스 로직

본인은 이 부분이 문제정의에서 가장 중요한 부분이라고 생각한다. 왜냐하면 개발 코드를 작성하는데 직접적으로 연관이 있기 때문이다. 유즈케이스 다이어그램과 비슷하게 비즈니스 로직을 UML로 구성하였는데 이 부분에서 효율적인 개발을 위한 토론이 가능했고 또 역할 할당이나 협업 방식등을 정리하기에도 수월했다. 그리고 디자인에서도 점검한 유저 스토리에 대한 논리적인 오류를 발견하여 개발전 빠른 조치까지 가능했다. (나중에 개발을 할 때, 이 부분은 무슨일이 있어도 작성해야겠다고 다짐했다.) 또한 한눈에 프로그램의 동작과정을 파악 할 수 있었기 때문에 개발 팀원들간의 생각 차이를 줄이는데도 한몫했다.

UML형태로 작성한 비즈니스 로직의 또 다른 장점은 확장성이다. 애자일 형식으로 개발할 때는 스프린트 형태로 주마다 새로운 기능을 추가하는 형태로 개발했는데, 이 때 UML 컴포넌트를 기존의 비즈니스 로직에 추가하여 쉽게 확장 내용을 기술 할 수 있었으며 다시 논리적인 오류를 검증하여 기존 기능과의 병합을 안정적으로 진행할 수 있었다.

5. 후기

유저 스토리, 디자인 그리고 비즈니스로직을 작성하면서 클라이언트의 요구를 점검하는 과정들을 통해 실제 프로젝트를 개발하는데 오류를 줄이고 개발방향을 확고히 함으로써 코드 재작성이나 수정 과정을 대폭 줄이는 효과를 얻을 수 있었다. 그러나 이런 과정도 완벽하지는 못하다. 중간까지의 개발과정에서 클라이언트의 요청이 아예 변경될 수도 있기 때문이다. 실제로 그런 경우가 있었고 이미 작성한 기능을 삭제하거나 수정해야 했다. 앞으로는 이런 상황에도 대비하기 위한 문제정의 방법을 계속 공부하거나 개발해야 할 것 같다. 

1. 들어가며

최근 들어서 연구실에서 새로운 프로젝트를 시작하여 블로그 글을 작성하는게 뜸해졌다.  생각한 기능을 구현하고자 바쁘게 움직이면서 무의식적으로 글을 작성하는 과정을 미뤄왔던 것 같다. 프로젝트가 어느정도 기능이 구현되어 할 일이 줄어들어 지금까지 있었던 여러 고난과 극복과정을 앓음다운 글로 작성해보면서 그 동안의 팀 리더로서의 경험을 정리하고자 한다. 아직 많이 미숙하지만 이 글이 새로운 프로젝트를 시작하려는 모든 이에게 도움이 되었으면 좋겠다. 

2. 새로운 프로젝트

새로운 프로젝트의 이름은 DSMP(Dicom Service Mangement Project)로 Dicom이라는 의료용 디지털 영상 데이터를 관리한다는 의미를 가지고 있다. 의료영상을 베이스로 머신러닝을 연구하는 연구실이다 보니 의료 영상을 관리하는 작업이 필요했다. 이 과정에서 환자 개인정보를 지우는 익명화 작업, 서로 다른 병원에서 얻은 Dicom의 PatientID가 중복되는 문제 식별 및 수정 등의 여러 작업과 문제가 있었다. 반복적인 작업과 문제를 해결하기 위해서 시스템이 필요하게 되었는데 이를 위해 개발하기로 한 것이 DSMP이다.

3. 개발 방법론

3.1 실패

지금까지 진행했던 프로젝트는 워터폴 방식으로 진행했었다. 이 방법은 공모전이나 단기 프로젝트 같은 방식에는 별로 문제가 발생하지 않았었지만, 실제로 고객 요구사항에 맞춰 개발할 때는 엄청난 독이 되었었다. 예를 들어, 스타트업 외주를 담당하게 된 적이 있었는데, 매 주 회의를 할 때마다 저번주에 정한 요구사항이 변경되는 경우가 다반사였다. 그러다 보니 개발을 시작하려고 하면 다시 요구사항 정의로 돌아가기를 반복하기 일수였기에 굉장히 스트레스를 많이 받은 적이 있었다. 

3.2 도전

따라서 이번 프로젝트 또한 그런 상황을 방지하고자 애자일 개발 방법론을 공부하고 선택했다. 국내, 국외의 여러 포스트들을 검색하고 읽으며 학교 도서관에서 PM에 도움이 될만한 책들을 여러 권 읽어가며 실패하지 않는 개발 방법론을 실천하겠다고 다짐했다. 애자일에 대해서 알고 싶은 사람들에겐 로버트.C.마틴의 클린 애자일을 추천한다. 장 수는 별로 없는 것에 반해 굉장히 인상 깊게 읽었었다. 또한 이 과정에서 교수님이 스타트업 대표님과 개발 팀장님을 소개시켜주셨는데 굉장히 현실적인 조언들을 많이 해주셔서 배운점이 많았다.

3.3 구현

공부를 통해서 스프린트, 에픽, 테스크 등 개념에 대해서 공부하고 PM과 Wiki를 구축하기 위한 툴을 선택했는데 맨 처음에는 Jira와 Confluence를 선택했다. 그러나 결국 Github Project와 Notion으로 대체 했는데 그 이유는 아래와 같다.

1. 편의성 vs 기능성

Jira의 경우 Confluence와 Github Repository와의 연결 기능을 제공하고 있고 로드맵이나 애자일 보드 등 유용한 기능들이 많아 잘 사용한다면 개발을 빠르고 유연하게 진행할 수 있을 것 같았다.

그러나 처음 팀원들에게 이를 알려주었을 때, 기능을 사용하는게 굉장히 복잡하다는 피드백을 받았다. 나는 처음 사용하기에 그럴 수 있다고 생각했지만, 다시 곰곰히 생각해보니 5명 단위의 프로젝트였기 때문에 사실 복잡한 기능들을 모두 사용할 필요가 없다고 느꼇다. 따라서 Issue Tracking, Automated Kanban 등 기본적인 기능을 제공하며 편의성이 Jira에 비해서 높은 Github Project를 사용하게 되었다.

2. 불필요한 Description

개발을 진행하면서 결국 Github Issue를 사용했는데, 이슈에도 Description을 작성하고 이와 관련된 Jira 테스크에도 같은 Descriptiondn을 작성하는 경우가 다반사였다. 처음에는 Jira 테스크에 내용을 기술하고 링크를 Github Issue에 추가했으나 뭔가 잘못된것 같은 느낌이었다. 결국 과감히 Jira 사용을 포기함으로서 Desciption을 한 곳에만 집중하여 기술할 수 있어 오기입을 줄이고 편의성을 높일 수 있었다.

3. Commit Tracking

Github에서는 커밋을 작성할 때, 이슈 태그를 기술하면 이슈에 해당 커밋 내용이 자동으로 추가되고 만약 또 다른 커밋을 언급했다면 자동으로 링크가 형성되는데 이 기능이 팀원과 소통하는데 굉장히 도움이 많이 되었다. 물론 Jira에도 이와 비슷한 기능이 있지만, 이를 설정하고 이용하는데 Github에 비해서 번거롭기 때문에 Github에서 사용하는것 이 도움이 많이 되었다. 

3.4 후기

내가 느낀 애자일을 한 단어로 말하자면 "분할 정복"이라고 생각한다. 작은 계획이 모여 결과를 만들어 내는 과정이 알고리즘의 분할 정복과 비슷한 느낌이었기 때문이다(엄밀히 말하면 다르지만). 사실 아직도 애자일을 제대로 알고 있는지는 모르겠다. 그러나 워터폴 방식에 비해서 확실히 좋았던 점이 많았던 것 같고 새로운 개발방법론을 적용하면서 많을 공부가 되었다. 지금 느끼는 거지만 모듈화와 함수형 프로그래밍 방식을 적용했다면 더욱 효율적이지 않았을까 생각이 자주 든다(이와 관련된 포스트는 따로 작성예정). 또한 이와 관련된 툴은 생각보다 엄청 많으며 자신의 프로젝트에 어떤 것이 적합한지 판단하는 능력이 중요하다고 생각했다. 무턱대고 기능이 더 많고 좋아보이는 툴이 자신의 프로젝트에 비해 오버 스펙인 경우가 있을 수 있기 때문이다. 그러나 프로젝트를 진행하면서 복잡성이 증가하고 이에 따라 새로운 기능이 필요하다면 열린 마음으로 새로운 툴을 선택할 수 있어야 한다고 생각한다.