그래프 정점(vertax)과 간선(edge)으로 이루어진 자료 구조 가중치 : 간선과 정점 사이에 드는 비용 트리 정점과 간선으로 이뤄진, 트리 구조로 배열된 계층적 데이터의 집합 부모, 자식 계층 구조 E = V - 1, 간선 수는 노드 수 - 1 루트 노드 : 가장 위에 있는 노드 내부 노드 : 루트 노드와 리프 노드 사이에 있는 노드 리프 노드 : 자식이 없는 노드 깊이 : 루트 노드로부터 특정 노드까지 최단 거리 높이 : 루트 노드로부터 리프 노드까지 거리 중 가장 긴 거리 서브 트리 : 트리 내의 하위 집합 이진 탐색 트리 (BST) 노드의 오른쪽 하위 트리에는 ‘노드 값보다 큰 값’ 이 있는 노드만 포함되고, 왼쪽 하위 트리에는 ‘노드 값보다 작은 값’이 들어 있는 트리 탐색 시간 복잡도는 O..
배열 같은 타입의 변수들로 이뤄졌으며, 크기가 정해져 있고, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합 중복을 허용하고 순서가 있음 삽입 / 삭제 O(n), 탐색 O(1) *배열은 요소의 인덱스만 알면 해당 요소를 끄집어낼 수 있지만 연결리스트는 요소들을 하나씩 탐색해가며 요소를 찾아야 함 벡터 동적으로 요소를 할당할 수 있는 동적 배열. 컴파일 시점에 개수를 모른다면 벡터를 사용 중복을 허용하고 순서가 있음. 랜덤 접근 가능 탐색과 맨 뒤의 요소를 삽입 / 삭제 O(1), 중간의 요소를 삽입 / 삭제 O(n) 크기가 고정적인 배열과 달리 러닝타임 때 배열의 크기가 변할 때 벡터를 사용 *삽입삭제가 번번히 일어나는 상황에서는 벡터던 배열이던 비효율적 연결 리스트 데이터를 감싼 노드를 포인터로 연결..
시간 복잡도 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 알고리즘 로직이 ‘얼마나 오랜 시간’ 걸리는지 입력된 N 의 크기에 따라 실행되는 조작의 수 ( 연산수치, 명령어의 실행 횟수 ) 빅오 표기법 사용, Ex. 10n^2 + n 은 O(n^2) O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함. O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬. O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐. O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형) O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력..
