Algorithm/Java class library package

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

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

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[..

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..