Algorithm

Merge Sort

기본 원리 우선 2개의 정렬된 배열이 있다고 가정해보자. 이 2개의 배열을 하나의 정렬된 배열로 만들고 싶다면, 두 배열의 첫번째 인덱스를 비교해가면서 더 작은 값을 빼내어 새로 만들 배열에 추가해주면 된다. Merge Sort는 배열을 쪼개는 과정부터 시작한다. 우선 각 배열의 길이가 2가 될 때까지 배열을 계속해서 둘로 나눈다. 다 쪼개졌으면 위에서 살펴본 방식대로 배열 안의 값들을 서로 비교하면서 작은 값을 먼저 삽입한다. 이렇게 각 배열의 길이가 2이고, 그 안에서 정렬된 배열들을 똑같은 방법으로 길이가 4이며, 그 안에서 정렬된 배열로 합쳐준다. 이런 식으로 다시 원본 배열의 전체 길이가 될 때까지 합치면서 돌아온다. 이렇듯 함수가 호출될 때마다 절반씩 잘라서 재귀적으로 함수를 호출하고, 작은 ..

Quick Sort

What is Quick Sort? 배열 안에서 기준점(pivot)을 잡고, 해당 기준점보다 작으면 왼쪽으로, 크면 오른쪽으로 옮긴다. 이 때, 기준점 양 옆으로 배열이 partition 2개로 나뉘는데, 왼쪽 따로 정렬하고 오른쪽 따로 정렬하는 작업을 재귀적으로 반복하면 완전히 정렬된 배열을 얻을 수 있게 된다. Quick Sort의 시간 복잡도 평균적으로 O(n log n)이라고 볼 수 있다. 최악의 경우 O(n²) 복잡도가 나오기는 하지만 보통의 경우에는 O(n log n)의 복잡도를 가진다고 설명한다. 그렇다면 왜 O(n log n)의 복잡도를 가진다고 보는지 그 이유를 살펴보자. 일단 partition을 나누는 횟수는 n번이다. 파티션의 데이터가 낱개가 될 때까지 나누게 되는 것이다. 그런데 한..

Binary Tree의 3가지 순회방법 구현하기

Binary Tree Traversal Binary Tree를 횡단하면서 Tree의 모든 데이터를 가져오는 방법에는 3가지 방법이 있다. Inorder (Left, Root, Right) Preorder (Root, Left, Right) Postorder (Left, Right, Root) Inorder 우선 왼쪽 자식을 따라서 끝까지 탐색한다. 왼쪽 끝 leaf에 도달하면 해당 leaf를 출력하고, 해당 leaf의 Root인 부모 Node를 출력한다. 그 다음에는 해당 부모 Node의 오른쪽을 탐색하기 시작하며, 끝에 도달하면 똑같이 출력 이후에 Root로 돌아온다. Preorder 자기 자신을 먼저 출력하고 그 다음에 왼쪽 - 오른쪽 순서로 탐색을 하는데, 역시나 자기 자신을 먼저 출력하고 왼쪽과 ..

Graph 기본 개념

Tree와 Graph 사실 Tree는 Graph의 한 형태이다. Tree는 root가 있고, 단방향이며, cycle이 있을 수 없는, 아래로만 흐르는 방향 그래프이다. Graph의 방향 Graph는 방향이 있을 수도 있고, 없을 수도 있다. 있으면 Direted Graph가 되고, 없으면 Undirected Graph가 된다. Graph 안에서의 Circle 하나 이상의 Circle이 있으면 Cyclic Graph라고 하며, 단 한개의 Cycle도 없다면 Acyclic Graph라고 한다. Graph를 표현하는 방법 Adjacency Matrix Adjacency List Adjacency Matrix는 2차원 배열에 표현하는 방법이고, Adjacency List는 배열에 Node들을 나열하고 관계를 L..

Tree의 종류

What is Tree Array, LinkedList, Stack, Queue는 일직선 데이터 구조이다. 반면에 Tree는 부모 - 자식 관계를 갖는 데이터 구조이다. 따라서 Tree에는 계층과 그룹이 있다. 그리고 Tree의 맨 끝, 더이상 자식이 없는 Node를 leaf라고 부른다. Binary Tree (이진 트리) Child Node가 최대 2개까지만 붙는 Tree가 Binary Tree이다. Child Node가 3개씩 붙게 되면 Ternary Tree라고 부른다. 우리가 특히 관심을 갖고 공부하기 되는 Tree는 Binary Tree이다. Binary Search Tree (이진 검색 트리) Binary Tree는 Child Node가 최대 2개라는 조건 외에 다른 조건은 필요 없다. 하지만..

Java에서 Queue 직접 구현해보기

Queue의 4가지 기능 add() : 맨 마지막에 데이터를 삽입 remove() : 맨 앞에서 데이터를 꺼냄 peek() : 맨 앞 데이터를 확인 isEmpty() : 큐에 데이터가 있는지 없는지 확인 코드로 구현해보기 import java.util.NoSuchElementException; class Queue { class Node { private T data; private Node next; public Node(T data) { this.data = data; } } private Node first; private Node last; public void add(T item) { Node t = new Node(item); if (last != null) { last.next = t; } ..

Java에서 Stack 직접 구현해보기

Stack의 4가지 기능 pop() : 맨 마지막에 넣은 데이터를 가져오면서 지움 push() : 새로운 데이터를 맨 위에 쌓아올림 peek() : 맨 마지막 데이터를 확인 isEmpty() : 스택에 데이터가 있는지 없는지 확인 코드로 구현해보기 import java.util.EmptyStackException; class Stack { class Node { private T data; private Node next; public Node(T data) { this.data = data; } } private Node top; public T pop() { if (top == null) { throw new EmptyStackException(); } T itme = top.data; top = t..

Big-O 표기법

What is Big-O? Algorithm의 성능을 수학적으로 표현해주는 표기법 Algorithm의 시간과 공간 복잡도를 표현할 수 있게 해줌 Algorithm의 실제 러닝 타임을 표기해주기 보다는 데이터나 사용자의 증가에 따른 Algorithm의 성능을 예측하는 것이 목표 O(1) constant time F (int[] n) { return (n[0] == 0) ? true : false; } 입력 데이터의 크기에 상관 없이 언제나 일정한 시간이 걸리는 Algorithm O(n) linear time F (int[] n) { for i = 0 to n.length print i; } 입력 데이터의 크기에 비례해서 처리 시간이 걸리는 Algorithm O(n²) quadratic time F (int..