각 자료구조 포스팅에 big O 시간복잡도 연산별로 추가하기 big O(최악의 경우를 나타냄: 이걸로 계산한 것보다는 빠르다), big theta(평균), big omega(최선) data의 양도 큰 영향을 미침 (계수 등을 무시하기 때문) 사전조건 중요(ex. 퀵소트: 원래 n log n, 정렬이 되어 있는 것을 다시 정렬하면 worst case: n^2) log n 의 시간복잡도를 갖는 알고리즘의 증명방식 그 이전에 다시한번 알고리즘 시간복잡도가 계산되어 나오는 과정을 훨씬 더 자세하게 함 봐야될것같음 https://www.bigocheatsheet.com/ 체크포인트 리뷰

# Tree - 그래프의 일종으로, 노드로 구성된 계층적 자료구조 - 최상위의 루트노드가 자식노드를 갖고, 그 자식노드가 또 자식노드를 갖는 형식 - tree는 indegree가 무조건 1 : 1개의 부모노드만 가질 수 있음 - 트리는 순환 구조를 가질 수 없음 - node : 트리의 구성 요소 (ex. A, B, C...) - root node : 트리의 최상위 요소 (ex. A) - child node : 특정 요소의 바로 하위 요소 (ex. F, H, I에서 H, I는 F의 자식 노드) - parent : 특정 요소의 바로 상위 요소 (ex. F, H, I에서 F는 H, I의 부모 노드) - cibiling : 부모 노드가 같은 노드들 사이의 관계 (ex. D, E) - edge : 노드와 노드 사..

# Graph - 노드(node, vertex: 정점)와 그 노드들을 연결하는 간선(edge)으로 구성되는 자료구조 - 서로 연결되어 있는 원소들 간의 다대다 관계를 표현 - 그래프는 방향성이 없는 무방향(undirected) 그래프도 존재하지만, 방향성(directed)을 가질 수도 있음 - 무방향 그래프의 경우는 연결된 두 개의 노드가 대칭, 방향성을 가진 그래프는 연결된 두 개의 노드가 비대칭 관계 ## 진입차수(in-degree)와 진출차수(out-degree) - 진입차수: 방향 그래프의 경우 외부에서 해당 노드로 들어오는 간선의 수 - 진출차수: 방향 그래프의 경우 해당 노드에서 다른 노드로 향하는 간선의 수 - 그래프의 진입차수와 진출차수를 모두 더하면 그래프에 존재하는 모든 간선의 수가 됨..

# Hash Table - 키와 값이 1:1로 연결되어 있는 자료구조 - 키를 저장할 때 해당 키를 특정 인덱스로 변환하는데, 그 함수를 해시 함수(Hash function)라고 함 - 키 값에 해시함수를 적용해 해당 요소의 값이 저장되어 있는 주소값(인덱스)를 계산해 접근하는데, 이를 해싱(Hashing)이라고 함 ## Hash function의 특징 - 결과값으로 항상 해시테이블 크기 범위에 있는 숫자를 반환 (0부터 전체 길이 -1 까지) - 같은 입력값이라면 항상 나오는 결과값의 인덱스도 같아야 함 - 해시함수는 키나 특정 값을 저장하는 역할을 하지 않고, 단순히 키값을 받아 주소값을 리턴해주는 역할만 함 ## Hash Table에서의 용어 - key : 이 key를 이용해 해시함수가 특정 인덱스..

# Linked List - 각 원소의 주소값이 연속해서 붙어 있지 않고, 원소들이 각각 다음에 올 원소의 주소값을 가리키고 있는 형태 - 연결 리스트에서 각 원소들을 노드(Node) 라고 부름 - 크기가 동적인 자료구조 - 단일연결리스트(Singly-Linked List)와 이중연결리스트(Doubly-Linked List)가 있음 ## 단일 연결 리스트 (Singly-Linked List) - 노드들의 연결 방향이 한쪽 방향으로만 연결되어 있음 - 단일연결리스트의 노드는 다음에 올 노드의 주소와 자신의 값을 가지고 있어 한쪽 방향으로만 탐색이 가능 ## 이중 연결 리스트 (Doubly-Linked List) - 노드들의 연결 방향이 양쪽 방향으로 연결되어 있음 - 이중연결리스트의 노드는 자신의 값과 이..

# Stack - Stack은 데이터를 쌓아올리는 형태로 구성 - 데이터를 쌓아올릴 때, 정해진 방향으로만 데이터를 쌓아올릴 수 있음 - 데이터를 삽입하거나 삭제할 때, top으로 정해진 곳으로만 접근해 삽입, 삭제 작업을 수행할 수 있음 - top을 통해 들어온 데이터가 바닥에서부터 쌓이는 구조이므로 나중에 들어온 자료에 먼저 접근할 수 있고, 먼저 들어온 자료들은 나중에 들어온 자료들이 전부 삭제된 다음에 접근할 수 있음 => 후입선출구조 (Last in First out: LIFO) ## Stack의 사용 예시 - 컴퓨터 시스템 (시스템 스택, 실행시간 스택: 프로그램의 실행 순서를 관리) - 함수의 콜스택 - 브라우저의 방문기록 (뒤로가기) - 실행취소 - 후위표기법의 계산 - 하노이 탑 - 재귀..