해쉬 테이블 해쉬 테이블은 해시 값을 index로 삼아 key와 value를 저장하는 자료구조이다. 빠른 검색이 필요한 경우에 많이 사용되는 자료구조인데 내부적으로 배열을 사용하여 값을 저장하기 때문이다. 해쉬 테이블은 각 Key 값에 해쉬함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다. 이때 실제 값이 저장되는 장소를 버킷이라고 한다. 자바에서 제공하는 Hashtable 클래스를 살펴보면 해당 자료구조에 값을 저장할 때 아래의 그림처럼 동작한다. key를 자바에서 제공하는 해쉬함수인 hashCode()를 이용하여 해쉬 값으로 변경하고 그 변경한 값을 인덱스 값으로 또 계산하는 것을 볼 수 있다. 시간복잡도 추가, 삭제 : O(1) 검색 : O(1) 하..
스택(Stack) 스택은 데이터를 제한적으로 접근할 수 있는 자료구조이다. 앞선 글에서 설명한 큐는 FIFO 방식을 사용하는 자료구조이다. 스택은 LIFO(Last-In, First-Out) 방식을 사용하는 자료구조이다. 즉, 가장 마지막에 넣은 데이터를 가장 먼저 꺼내는 자료구조라고 할 수 있다. 이 자료구조가 활용되는 대표적인 예시로는 우리가 지금 사용하고 있는 Java의 JVM이다. JVM에는 메서드 호출 시, 스택 메모리에 메서드가 담기는데 이 때 스택 자료구조가 활용된다. 예를 들어 A메서드 안에서 B메서드를 호출한다고 가정해보자. 그럼 A메서드가 스택 영역에 할당되고, 그 다음 B메서드를 호출하는 부분에서 B메서드가 할당될 것이다. 당연하게도 메서드의 흐름상 B메서드가 먼저 동작이 끝날테니 B..
큐(Queue) 큐는 먼저 입력한 데이터를 먼저 꺼내는 자료구조이다. FIFO(First-In, First-Out) 방식을 사용하는 자료구조라고도 할 수 있다. 이는 만약 우리가 식당에 줄을 서면 먼저 줄을 선 사람이 먼저 입장을 하는 것과 동일하다고 생각하면 될 것 같다. 위의 그림에 주요 용어들이 있는데, 설명하자면 아래와 같다. Enqueue : 큐에 값을 넣는 기능 Dequeue : 큐에서 값을 꺼내는 기능 head : 큐의 맨 앞 부분, front 라고도 함 tail : 큐의 맨 뒷 부분, rear 라고도 함 큐에 값이 추가된다면, tail 위치에 값이 Enqueue 될 것이다. 그리고 값을 지운다면 head의 값이 Dequeue 될 것이다. Enqueue 위의 그림처럼 큐는 선입선출 구조이고,..
배열(Array) 배열은 값을 나열하고, 각 값을 인덱스에 대응하도록 구성한 자료구조이다. 배열이 필요한 이유 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 같은 종유의 데이터를 순차적으로 저장 장점 값에 빠른 접근이 가능하다. (시간복잡도 O(1)) 단점 중간에 값을 추가, 삭제하기가 쉽지 않다. 미리 크기를 할당해야한다. 또는 배열의 크기를 가변할 수 없다. 위의 내용들을 자바로 예를 들어서 알아보려고 한다. 우선 먼저 배열을 만들어주는데, 위의 단점에 설명했듯이 배열은 선언할 때 미리 크기를 할당해야한다. 그래서 아래와 같이 크기가 7인 배열을 하나 만들어주자. int[] arr = new int[7]; 위의 그림처럼 크기가 7인 배열이 생성된다. int형의 배열을 생성했기 때문에 int 자..
