datastructure.md

자료구조

List

• 선형 자료구조
• 다른 자료구조와 비교했을 때, 자료의 추가 삭제의 위치가 자유롭다.

ArrayList

• 배열을 이용한 선형 자료구조
• 인덱스로 접근 가능
• 추가, 삭제시 비용이 많이든다.

LinkedList

• 노드와 포인터
• 자바 Collection의 Queue를 구현함.
• 추가, 삭제 비용이 적으나 인덱스로 접근할 수 없다.
• 멍청한 실수말길… for문에서 삭제 할 때 iterator를 사용해야 한다는 점

Queue

• 선입 선출입 구조, first in first out
• push, pop, poll 연산
• 자바 collection - linkedList로 구현
  • collections에서 arrayDeque가 더 빠르다고한다.

PriorityQueue

• 우선순위 큐
• 힙 알고리즘으로 구현

Deque

• Queue에서 앞뒤로 삽입,삭제가 가능
• 자바 Collections에서 ArrayDeque와 linkedList 로 구현

Stack

• Lifo
• push, pop, peek 연산
• 자바 컬렉션 vector - list / 구현 / 배열을 이용함
• Collections/vector는 쓰레드 안전하게 구현되어 있다.

Vector

• arrayList와 비슷하게 선형구조를 배열로 구현한 클래스
• arrayList와 다르게 쓰레드 작업이 보장되어 있어서 성능상 arrayList보다 느리다.

Map

• 키와 밸류 값이 중요
• 키는 중복이 불가능하고

HashMap

• Map을 구현하기위해 Hash Code를 사용한다.
• 해싱을 할 때 충돌이 생기면, 다음에 저장을 하거나 chaining을 이용한다.
• 충돌이 검색 성능을 좌우 한다. O(1), 최악의 경우 O(n)에 접근 할 수 있다.
• 안드로이드에서 sparseArray를 사용하라고 권장함.
• HashMap의 동작원리 - d2
• HashMap의 버킷의 크기는 임계점에 도달하면 2배씩 커진다. 기본은 16
• 충돌을 관리하기 위해서 red-black tree 알고리즘을 사용한다.

TreeMap

• 키가 저장될 때 키값이 정렬된다.
• HashMap은 배열로 이루어져있기 때문에 O(1) 접근이 가능하다. 그에 비해 TreeMap은 tree로 구현되어 있기 때문에 value를 찾는 시간이 O(lonN)이 걸린다. 키를 정렬하고 싶을 때 사용하면 된다.

SET

• 순서와 상관없이 해당 key가 포함되어있는지만 중요하다.
• key에 대한 중복이 불가능 하다.

HashSet

• HashMap을 사용하여 구현

TreeSet

• 저장된 데이터의 값에 따라 정렬됨

LinkedHashSet

• 저장된 순서에 따라 값을 정렬

Tree

• Connected Component이면서 cycl이 존재하지 않은 그래프
• 순회방식이 중요 / 전위, 중위, 후위
• 검색 O(lgN)의 시간 복잡도
• 깊이가 깊어질 수록 속도가 느려진다.

Binary Search Tree

• 이진 트리모양의 자료구조에 이진탐색의 개념을 더한 자료구조
• 중위 순회 방식의 사용한다.
• 탐색이 빠르다. 탐색할때 좌우로 내려가며 해당값이 리프노드에 있더라도 O(lgN)의 탐색 시간 복잡도를 가지고 있다.
• 왼쪽 자식 < root < 오른쪽 자식 순으로 정렬된다.

Heap

• 최소, 최댓값을 구하기 위한.
• 완전이진트리 -> 항상 완전 이진트리 이기 때문에 배열을 사용하는 것이 좋음
• Priority Queue를 구현 / 배열을 이용
• Heapify -> 힙 성질을 만족하도록 하는 연산
  • 삽입 : 배열 마지막에 새로운 데이터를 넣고 부모와 비교하여 힙을 구성한다.(형제와 비교할 필요 없다.)
  • 삭제 : 해당 데이터를 삭제하고 배열 마지막 데이터를 해당 자리에 넣어 자식들과 비교한다. (자식 모두와 비교해야한다.)

알고리즘

