TIL 자료구조 : 스택,큐,연결리스트,그래프 형태

flobeeee·2021년 1월 21일
0

Today I Learned

목록 보기
3/35

[공부방향]
1. 각각의 장단점을 파악해야함
2. 내 상황에서 어떤 것이 필요한지 알 수 있어야함

스택 ( Stack )

큐 ( Queue)

  • First in, First out
  • 실생활에서 흔히 볼 수 있음. (자판기, 번호표 등)
  • 늦게 추가할수록 순서가 계속 밀린다는 단점을 보완하기위해 우선순위 큐 사용
    (우선순위가 높은 데이터 먼저 사용 ex. 응급실 긴급환자 우선)
  • 가져오기 O(n), 추가 O(1), 삭제 O(1)

연결리스트 ( Linked List )

  • 실생활 예시 : 플레이 리스트 , 이미지뷰어 등
  • 배열과 차이점
    배열: 탐색 / 정렬 용이
    연결리스트 : 추가/ 삭제 용이
  • 가져오기 O(n), 추가 O(1), 삭제 O(1)

해시테이블 ( Hash Table )

  • 객체 저장구조와 비슷
  • 해시함수 : 어떤 값을 넣었을 때, 정보를 암호화 하거나 조금 더 자료를 정리하기 위해 일련의 값으로 만들어 내는 것을 뜻함. (input이 같으면 output은 항상 같다)
  • 해시충돌 : 해시함수를 돌린 후 같은 인덱스를 부여받았을 때 일어난다.
  • 가져오기 O(1), 추가 O(1), 삭제 O(1)

그래프 형태 자료구조 (그래프, 트리, 이진탐색트리)

그래프 표현 방식

  1. 인접리스트(가장 일반적)
    그래프 내 적은 숫자의 간선만을 가지는 경우 용이
    각각의 정점(노드)에 인접한 정점들을 리스트로 표시
    정점 추가, 삭제는 인접리스트가 효율적이다.
    (V= Vertex, 정점, E = Edge , 간선)
  • 공간복잡도 : O(V + E)
  1. 인접행렬 (정점들을 2차원 배열로 구현)
    간선의 추가와 삭제가 빈번하게 일어나는 경우에는 인접행렬 방식이 효율적이다.
  • 공간복잡도 : O(V²)

이진탐색트리(Binary Search Tree)

최대 2개의 자식만 갖는 트리
그 자식노드 역시 2개의 자식만 가짐

  • 순회방법
  1. 깊이우선탐색(DFS, Depth First Search) : 부모자식 확인후 옆 부모로 넘어감
    1-1.전위순회 : root - left - right
    1-2.중위순회 : left - root - right
    1-3.후위순회: left - right - root
    ( root를 언제 방문하냐 기준으로 나뉘어진다.)

  2. 너비우선탐색(BFS, Breadth First Search) : 레벨마다 나열

  • 종류
  1. 정 이진트리 (Full Binary Tree)
    모든 노드가 0개 || 2개의 자식을 갖는 트리

  2. 완전 이진트리 (Complete Binary Tree)
    마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 트리
    (마지막 레벨 자식들은 왼쪽에 몰려있어야 한다.)
    = 힙 (아직 배우지않았다.)

  3. 포화 이진트리 (Perfect Binary Tree)
    모든 레벨에서 노드가 꽉 찬 트리

그림참고링크

profile
기록하는 백엔드 개발자

0개의 댓글