자료구조 정리

코딩테스트 문제는

논리는 복잡하더라도 답은 간단하다.

최대한 얍삽하게 풀면 된다.

 

시간복잡도와 공간복잡도를 고민하고

제한 조건에 맞는 풀이법을 고민해야 한다.

문제를 풀 때는 항상 최악의 케이스를 고려해야 한다.

 

1억번은 1초가 걸린다고 가정하는 것이 좋다.

 

N^2으로 풀 수 있는 문제는 다이나믹, 스트링, 구현문제들은 n^2이 나오는 경우가 많다.

1초 1억회 0.1초 3천만 이내로 풀어야 시간초과가 안 나올 확률이 높다.

————————————————————————————————————————————————

 

1.배열

i번째 인덱스 데이터에 Access - O(1)

데이터의 삽입 / 삭제(배열의 사이즈가 달라질 떄) / 어떠한 데이터가 존재하는지 탐색 - O(N)

 

장점: 데이터 탐색이 빠르다. 

단점: 데이터 삽입 삭제시 데이터를 복사해 시간이 오래걸린다. /데이터를 탐색할 때도 순차적으로 검색해서 오래걸린다. 

 

2.ArrayList

i번째 인덱스 데이터에 Access / 배열 끝에 삽입- O(1)

데이터의 삽입 / 삭제(배열의 사이즈가 달라질 떄) / 어떠한 데이터가 존재하는지 탐색 - O(N)

 

배열과 리스트는 데이터가 변경하지 않을 떄 사용하기 좋다.

데이터에 접근할 때는 배열이 제일 빠르다.

 

3.queue

데이터의 Add(Append) / 데이터의 poll (pop) - O(1)

i번째 데이터에 접근/삽입/삭제 O(N) / 어떠한 데이터가 존재하는지 탐색 O(N)

 

배열에 비해서 메모리를 효율적으로 사용할 수 있음

 

4.deque

데이터의 Add(Append) / 데이터의 poll (pop) - O(1)

i번째 데이터에 접근/삽입/삭제 O(N) / 어떠한 데이터가 존재하는지 탐색 O(N)

 

양쪽 끝에서 데이터의 삽입/삭제가 가능한 큐

Deque로 Queue와 Stack을 구현할 수 있음

 

5.stack 

가장 위에 있는 데이터에 대한 접근/삭제 

가장 위에 데이터 삽입 - O(1)

 

i번째 데이터에 접근/삽입 삭제

어떠한 데이터가 존재하는지 탐색 - O(N)

 

스택을 활용한 유명한 문제로는 펠린드 룸 문제가 있음

함수(메소드)의 호출은 내부적으로 스택 자료 구조를 이용하여 동작함

 

6.재귀

프로그램의 내부적으로 함수의 호출은 스택 자료구조를 사용하여 구현됨

재귀함수를 이용한 알고리즘은 스택과 비슷하게 생각하면 이해가 조금 더 수월하다.

 

 

7.우선순위 큐 - 다익스트라 알고리즘을 위해서는 우선순위 큐를 사용해야 한다.

 

데이터의 삽입 / 우선순위가 가장 큰(작은) 데이터 접근/삭제 - O(logN)

i번째 데이터에 접근/삽입/삭제 O(NlogN)

어떠한 데이터가 존재하는지 탐색O(N)

 

 

8.맵/셋

 

 

 

 

9.HashMap

 

어떠한 데이터(Key)가 존재하는지 탐색

Key에 대한 Value에 접근/삭제

Key-Value 저장 - O(1)

 

어떠한 Value가 존재하는지 탐색 - O(N)

 

언어에 따라 딕셔너리라고 부르기도 한

딕셔너리의 내부 구조는 HashMap으로 구현되어 있음

 

자바 8 이후는 2번째 인덱스에 해쉬충돌이 일어나서 8개까지 연결되는 순간 2진 트리로 바꾼다.

트리로 바꿔서 충돌이 발생하면 O(logN)으로 찾을 수 있게 만든다.

 

데이터를 지워서 8개보다 줄어들면 다시 링크드 리스트로 바꾼다.

 

Hash -> 단방향 암호화

Plain text - hash - sha-256 (256bit) - secure hash algorithm

 

 

 

 

자바 컬렉션 프레임 워크

 

 

Collection

 

List - ArrayList, Vector, LinkedList

 

Set - HashSet, TreeSet

 

Map - HashMap, HashTable, TreeMap, Properties

 

Collection - List  : 순서를 유지하고 저장, 중복 저장 기능

                     - Set  : 순서를 유지하고 저장, 중복 저장 안됨

 

                      - Map : 키와 값으로 구성된 엔트리 저장

                      - 키는 중복 저장 안됨

 

List 컬렉션 

 

객체추가

 

boolean add(E e) 주어진 객체를 맨 끝에 추가

Void add(int index) 주어진 인덱스에 객체를 추가

set(int index, E element) 주어진 인덱스의 객체를 새로운 객체로 바꿈

 

객체검색

 

boolean contains(Object o) 주어진 객체가 저장되어 있는지 여부

E get (int index) 주어진 인덱스에 저장된 객체를 리턴

isEmpty() 컬렉션이 비어 있는지 조사

Int size() 저장되어 있는 전체 객체 수를 리턴

 

객체 삭제

 

Void clear() 주어진 모든 객체를 삭제

E remove(int index) 주어진 인덱스에 저장된 객체를 삭제

Boolean remove(Object o) 주어진 객체를 삭제

 

ArrayList - 제한 없이 객체를 추가할 수 있다.

 

List<E> list = new ArrayList<E>();

List<E> list = new ArrayList<>();

List list = new ArrayList(); // 모든 타입의 객체를 저장

 

