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

자료구조

개념

자료구조란?

• 다양한 데이터를 하나의 틀로 묶는 구조

자료구조 종류

• 단순 구조
  • 2진수, 정수/실수, 문자/문자열
• 선형 구조
  • 배열, 연결 리스트(단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트)
  • 덱, 스택, 큐
• 비선형 구조
  • 트리(일반 트리, 이진트리)
  • 그래프(방향 그래프. 무방향 그래프)
• 파일 구조
  • 순차 파일, 색인 파일, 직접파일

Stack

• 개념
  • 쌓는다는 뜻
  • LIFO(Last in First out)
• 특징
  • 후입 선출
  • 하나씩 넣고(push), 뽑기(pop)
  • 하나의 입출력 방향
• 대표적 사례
  • 브라우저의 앞으로 가기, 뒤로 가기
• java stack
  • push, pop, size, peek, clear, show
• 선언
  • Stack <T> stack = new Stack <>();

Queue

• 개념
  • 줄의 개념
  • FIFO(First in First out)
• 특징
  • 선입선출
  • 하나씩 넣고(push), 뽑기(pop)
  • 두 개의 양방향 입출력
• 대표적 사례
  • 컴퓨터 출력의 인쇄 작업
• java queue
  • add, poll, size, peek, clear, show
• 선언
  • Queue <T> queue = new LinkedList <>();

Tree

• 개념
  • 부모 노드로부터 자식 노드들로 뻗어나가는 구조
  • 방향이 없이 연결되고 비선형 구조
• 특징
  • 데이터를 저장하는 node 존재
  • 맨 위 루트 노드(root node) 존재
  • 상하로 관계로 여러 개의 데이터를 선(edge)으로 연결
    • 상위에 있는 노드는 부모 노드(parent node)
    • 하위에 있는 노드는 자식 노드(child node)
  • 최하위 자식이 없는 노드는 리프 노드(leaf node)
  • 같은 레벨에 있는 노드는 형제 노드(sibling node)
• 구성
  • 깊이(depth) : 루트 노드(0)로부터 하위 노드 사이의 깊이
  • 레벨(level) : 같은 높이에 있는 노드를 말하는 계층(루트가 level 1)
  • 높이(hight) : 리프 노드(0)로부터 특정 노드까지의 높이
  • 서브 트리(sub tree) : 트리 내부에 트리 형태를 구성하는 부분 트리
• 대표적인 사례
  • 파일 시스템

Graph

• 개념
  • 여러 개의 점들을 서로 연결해 놓은 구조
• 구성
  • 정점(vertex)과 간선(edge)으로 구성
• 구현
  • 인접 행렬(adjacency matrix) : 2차원 배열로 연결이 되어 있으면 1로 표시
    • 가중치 그래프 : 2차원 배열에 값을 표시
    • 최단 경로를 위해 사용
  • 인접 리스트(adjacency list) : 각 정점마다 리스트를 가지고 인접한 정점을 연결
    • 인접 행렬에 비해 메모리 적게 소모
• 그 외의 개념들
  • 인접 정점(adjacency vertex) : 한 정점에서 연결되어 있는 다른 정점
  • 가중치/비가중치 그래프(weighted/unweighted graph) : 가중치가 있는 그래프와 없는 그래프
  • 방향/무방향 그래프(directed/undirected graph) : 간선에 방향이 존재하거나 존재하지 않는 그래프
  • 진입차수/진출차수(in-degree/out-degree) : 정점에서 들어오거나 나가는 간선의 수
  • 자기루프(self-loop) : 정점에서 연결된 간선 중 자기 자신으로 오는 경우
  • 사이클(cycle) : 한 정점에서 간선을 타고 이동하여 자신으로 돌아올 수 있는 경우

Binary Search Tree

• 이진 탐색 트리(BST) : 효율적인 탐색을 위한 트리 자료구조
• 이진트리(Binary Tree)
  • Full Binary Tree(정이진트리) : 각 노드가 자식 노드를 0 또는 2개를 가지는 트리
  • Perfect Binary Tree(포화 이진 트리) : 모든 리프 노드의 레벨이 같고 모든 레벨이 가득 채워진 트리
  • Complete Binary Tree(완전 이진 트리) : 리프 노드를 제외한 모든 레벨이 가득 채워지고 리프 노드가 왼쪽부터 채워진 트리
• BST 특징
  • 왼쪽 자식 노드가 부모 노드보다 작은 값, 오른쪽 자식 노드가 부모 노드보다 큰 값이 들어감
  • 균형이 잡히지 않아 한 쪽에 치우쳐진 경우 효율성이 떨어짐
  • 단점을 보완하기 위해 red-black tree를 사용(몇 가지 규칙으로 균형을 맞춰 준다)

