# Object Oriented Programming (OOP) - 객체 지향 프로그래밍 - 객체 단위로 데이터와 기능을 묶어서 사용 - class라는 틀에 기본적인 속성, 기능 등을 정의하고 이를 기반으로 instance를 생성 (해당 기능을 가지는 객체를 찍어냄) ## OOP의 특징 - Encapsulation (캡슐화) : 속성, 메소드 등을 하나의 객체로 묶어 사용하기 때문에, 제 3자가 객체 내부의 데이터를 변조하는 것을 막아줌 - Inheritance (상속) : 상속을 통해 상위 객체가 가지고 있는 속성을 하위 객체가 이어받을 수 있음 - Abstraction (추상화) : 해당 객체에서 꼭 필요한 부분만 표현하고, 나머지 세부사항은 감춤 - Polymorphism (다형성) : 동일한 명령..

각 자료구조 포스팅에 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) - 노드들의 연결 방향이 양쪽 방향으로 연결되어 있음 - 이중연결리스트의 노드는 자신의 값과 이..