목록분류 전체보기 (10)
Manhattan Distance
Java Source code .java: 사람이 이해할 수 있는 파일, 기계는 이해할 수 없는 파일Java Application .class: 기계가 이해할 수 있도록 변환된 파일Java Virtual Machine: Java 로 개발한 프로그램을 컴파일하여 만들어지는 바이트코드를 실행시키기 위한 가상머신computer: 컴퓨터우리가 .java 라는 확장자를 가진 Java Source code 파일을 생성하게 되면, 인간은 이를 이해할 수 있으나 기계는 아직 이해할 수가 없다. 그렇기 때문에 Compile 이라는 단계를 통해서 이를 기계가 이해할 수 있도록 .class 라는 확장자를 가진 Java Application 파일로 변환한다. 최종적으로 실행하게 되면, Java Virtual Machine 이..
귀류법어떤 명제가 참이라고 가정한 후, 모순을 이끌어내 그 가정이 거짓임을, 즉 처음의 명제가 거짓임을 증명하는 방법 우선 결론부터 얘기하면, 소수는 무한하다.유클리드는 BC 300년경 귀류법으로 소수의 무한성을 증명하였다.귀류법으로 다음과 같이 증명할 수 있다.우선 소수의 개수가 유한한 k개라고 가정해보자.그리고 모든 소수를 다 곱하고 1을 더한 수를 n이라고 하자. n은 아래와 같이 표현할 수 있다.n = P₁ * P₂ * P₃ * ... * Pₖ + 1 (P₁ = 첫 번째 소수, Pₖ = 마지막 소수)이때 n은 제일 마지막 소수인 Pₖ보다 클 것이고, 위 명제가 참이라면 n은 합성수여야 한다.소인수분해를 통해서 합성수는 소수들만의 곱으로 나타낼 수 있어야 되지만, n은 어떤 소수로 나누어도 나머지..
기본 입력 받기// 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)) 원형 큐 배열을 원형으로..