Algorithm

Heap Sort

What is Heap? 최대값이나 최소값을 찾아내는 연산을 빠르게 찾아내기 위해 고안된, 완전이진트리 를 기본으로 한 자료구조이다. 완전이진트리는 노드의 맨 마지막 리프 부분을 제외하고는 모든 level이 완전하게 채워져 있으며, 가능하면 왼쪽부터 채워진 구조이다. 그리고 Heap에는 Min-Heap과 Max-Heap이 있다. Min-Heap은 부모 노드에 자신보다 작은 값을 둬서 트리의 루트에는 가장 작은 값이 오게 한다. 반대로 Max-Heap은 부모 노드에 자신보다 큰 값을 둬서 트리의 루트에는 가장 큰 값이 오게 한다. Min-Heap에 대해서 알면 Max-Heap의 구현도 간단해지니 Min-Heap을 한 번 살펴보자. Min-Heap에 노드 삽입하기 우선 완전이진트리의 맨 끝에 추가한다. 추가..

Insertion Sort

Insertion Sort 개념 마치 손에서 카드 놀이를 하는 듯한 간단한 정렬 Algorithm이다. Insertion Sort에서 배열은 정렬된 부분과 정렬되지 않은 부분으로 나누어서 본다. 정렬되지 않은 부분에서 값을 하나씩 꺼내와서, 정렬된 부분에서 해당 값이 있을 수 있는 올바른 위치에 배치한다. 배열의 길이가 n인 배열을 오름차순으로 정렬하기 위한 세부적인 작동은 다음과 같다. arr[1]부터 arr[n]까지 반복 꺼내온 값(key)과 정렬된 부분 배열의 값들을 뒤쪽부터 차례대로 비교 key 값이 비교 대상보다 작은 경우, 정렬된 부분에서의 보다 앞의 값들과 계속해서 비교 Java 구현 class InsertionSort { void sort(int arr[]) { int n = arr.len..

Selection Sort

Selection Sort 개념 배열을 돌면서 가장 작은 값을 찾아내면서 맨 앞으로 옮기는 정렬 방식이다. 초기의 가장 작은 값은 시작값으로 지정하고, 배열을 loop하면서 보다 작은 값이 있으면 가장 작은 값으로 지정한다. 그리고 찾아낸 가장 작은 값을 배열의 맨 앞 요소와 교체해준다. 이런 식으로 배열의 길이만큼 반복하며 정렬해준다. 가장 작은 값을 찾아내기 위한 배열 내 loop를 다시 배열의 길이만큼 찾아내야 하기 때문에 O(n²) 의 시간복잡도를 가진다. 한 번 배열을 돌 때마다 정렬해야 하는 요소도 하나씩 줄어들지만, 그래도 square의 절반의 면적이 나오기 때문에 O(n²) 시간복잡도를 가진다고 말한다. Java로 구현하기 public class Test { public static voi..

Bubble Sort

Bubble Sort 개념 앞에서부터 2개씩, 인접한 요소들끼리 비교해서 작은 값을 앞으로, 큰 값을 뒤로 배치한다. (맨 뒤에서부터 시작하는 것도 가능하다.) 이 작업을 배열의 끝까지 도달하면서 정렬하는 방법이다. 그렇게 한번 배열의 끝까지 도달하는 과정을 거쳤다면 해당 배열의 맨 마지막 요소는 해당 배열에서 가장 큰 값이 된다. 한번 loop를 돌 때마다 끝 쪽에 요소 하나씩은 정해지니, 하나씩 비교하는 loop 자체를 배열의 길이만큼 돌려야 한다. 배열 내 요소의 갯수만큼 반복하는 작업을 다시 배열 내 요소의 갯수만큼 순회하게 되니 이 작업은 O(n²) 의 시간복잡도를 가진다. 물론 인접 요소끼리 비교하는 loop를 한번 돌 때마다 비교해야 하는 요소가 하나씩 빠지기는 하지만, 결국 square에서..

Hash Table에 대해 알아보고 Java로 구현해보기

Hash Table의 간단한 활용 사례 만약 어떤 사람이 유튜브 영상을 불법 복제하여 자기 계정으로 업로드를 시도하게 되면, 유튜브는 '중복되는 동영상'이라며 거절하게 된다. 전 세계 유튜브 동영상이 얼마나 많은데 이런 작업이 가능한걸까? 바로 Hash Table이 이와 같은 문제를 해결해주는 것이다. Hash Table의 작동 원리 F(key) → Hash Code → Index → Value 우선 검색하고자 하는 key 값을 입력받아서, 해쉬 함수를 돌려 Hash Code를 얻어낸다. 이 Hash Code를 배열의 Index로 환산해서 데이터에 접근하는 방식의 자료구조이다. 여기서 key 값은 숫자나 문자열, 혹은 File이 될 수도 있다. 그리고 해쉬 함수는, 특정한 규칙을 이용해서 입력받은 key..

Algorithm 핵심 개념들

Algorithm은 '문제를 어떤 식으로 푸는 것이 최선인가' 로 정의될 수 있다. Time Complexity Algorithm 문제들을 풀 때는 문제에 대한 해답을 찾는 것도 중요하지만 '더 효율적인 방법은 없을까?'에 대한 고민도 중요하다. 효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같다. 그리고 시간 복잡도를 고려한다는 것은 한 문장으로 정리하자면 다음과 같다. 입력값의 증가 및 감소에 따라 시간이 얼마만큼 비례하여 증가 및 감소하는가? Big-O 표기법 시간 복잡도를 표기하는 방법 중에는 다음과 같은 방법들이 있다. Big-O Big-Ω Big-θ 위 표기법들은 각각 최악, 최선, 평균의 경우 입력값의 증가에 따라 시간 복잡도가 얼마나 증가하는지 표기하는 방법들이다. 이 중에..

Data Structure 핵심 개념들

"자료 구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것" 데이터는 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값이다. 우리의 이름, 나이, 키, 집 주소, 목소리 혹은 유전자 DNA까지 데이터로 분류할 수 있다. 그러나 데이터는 그 자체만으로 어떤 정보를 가지기 힘들다. 예를 들어 나이라는 데이터만 알고 있다면, 사람의 나이인지 나무의 나이인지 알 수 없다. 이처럼 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다. 뿐만 아니라 데이터를 사용하려는 목적에 따라 형태를 구분하고, 분류하여 사용할 수 있다. 전화번호부를 작성할 때, 숫자를 3개 또는 4개씩 묶음짓고 하이픈(-)으로 합친다. 이 숫자의 묶음에 이름을 붙여 보관해야 한다면, 해당 데이터를 꺼낼..

Java의 ArrayList에 대해 알아보고 구현하기

Java의 고정된 배열 사이즈 다른 언어에서는 배열에 데이터가 추가되면 자동으로 사이즈가 늘어나는 방식으로 설계가 되어있다. 하지만 Java에서는 배열을 선언할 때 사이즈를 입력해주어야만 한다. ArrayList에 대해서 다른 언어와 마찬가지로 Java에서도 배열의 size를 유동적으로 활용할 수 있게 해준다. 그럼에도 불구하고 ArrayList의 검색 시간은 똑같이 O(1)의 복잡도를 가진다. ArrayList은 공간이 다 차면 공간을 두배로 늘려서 검색할 때는 여전히 고정된 배열에서 검색을 진행한다. 이 때, 사이즈를 두배로 늘린 뒤 기존의 값들을 복사하는 작업을 Doubling이라고 한다. Doubling 작업의 소요 시간은 기존의 데이터를 n이라고 할 때 O(n)의 시간이 소요된다. 이러한 번거로..

Java의 StringBuilder에 대해 알아보고 구현하기

StringBuilder를 사용하지 않았을 때의 문제점 public String joinWords(String[] words) { String sentence = ""; for (String w : words) { sentence += w; } return setence; } 굉장히 단순해보이지만 상당히 무거운 작업이다. 왜냐하면 두개의 문자열을 합칠 때마다 그 크기만큼의 새로운 문자열을 생성하고, 두개의 문자열에서 한 문자씩 복사해서 붙이는 작업을 하게 되기 때문이다. 각 단어의 길이를 x라고 했을 때, x + 2x + 3x + ... + nx의 방식으로 로직이 수행된다. 따라서 O(xn²)으로 표현할 수 있다. StringBuilder 활용하기 public String joinWords(String[..