Tree Traversal

• 개념
  • 트리의 모든 노드를 방문
  • Preorder traversal - root, left child, right child 순서로 순회
  • Inorder traversal - left child, root, right child 순서로 순회
  • Postorder traversal -left child, right child, root 순서로 순회

BFS(Breadth First Search)

• 그래프에서 너비를 우선적으로 탐색
• 두 정점 사이 최단 경로를 찾을 때 주로 사용(ex Dijkstra)
• 주로 큐(queue)를 사용해서 구현

DFS(Depth First Search)

• 그래프에서 깊이를 우선적으로 탐색
• 다음 경로를 넘어가기 전 완전히 탐색
• 주로 재귀를 사용해서 구현
• 그래프가 클수록 DFS 사용
• 장애물이 존재하는 경우는 DFS 사용

Deque(Double Ended Queue)

• 개념
  • 양방향 대기열
  • stack과 queue의 속성이 혼합
  • queue와 비슷한 형태이지만 데이터를 뺄 때 순서에 구속되지 않는다
• 특징
  • 양방향 추가 가능, 단방향 제거
  • 양방향 제거 가능, 단방향 추가
  • 양방향 추가 , 제거 가능
  • 중간에 임의의 데이터에 추가, 수정, 제거하는 것이 불가

Linked List

• 개념
  • 선형 자료구조로 데이터와 다음 데이터의 주소를 포함
  • 데이터들이 연결되어 있는 구조
  • 일렬로 세워 인덱스를 부여한 배열과 차이 존재
• 특징
  • 노드의 추가 제거가 빠르고 용이(O(1) 시간 복잡도)
  • 특정 노드 값을 조회할 때 순차로 순회해야 하기 때문에 비효율적(최대 O(n) 시간 복잡도)
• 사용 예
  • 삽입, 삭제가 중요한 메서드(join, split)
  • 동적 기억 장소(실행에 필요한 메모리 할당)
  • garbage collection

Hash Table

• 개념
  • key를 hash function을 사용하여 hash로 바꾸고 value를 저장하는 구조
• 구조
  • key : 고윳값, 길이가 다 다르다
  • hash function : key를 같은 길이의 hash로 변환, 서로 다른 키가 같은 hash값을 가지면 hash collision 발생
  • hash : hash function으로 얻은 값으로 value값과 매칭
  • value : 저장하고자 하는 데이터
• 특징
  • 시간 복잡도 O(1)로 데이터 관리 가능
  • hash function에 대한 의존도가 높아 복잡할수록 hash 생성에 오랜 시간 발생
  • 저장, 삭제, 검색 : O(1)의 복잡도를 가지나 hash collision이 발생할 경우 최대 O(n)
• 알고리즘
  • division method
    • modular를 사용하여 저장소 크기로 숫자 key값을 나누어 hash 생성
    • 저장소 크기를 소수로 정하고 2의 거듭제곱과 먼 값을 설정할 때 hash collision 줄일 수 있다.
  • digit folding
    • 문자열 key를 ascii 코드로 바꾸고 합하여 hash를 생성
    • 저장소 크기를 넘어간다면 division method 사용
  • multiplication method
    • 숫자 key 값에 특정 실수(0 <A <1)를 곱하여 소수 부분을 취해서 hash table 크기 m을 곱해 정수부를 취한다.
    • (key*A mod 1)*m
  • universal hashing
    • 여러 개의 hash function을 랜덤으로 가져와 적용
• hash collision 해결 방법
  • 개방 연결법(Open Addressing)
    • collision이 발생하면 다른 index로 가서 데이터 저장
    • linear probing : 특정 크기만큼 이동하여 저장
    • Quadratic probing : 이동할 숫자를 제곱으로 하여 이동
    • Double Hashing Probing : 충돌하면 다른 hash function 사용
  • 분리 연결법(Seperate Chaining)
    • 충돌이 발생하면 linked list나 tree 형태로 데이터 저장
  • 저장소 확장(Resize)
    • 저장소의 크기를 늘려서 성능 손실 감소
  • 사용 예시
    • DNS, Address book, block chain, 자바 스크립트 실행 엔진

Heap tree

• 개념
  • 우선순위에 따라 구성된 트리 구조
  • 부모 - 자식 간에는 정렬이 되어있지만 자식 간에는 정렬이 안되어 있다.
• 특징
  • 완전 이진트리 - 삽입 삭제 시 O(logn)
  • 중복 값 저장 -BST와 다르게 중복값 저장
  • 최대 힙 / 최소 힙
• 데이터 처리 방식
  • 최댓값/최솟값 검색
    • root 값으로 O(1)
  • 데이터 삽입
    • O(logn)
  • 데이터 삭제
    • O(logn)