목록Computer Science (7)
Manhattan Distance
탐색 트리란? 탐색을 위한 트리 기반의 자료구조 이진 탐색 트리 정의 모든 노드는 유일한 키를 가짐 왼쪽 서브트리의 키들은 루트의 키보다 작음 오른쪽 서브트리의 키들은 루트의 키보다 큼 왼쪽과 오른쪽 서브트리도 이진 탐색 트리임 효율적인 탐색을 위한 이진 트리 기반의 자료구조 시간 복잡도(삽입/삭제/탐색): O(log₂n) 이진 탐색 트리 구현 class BSTNode: # 이진탐색트리를 위한 노드 클래스 def __init__(self, key, value): # 생성자 self.key = key # 키 self.value = value # 값 self.left = None # 왼쪽 자식에 대한 링크 self.right = None # 오른쪽 자식에 대한 링크 def search_bst(n, key):..
트리란? 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 트리 관련 용어 루트 노드: 부모가 없는 최상위 노드 단말 노드: 자식이 없는 노드 크기: 트리에 포함된 모든 노드의 개수 깊이: 루트 노드부터의 거리 높이: 깊이 중 최댓값 차수: 각 노드의 (자식 방향) 간선 개수 기본적으로 트리의 크기가 N일 때, 전체 간선의 개수는 N-1개 이진 트리 이진 트리의 정의 (서브 트리가) 공집합이거나 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 집합, 이진 트리의 서브 트리들은 모두 이진 트리이어야 함 이진 트리의 분류 포화 이진 트리 트리의 각 레벨에 노드가 꽉 차있는 이진 트리 전체 노드의 수: 높이가 h일 때, 2ʰ-1 완전 이진 트리 높이가 h일 때, 레벨 1부터 h-1..
정렬이란? 가장 기본적이고 중요한 알고리즘 비교할 수 있는 모든 속성들은 정렬의 기준이 될 수 있음 정렬된 자료는 탐색에 더 효율적 정렬 알고리즘 종류 단순하지만 비효율적인 방법 선택 정렬, 삽입 정렬, 버블 정렬 등 복잡하지만 효율적인 방법 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬 등 선택 정렬 리스트에서 가장 작은 숫자를 선택하여 리스트 앞쪽으로 옮기는 방법 시간 복잡도: O(n²) def selection_sort(A): # 선택 정렬 n = len(A) for i in range(n-1): least = i for j in range(i+1, n): if A[j] < A[least]: least = j A[i], A[least] = A[least], A[i] printStep(A, i+1) d..
연결된 구조란? 연결된 구조는 흩어진 데이터를 링크로 연결해서 관리 노드 = 데이터(값을 저장) + 링크(다음 노드를 가리킴) 연결된 구조의 특징 용량이 고정되지 않음 중간에 자료를 삽입하거나 삭제하는 것이 용이 → 시간복잡도: O(1) n번째 항목에 접근은 시간이 걸림 → 시간복잡도: O(n) 연결 리스트의 구조 노드 데이터: 값을 저장 링크: 다음 노드를 가리킴 헤드 포인터 첫번째 노드의 주소를 저장 연결 리스트의 종류 단순 연결 리스트 원형 연결 리스트 이중 연결 리스트 단순 연결 리스트 응용: 연결된 스택 class Node: # 노드 def __init__(self, elem, link=None): # 생성자 self.data = elem # 데이터 초기화 self.link = link # 링크..
큐란? 큐는 먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조 입구와 출구가 모두 뚫려 있는 터널과 같은 형태인 선형구조 큐 ADT 데이터: 선입선출(FIFO)의 접근 방법을 유지하는 항목들의 모음 연산 Queue(): 비어 있는 새로운 큐를 만듦 isEmpty(): 큐가 비어있는지를 검사 enqueue(x): 항목 x를 큐의 맨 뒤에 추가 dequeue(): 큐의 맨 앞에 있는 항목을 꺼내 반환 peek(): 큐의 맨 앞에 있는 항목을 삭제하지 않고 반환 size(): 큐의 모든 항목들의 개수를 반환 clear(): 큐를 공백상태로 만듦 큐의 구현 방법 원형 큐 이용 → 선형 큐는 비효율적(enqueue(item) 연산: O(1), dequeue()연산: O(n)) 원형 큐 배열을 원형으로..
스택이란? 스택은 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조 입구와 출구가 동일한 형태인 선형구조 스택 ADT 데이터: 선입후출(FILO)의 접근 방법을 유지하는 항목들의 모음 연산 Stack(): 비어 있는 새로운 스택을 만듦 isEmpty(): 스택이 비어있는지를 검사 push(e): 항목 e를 스택의 맨 위에 추가 pop(): 스택의 맨 위에 있는 항목을 꺼내 반환 peek(): 스택의 맨 위에 있는 항목을 삭제하지 않고 반환 size(): 스택의 모든 항목들의 개수를 반환 clear(): 스택을 공백상태로 만듦 스택의 구현 방법 배열 구조를 이용 파이썬에서 리스트를 사용 → 중간에 있는 항목을 꺼내지 않고 한쪽으로만 삽입, 삭제 항목의 삽입/삭제 위치 → 후단(항목들의 이동없..
리스트란? 리스트는 가장 자유로운 선형 자료구조 스택, 큐, 덱과의 차이점: 리스트는 임의의 위치에서도 항목의 삽입과 삭제가 가능 리스트 ADT 데이터: 같은 유형의 요소들의 순서있는 모임 연산 List(): 비어 있는 새로운 리스트를 만듦 insert(pos, e): pos 위치에 새로운 요소 e을 삽입 delete(pos): pos 위치에 있는 요소를 꺼내 반환 isEmpty(): 리스트가 비어있는지를 검사 getEntry(pos): pos 위치에 있는 요소를 반환 size(): 리스트안의 요소의 개수를 반환 clear(): 리스트를 초기화 find(item): 리스트에서 item이 있는지 찾아 인덱스를 반환 replace(pos, item): pos에 있는 항목을 item으로 바꿈 sort(): 리..