Algorithm/Data Structure

특정 타입의 데이터를 연속된 형태로 묶어놓은 자료구조로, 인덱스로 데이터에 접근할 수 있어 접근에 대한 시간복잡도가 매우 낮다. ( O(1) ) 배열을 선언할 때 메모리를 할당해야 한다. 간단하게 계산할 수 있다. (타입의 크기) * (배열의 크기) int[100][100]크기의 배열을 선언하면 4 * 100 * 100이 메모리에 할당된다. 정해진 타입의 데이터를, 입력 길이가 변하지 않을 때 배열을 사용하면 편하다. 구현이 간단하고 이해하기 쉬우며 앞에서 살펴봤듯 데이터에 접근하는 속도가 매우 빠르다는 장점이 있다.

Collection인터페이스를 구현하는 컬렉션들과 Map에 대해 이어서 살펴보자. HashSet Set인터페이스를 구현한 컬렉션이며, 역시 중복을 허용하지 않고 순서가 유지되지 않는다. 지정된 순서를 보장하지 않고 자체적인 저장방식에 의해 순서가 결정되기에, 순서가 중요한 경우는 LinkedHashSet 컬렉션을 사용하는 편이 합리적이다. 여기서 Hash는 해시 함수(Hash Function)를 이용해 데이터를 해시테이블에 저장하고 검색하는 기법을 의미한다. 해시를 통해 데이터가 저장된 위치를 빠르게 알 수 있어 많은 데이터 중 원하는 데이터를 빠르게 찾아올 수 있다. 해싱 기법에서 사용하는 자료구조는 배열과 링크드 리스트로 구성된다. 저장할 데이터의 키 값을 해시함수를 통해 배열의 한 요소를 얻고, 연..

배열 sort() : 배열을 오름차순으로 정렬할 때 사용한다. binarySearch() : 배열에서 지정한 값이 저장된 위치를 찾을 때 사용한다. (중복되는 값이 있을 경우 무작위) 이진 검색은 배열의 검색범위를 절반씩 줄여가며 검색하기 때문에 빠른 속도로 검색할 수 있다. 정렬 배열을 정렬할 때 Arrays.sort()메서드를 자주 사용했는데, 사실 Character클래스의 Comparable의 구현에 의해 정렬되고 있었다. 정렬에 필요한 인터페이스로 Comparator와 Comparable이 있다. 같은 타입의 인스턴스끼리 서로 비교할 수 있는 클래스들에 대해서 (Integer, String...) Comparable인터페이스가 정의돼있고, 기본적으로는 오름차순으로 정렬을 수행한다. public i..

Collection : 가장 기초가 되는 인터페이스. List와 Set를 상속시킨다. List : Order (O) / replacement (O) - ArrayList, LinkedList, Stack, Vector... Set : Order (X) / replacement (X) - HashSet, TreeSet.. Map : List와 Set과는 다른 형태로 컬렉션을 다룬다. key) Order (X) / Replacement (X) value) Order (X) / Replacement (O) - HashMap, TreeMap, Hashtable, Properties... Collection인터페이스 add clear contains equals isEmpty remove iterator ......

배경 기존 배열은 고정된 크기를 가지고 있었고, 이 부분을 개선하기 위해 자동으로 크기가 관리되는 동적 배열의 필요성이 확대됐고, 링크드리스트가 도입됐다. 싱글 링크드 리스트 (Singly Linked List) 데이터가 추가될 때 마다 데이터와 다음 데이터의 주소를 생성한다. 미리 데이터 공간을 할당하지 않고 사용할 수 있어 편리하지만, 데이터들을 연속적으로 이어 주기 위해 다음 데이터의 주소를 담고 있는 데이터 공간을 사용해야 해서 저장공간의 효율은 좋지 않으며, 같은 이유로 데이터에 접근하는 속도도 기존 배열보다 느리다. 또한 중간에 끼어 있는 데이터를 삭제할 때도 앞뒤 데이터의 연결을 재구성해야 하는 등 추가 작업이 필요하다. // 코드 추가 예정 이중 링크드 리스트 (Doubly Linked L..