자료구조의 분류
선형구조
- 배열, 스택, 큐, 덱,
- 리스트
- 선형(연속) 리스트: 순차적
- 연결 리스트: 비순차적
비선형구조
- 트리, 그래프
선형구조
배열(Array)
- 메모리상에 데이터를 연속으로 배치한 자료구조
- 정적인 자료구조
- 반복적인 데이터 처리 작업에 적합
스택(Stack)
- 한쪽 끝으로만 자료의 삽입/삭제가 이뤄지는 자료구조
- 후입선출(LIFO;Last In First Out) 방식
- 용도: 재귀호출, DFS, 웹 방문기록, 인터럽트 처리, 수식 계산, 서브루틴 복귀번지 저장 등
큐(Queue)
- 한쪽끝에서 삽입, 반대쪽에서 삭제가 이뤄지는 자료구조
- 선입선출(FIFO;First In First Out) 방식
- 시작과 끝을 표시하는 두 개의 포인터 존재
- 용도: 인쇄작업 대기목록, 프로세스관리, BFS 등
덱(Deque)
- 양쪽 끝에서 삽입/삭제가 모두 이뤄지는 자료구조
리스트(List)
연속(순차)리스트
- 배열과 같이 연속되는 기억장소에 저장되는 자료구조
- 접근 시 인덱스 사용으로 빠름
- 저장 효율이 뛰어남
- 중간 삽입을 위해 연속된 빈공간이 있어야함
- 삽입/삭제 시 자료 이동 필요
연결리스트
- 자료를 임의의 공간에 기억시키고, 각 노드의 포인터를 이용해 서로 연결시킨 자료구조
- 노드의 삽입/삭제 작업 용이
- 접근 시 포인터를 찾아야하므로 속도 느림
- 포인터를 위한 추가 공간 필요
- 중간에 연결이 끊어지면 다음 노드 찾기 힘듦
비선형구조
트리(Tree)
- 정점(Node)와 간선(Branch)를 이용해 사이클을 이루지 않도록 구성한 그래프의 특수한 형태
- 차수와 단말노드(20.6,8)
- 차수(Degree): 각 노드에 연결된 자식 수
- 단말 노드(Terminal Node): 트리의 마지막 노드, 자식이 하나도 없는/Degree가 0인
트리의 순회방법
(20.6,8)
- 전위순회: root - left - right
- 중위순회: left - root - right
- 후위순회: left - right - root
트리의 종류
- 이진 트리: 최대 2개의 자식을 가진 노드로 구성된 트리
- 완전이진트리
- 포화이진트리
- 편향이진트리: 최악의 경우 검색 O(n)
그래프(Graph)
방향 그래프
- 정점을 연결하는 선에 방향이 있는 그래프
- n개의 정점으로 구성된 방향그래프의 최대 간선수 = n(n-1)
무방향 그래프
- 정점을 연결하는 선에 방향이 없는 그래프
- n개의 정점으로 구성된 무방향그래프의 최대 간선수 = n(n-1)/2
수식표기법
- 전위표기법(Prefix): +AB
- 중위표기법(Infix): A+B
- 후위표기법(Postfix): AB+
표기법 변환
중위표기법 → 전위표기법
A*(B+C)/D-E(((A*(B+C))/D)-E)(-/(*(A+(BC))D)E)-/*A+BCDE
중위표기법 → 후위표기법
A*(B+C)/D-E(((A*(B+C))/D)-E)(((A(BC)+)*D)/E)-ABC+*D/E-
전위표기법 → 중위표기법
-/*A+BCDE(-(/(*A(+BC))D)E)(((A*(B+C))/D)-E)A*(B+C)/D-E
후위표기법 → 중위표기법
ABC+*D/E-(((A(BC+)*)D/)E-)(((A*(B+C))/D)-E)A*(B+C)/D-E
해싱
- 주어진 키를 해시함수에 대입하여 결과값(해시값)을 생성하고, 이 해시값을 인덱스로 사용하여 해시테이블 내 데이터에 직접 접근하는 기술
- 삽입/삭제/검색 모두 O(1)
해싱함수
제산법
키값을 특정숫자로 나눈후 그 나머지를 해시값으로 사용
중간제곱법
키값을 제곱한 다음 그결과의 중간부분을 해시값으로 사용
중첩법
키를 여러부분으로 나눈후, 합치거나 XOR연산을 수행해 해시값으로 사용
숫자분석법
데이터의 특성을 분석하여 데이터 분포의 균등성을 유지하면서 해시값 결정
기수변환법
키값을 다른진법의 숫자로 변환하여 해시값으로 사용
무작위방법
난수 생성 알고리즘 사용
공부한 내용은 바로바로 기록하자!