빈번한 객체 삭제와 삽입이 일어나는 곳에서는 ArrayList를 사용하는 것은 바람직하지 않다.

다만 이런 경우라면 LinskedList를 사용하는 것이 좋다. 다음은 ArrayList에 객체를 추가, 검색 삭제하는 방법을 보여준다.

 

Vector - ArrayList와 동일한 내부 구조를 가지고 있다. 차이점은 Vector는 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 Vector() 메소드를 실행할 수 없다는 것이다.

그렇기 떄문에 멀티 스레드 환경에서는 안전하게 객체를 추가 또는 삭제할 수 있다.

 

LinkedList- 사용 방법은 ArrayList와 동일하지만 내부 구조는 완전히 다르다. ArrayList는 내부 배열에객체를 저장하지만 LinkedList는 인접 객체를 체인처럼 연결해서 발휘한다.

빈번한 객체 삭제와 삽입이 일어나는 곳에서 좋은 성능을 발휘한다.

 

 

Set 컬렉션

 

List 컬렉션은 저장 순서를 유지하지만, Set 컬렉션은 저장 순서가 유지되지 않는다. 또한 객체를 중복해서 저장할 수 없고 하나의 null만 저장할 수 있다. Set 컬렉션은 수학의 집합에 비유될 수 있다.

집합은 순서와 상관없고 중복이 허용되지 않기 때문이다.

 

Set 컬렉션은 또한 구슬 주머니와도 같다. 동일한 구슬을 두 개 넣을 수 없으며, 들어갈 (저장할) 때와 나올(찾을) 떄의 순서가 다를 수도 있기 때문이다.

 

객체 추가 

 

Boolean add(E e) - 주어진 객체를 성공적으로 저장하면 true를 리턴하고 중복 객체면 falsefㅡㄹ 리턴

 

객체 검색

 

Boolean contains(Object o) - 주어진 객체가 저장되어 있는지 여부

isEmpty() 컬렉션이 비어 있는지 조사

Iterator<E> iterator() 저장된 객체를 한 번씩 가져오는 반복자 리턴

Int size() 저장되어 있는 전체 객체 수 리턴

 

객체 삭제

 

Void clear() 저장된 모든 객체를 삭제

Boolean remove 주어진 객체를 삭제

 

HashSet은 동일한 객체는 중복 저장하지 않는다. 여기서 동일한 객체란 동등 객체를 말한다.

HashSet은 다른 객체라도 hashCode() 메소드의 리턴값이 같고, equals() 메소드가 true를 리턴하면 동일한 객체라고 판단하고 중복 저장하지 않는다.

 

Set 컬렉션은 인덱스로 객체를 검색해서 가져오는 메소드가 없다.

대신 객체를 한 개 씩 반복해서 가져와야 하는데, 여기에는 두 가지 방법이 있다.

하나는 다음과 같이 for 문을 이용하는 것이고 하나는 Iterator을 사용하는 것이다.

 

Map컬렉션

 

객체 추가 

 

V put(K key, V value) 주어진 키와 값을 추가, 저장이 되면 값을 리턴

 

객체 검색

Boolean containsKey(Object key) 주어진 키가 있는지 여부

Boolean containsValue(Object value) 주어진 갑ㅈㅅ이 있는지 여부

Set<Map.Entry<K,V>> entrySet() 키와 값 쌍으로 구성된 모든 Map.Entry 객체를 Set에 담아서 리턴

V get(Object key) 주어진 키의 값을 리턴

Boolean isEmpty() 컬렉션이 비어있는지 여부

Set<K> keySet() 모든 키를 Set 객체에 담아서 리턴

Int size() 저장된 키의 총 수를 리턴

Collection<V> values() 저장된 모든 값 Collection에 담아서 리턴

 

객체 삭제 

 

Void clear() 모든 Map.Entry(키와 값) 를 삭제

V remove(Object key) 주어진 키와 일치하는 Map.Entry 삭제, 삭제가 되면 값을 리턴

 

HashMap - 키로 사용할 객체가 hashCode() 메소드의 리턴값이 같도 equals() 메소드가 true를 리턴할 경우, 동일 키로 보고 중복 저장을 허용하지 않는다.

 

Hashtable - Hashtable은 Hashmap과 동일한 내부 구조를 가지고 있다. 차이점은 Hashtable은 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 Hashtable의 메소드들을 실행할 수 없다는 것이다. 따라서 멀티 스레드 환경에서도 안전하게 객체를 추가 삭제할 수 있다.

 

Properties - Properties는 HashTable의 자식 클래스이기 때문에 HashTable의 특징을 그대로 가지고 있다. Properties 는 키와 값을 String 타입으로 제한한 컬렉션이다. Properties는 주로 확장자가 .Properties인 프로퍼티 파일을 읽을 떄 사용한다.

 

검색 기능을 강화시킨 컬렉션

 

컬렉션 프레임워크는 검색 기능을 강화시킨 TreeSet과 TreeMap을 제공한다. 이름에서 알 수 있듯이 TreeSet은 컬렉션이고, TreeMap은 컬렉션이다.

 

TreeSet은 이진트리를 기반으로 한 Set 컬렉션이다. 이진 트리는 여러 개으 ㅣ노드가 트리 형태로 연결된 구조로, 루트 노드라고 불리는 하나의 노드에서 시작해 각 노드에 최대 2개의 노드를 연결할 수 있는 구조를 가지고 있다.

 

TreeSet에 객체를 저장하면 다음과 같이 자동으로 정렬된다. 부모 노드의 객체와 비교해서 낮은 것은 왼쪽 자식 노드에 높은 것은 오른쪽 자식 노드에 저장한다.