[자료구조/알고리즘] 자료구조

자료구조란

특정한 상황에 데이터를 효율적으로 다루는 방법들

자바는 stack만 구현돼 있고 나머지는 인터페이스만 있음

Stack 

• 선입후출
• 데이터를 하나씩 넣고 뺌
• 하나의 입출력 방향
• 재귀함수
• ex) 브라우저 뒤로가기, 스택메모리

 

Queue 

• 선입선출
• 데이터를 하나씩 넣고 뺌
• 두개의 입출력 방향
• ex) 일상에서 대기줄, 인쇄대기
• 원형큐 

 

Tree

• 단방향 그래프
• 하나의 뿌리로부터 가지가 뻗는 형태
• 비선형구조
• 레벨, 깊이, 부모노드, 자식노드, 형제노드, 리프, 루트
• ex) 폴더 구조

 

Graph

• 여러 개의 점들이 서로 연결되어 있는 관계를 표현한 자료구조
• 직접적인 관계/ 간접적인 관계
• 정점(vertex),  간선(edge)
• 인접행렬, 인접 리스트 (인접 리스트는 메모리를 효율적으로 사용)
• 방문여부를 표시하는 데이터 자료가 필요 

 

BST(Binary Search Tree)

• 이진 트리 종류: 정 이진 트리, 포화 이진 트리(두 개의 자식 노드가 모두 있음), 완전 이진 트리(왼쪽 자식 노드부터 채움)
• 이진 트리와 이진 탐색 트리의 차이점: 이진 탐색 트리는 요소의 크기에 따라 위치가 정해짐
• 시간 복잡도: O(logn)
• ex) 업다운

Deque

양방향 대기열

LinkedList, ArrayDeque 클래스로 구현 가능

 

Linked List

노드의 추가/삭제가 빠르고 쉬움

단, 검색을 하려면 최악의 경우 전체를 순회해야 함

ex) 삽입과 삭제가 중요한 join, split method 의 구현, 동적 기억장소 관리, Garbage Collection, 해시 테이블 충돌 시 해결방법 중 chaning

 

Hash Table

• 키와 데이터를 가진 맵 형식의 자료구조
• 값을 저장하기 위한 인덱스를 키와 해시함수를 이용
• 특징
  • 시간복잡도는 해싱을 고려하지 않기 때문에 저장, 삭제, 검색은 복잡도가 O(1)
  • 단, 해시충돌이 일어나는 경우는 저장소의 모든 인덱스(색인)(저장) 혹은 데이터(삭제, 검색)를 해봐야 하기 때문에 O(n)
• 대표적인 해시 알고리즘: Division Method, Digit Folding, Mutiplication Method, universal Hashing
• 해시 충돌 해결 방법
  • 개방 연결법
  • 분리 연결법
  • 저장소 확장
• ex) 주소록, 블록체인, JS실행 엔진(크롬, V8), Domain => DNS 변환
• 자바에서 제공

 

Heap Tree

• 일반적인 트리 구조와 다르게, 우선 순위에 따라서 빠르게 자료를 검색할 수 있는 구조 
• 응급 환자가 들어오면 순서가 바뀌는 경우
• 느슨한 정렬구조: 형제 노드끼리는 크기가 위치에 반영되지 않음
• 특징
  • 완전 이진 트리(왼쪽 자식 노드부터 채움)
  • 중복 값 저장
  • 최대 힙/ 최소 힙
• 배열로 구현 가능
• 구현 코드https://www.javatpoint.com/heap-implementation-in-java

Heap implementation in Java - Javatpoint

 

• ex)
  • 우선순위 큐(priority queue)
  • 우선 순위 큐는 자바에서 제공
  • 힙 정렬
    • https://www.geeksforgeeks.org/heap-sort/

Heap Sort - GeeksforGeeks

 

 

Search Algorithm

Tree traversal

전위순회, 중위순회, 후위순회

 

BFS/DFS

너비우선: 최단경로

깊이우선: 스택, 재귀로 구현, 경로에 장애물이 있는 경우, 깊이가 다른 경우, 그래프가 클수록 유리,  순열, 조합문제 

 

 

 

 

 

 

참고

1) 트리에 대해서

Introduction to Tree - Data Structure and Algorithm Tutorials - GeeksforGeeks

 

2) DFS/BFS 선택 기준

PS를 하며 느끼는 DFS와 BFS 선택의 기준

 

3) 우선순위 큐의 데이터 삽입/삭제 과정

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)