Manhattan Distance

기본 입력 받기// String 타입 입력 받을 때 사용var input = readLine()!// Int 타입 입력 받을 때 사용var input = Int(readLine()!)!공백 있는 숫자 입력 받기var arr = readLine()!.split(separator: " ").map {Int($0)!} // 1 2 3print(arr) // [1, 2, 3]공백 없는 숫자/문자열을 배열로 입력 받기// 공백 없는 숫자 -> 배열var arr = Array(readLine()!).map {Int(String($0))!} 123print(arr) // [1, 2, 3]// 공백 없는 문자열 -> 배열var arr = Array(readLine()!).map {String($0)} // ABCpri..

탐색 트리란? 탐색을 위한 트리 기반의 자료구조 이진 탐색 트리 정의 모든 노드는 유일한 키를 가짐 왼쪽 서브트리의 키들은 루트의 키보다 작음 오른쪽 서브트리의 키들은 루트의 키보다 큼 왼쪽과 오른쪽 서브트리도 이진 탐색 트리임 효율적인 탐색을 위한 이진 트리 기반의 자료구조 시간 복잡도(삽입/삭제/탐색): 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(): 리..