알고리즘 도감 - (1) 데이터 구조

1. 리스트 : 접근 느리나, 추가, 삭제 빠름

- ArrayList<Integer> list = new ArrayList<>();

-add, remove

​

2. 배열 : 접근 빠르나, 추가, 삭제 느림 (but, 선언시 크기 정해짐)

int [] array =new int[];

​

3. 스택 : first in last out, 최신정보 찾을 때 유용

-Stack<Integer> stack = new Stack<>();

-push, pop

​

4. 큐 : first in first out, 오래된 데이터부터 순서대로 처리해야 하는 경우

-Queue<Integer> list = new LinkedList<>();

-enqueue, dequeue

-add, offer, remove, clear, poll

​

5. 해쉬테이블 : key, value

- Hashtable<Integer, String> table= new Hashtable<Integer, String>();

- put, replace, remove, get

- 배열로 넣을 시, 선형탐색 -> 간단히 하기 위해 해쉬 함수 사용해서 넣는 방식

- 연쇄법, 개방주소법

​

6. 힙 : 그래프의 트리 구조 중 하나, 최솟값을 자주 추출해야 하는 경우

-PriorityQueue<Integer> heap = new PriorityQueue<>();

우선순위가 낮은 순자 순

-PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverOrder());

우선순위가 높은 숫자 순

***하지만, 우선순위큐 라이브러리를 사용하지 않고, 구현할 수 있도록 하기!

-add, poll, remove, clear, peek

-추가는 자유롭게 하고, 작은 값부터 꺼내는 것 : 우선순위 큐 (Priority Queue)

​

7. 이진 탐색 트리

- 모든 노드는 왼쪽 가지에 포함되는 어떤 숫자보다도 큰 숫자가 됨

- 모든 노드는 그 노드의 오른쪽 가지에 포함되는 어떤 숫자보다 작은 숫자가 됨

-즉, 그 숫자보다 작으면 왼쪽, 크면 오른쪽으로 이동