hashing 된 맵, 해싱 함수를 사용하여 key와 value 쌍으로 데이터를 보관하는 맵 자료구조 특성 순차적으로 데이터를 저장하지 않는다. key를 통해 value 를 얻는다. value값은 중복가능하지만 key는 중복될 수 없다. 수정 가능(mutable)하다. 시간복잡도 삽입 : O(1) 탐색 : O(1) Dictionary ### 선언 및 초기화 d = {} d = {'alice': 1, 'bob': 20, 'tony': 15, 'suzy': 30} d = dict() d = dict(alice = 5, bob = 20, tony = 15, suzy = 30) # 컴프리헨션 초기화 num_d = {key: 0 for key in range(10)} # {0: 0, 1: 0, 2: 0, 3: 0..
먼저 들어간 데이터가 먼저 나오는 FIFO (First In First Out)의 성질을 가진 자료구조 특성 삭제 연산이 수행되는 곳을 front, 삽입연산이 수행되는 곳을 rear 라 한다. 요소는 rear로 들어와서 front로 빠진다. 접근은 가장 첫 원소와 끝 원소만 가능하다. rear에서 수행되는 삽입연산을 enQueue, front에서 수행되는 삭제연산을 deQueue라 한다. 시간복잡도 삽입/삭제 : O(1) 탐색 : O(n) Queue 사용 with Python # 데이터 흐름: 왼쪽방향 queue = [1, 2, 3] # enQueue queue.append(4) # queue = [1, 2, 3, 4] # deQueue queue.pop(0) # 1 반환, queue = [2, 3, 4..
가장 마지막으로 들어간 데이터가 먼저 나오는 LIFO(Last In First Out)의 성질을 가진 자료구조 특성 top으로 정한 곳을 통해서만 접근이 가능하다. top 은 가장 위에 있는 요소를 가리키며, 삽입되는 새 요소는 top 위에 쌓인다. top이 가리키는 요소가 추출/삭제된다. 삽입 연산을 push, 추출 연산을 pop이라 한다. 시간복잡도 삽입/삭제 : O(1) 탐색 : O(n) Stack 사용 with Python stack = [1, 2, 3] # push stack.append(4) # stack = [1, 2, 3, 4] # pop stack.pop() # 4 반환, stack = [1, 2, 3] # top stack[-1] # 마지막 인덱스의 데이터 = 제일 위에 있는 데이터 = 3
그래프 정점(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차 시간 : 문제를 해결하기 위한 단계의 수는 입력..