• 최소신장트리
  • 신장트리 - 그래프의 최소 연결 부분 그래프 = 모든 노드가 연결되도록 가장 작은 수의 간선이 포함된 트리
  • 최소신장트리 - 신장트리중 간선의 가중치가 가장 작은 신장트리
• 크루스칼 알고리즘
  • 모든 간선중에서 가장 가중치가 작은 간선을 선택한다.
    • 가중치가 가장 작은 간선을 선택할때 사이클이 생기는지 확인한다.
    • 사이클이 생기지 않은 간선만을 포함 시킨다.
  • 간선에 연결된 노드를 포함한다.
• 프림 알고리즘
  • 시작 정점을 선택한다.
  • 정점에 연결된 간선중 가중치가 가장 낮은 간선과 그에 연결된 노드를 최소신장트리 집합에 포함시킨다.
  • 다시 최소신장트리에 포함된 노드들 에 연결된 가장 작은 간선을 선택한다.
  • 위의 과정을 반복한다.

Graph

구현

• 인접행렬

  • 행렬로 그래프 구현
  • 엣지 정보에 대한 접근이 빠르다.
  • 메모리 공간을 많이 차지한다.

• 인접 리스트

  • 메모리 공간을 덜 차지하나, 정점의 엣지를 찾기위한 추가적인 과정이 필요하다.
  • 링크드 리스트를 배열로 가지고 있다.

탐색

• BFS

  • 너비우선 탐색
  • 큐를 사용

• DFS

  • 깊이 우선 탐색
  • 스택이나 재귀를 사용한다.

최단거리 알고리즘

• 다익스트라
  • 하나의 정점에서 모든 정점까지의 최단거리
• 플루이드 와샬
  • 모든 정점들 사이의 최단거리를 구하는 알고리즘
  • 삼중 for 문을 활용해서 모든 거리의 최단거리를 구하는 알고리즘
  • dis[i][k] + dist[k][j] 와 dist[i][k];
  • dp를 사용한다.
  • 시간 복잡도가 O(lgN^3)이기 때문에 정점의 수가 많으면 사용해서는 안된다.
• 벨만포드 알고리즘
  • 하나의 정점에서 모든 정점까지의 최단거리를 구한다. 음의 사이클이 있음을 확인 할 수 있다.

정렬

선택정렬

• 배열 중에가 가장 작은 아이템을 선택하여 앞쪽으로 옮긴다.
• n, n-1, n-2, … 1 번의 비교가 필요하기 때문에 O(n^2)의 시간복잡도를 가진다.

삽입정렬

• n번째 데이터를 차례대로 비교한다. n번째를 기준으로 왼쪽은 정렬이되게 하는 정렬 방법
• 역으로 정렬되어 있을 경우 O(n^2), 순정렬일경우 O(n)의 시간 복잡도를 가진다.
• n번째 데이터를 정렬할 차례라면 n-1, n-2, n-3…1 번째 데이터와 비교하면 자리를 잡는다.

버블정렬

• 앞쪽부터 두개씩 비교하여 가장작거나 / 가장큰것을 제일 뒤로 보낸다.
• 역시 n, n-1, … 1 번의 비교가 필요하기 때문에 O(n^2)의 시간복잡도가 필요하다.

퀵정렬

• 피봇을 이용한 정렬 방법이다 .
• 피봇을 기준으로 작은 수는 왼쪽으로 큰수는 오른쪽으로 정렬하는 방법이다. 정렬이 되면 피봇을 고정한다.
• 피봇에 따라 성능이 달라진다.
• 선택된 피봇이 반으로 나눌수록 성능이 좋아지면 한쪽으로 치우쳐 있을 경우 성능이 낮아진다.
• 최악의 경우 O(N^2), 최선의 경우 O(N*lgN)의 성능이다

합병정렬

• 분할 정복의 방법을 사용한다.
• 해당 높이별로 최대N번의 비교가 필요하다. 평균O(N*lgN)의 시간복잡도

힙정렬

• 자료구조 힙을 이용한 정렬 방법이다.
• 주어진 배열을 힙으로 만든 다음. 최대값/최솟값을 하나씩 제거하는 방식이다.
• O(N*lgN)의 시간 복잡도