이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. Hahsing(해싱)- Hash Table(해쉬 테이블)해쉬 테이블은 Dynamic set을 구현하는 효과적인 방법의 하나적절한 가정하에서 평균, 삽입, 삭제 시간 -> O(n)보통 최악의 경우 -> Θ(n)- Hash Function(해쉬 함수)해쉬 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.h를 사용하여 키 k를 T[h(k)]에 저장h : U -> {0, 1, 2, ... , m-1}여기서 m은 테이블의 크기, U는 모든 가능한 키들의 집합키 k가 h(k)로 해싱되었다고 말함 Hash Function(해쉬 함수)의 예- 모든 키들을 자연수라고 가정(어떤 데이터든지 자연수로 해석하는 것이 가..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. BST : Binary Search Tree(이진 검색 트리)- Dynamic Set - 여러개의 Key(키)를 저장- 다음과 같은 연산들을 지원하는 자료구조Insert : 새로운 키의 삽입Search : 키 탐색Delete : 키의 삭제 다양한 방법들- 정렬된 혹은 정렬되지 않은 배열 혹은 연결리스트를 사용할 경우Insert, Search, Delete 중 적어도 하나는 O(n)- 이진 탐색 트리, 레드-블랙 트리, AVL-트리 등의 트리에 기반한 구조들(이진 트리의 확장형들)- Direct Address Table, 해쉬 테이블 등 속성- 각 노드에 값이 있다.- 각 노드들의 키 값은 모두 달라야 한다.- 값들은 전순..
트리(Tree)- 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다.- 간단하게 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.- 트리에서 최상위 노드를 루트노드(root node)라고 한다.- 한 노드 A가 노드 B를 가리킬 때 A를 B의 부모노드(parent node), B를 A의 자식노드(chiled node)라고 한다.- 자식 노드가 없는 노드를 잎 노드(leaf node)라고 한다.- 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.출처 : 위키백과 트리의 기본적인 성질- 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다.- 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 ..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. 정렬 알고리즘 비교 정렬 알고리즘 시간복잡도Sort Algorithm T(n) Bubble Sort Θ(n2) Insertion Sort Θ(n2) Selection Sort Θ(n2) Quick Sort Worst Θ(n2) and Average Θ(nlon2n) Merge Sort Θ(nlon2n) Heap Sort Θ(nlon2n) Counting Sort Θ(n+k) Radix Sort Θ(d(n+k)) Java에서의 정렬 Sorting in Java기본 타입 데이터의 정렬Arrays 클래스가 Primitive 타입 데이터를 위한 정렬 메서드를 제공int 이외의 다른 Primitive 타입 데이터(double, c..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Radix Sort(기수 정렬)낮은 자리 수 부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다.자릿수가 고정되어 있으니, 안전성이 있고(이때 데이터들 간의 상대적 순서는 보존되어야 한다.) 기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간복잡도 역시 이어서, 정수와 같은 자료의 정렬 속도가 매우 빠르다.하지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 좋은 알고리즘이다. 예시 329 720 720 329457 355 329 3..
이 글은 인프런의 영리한 알고리즘을 위한 프로그래밍 강좌를 듣고 정리한 내용입니다. Counting Sort(계수 정렬)항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하면서 선형 시간에 정렬하는 효율적인 알고리즘- n개의 정수를 정렬하라. 단 모든 정수는 0에서 k 사이의 정수이다.- 예 : n 명의 학생들의 시험 점수를 정렬하라. 단, 모든 점수는 100 이하의 양의 정수이다. 의사코드 Counting-Sort(A, B, k) {for i
정렬의 Lower Bound
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. 정렬의 Lower Bound정렬 알고리즘의 유형 Comparison Sort- 데이터들 간의 상대적 크기 관계만을 이용해서 정렬하는 알고리즘- 따라서 데이터들 간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용가능(문자열, 알파벳, 사용자 정의 객체 등)- 버블 소트, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬 등 Non-Comparison Sort- 정렬할 데이터에 대한 사전 지식을 이용 - 적용에 제한- Bucket Sort- Radix Sort 정렬 문제의 하한어떠한 경우에도 모든 Comparison Sort의 시간복잡도는 Θ(nlogn) 보다 낮을 수 없다를 증명 하한(Lower Bound)- 입력된 데이터를..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Priority Queue(우선순위 큐)힙의 응용 : 우선순위 큐최대 우선순위 큐(Maximum Priority Queue)는 다음의 두 가지 연산을 지원하는 자료구조이다.- INSERT(x) : 새로운 원소 x를 삽입- EXTRALT_MAX() : 최대값을 삭제하고 반환 최소 우선순위 큐(Minimum Priority Queue)는 EXTRALT_MAX 대신 EXTRALT_MIN을 지원하는 자료구조이다.- MAX HEAP을 이용하여 최대 우선순위 큐를 구현 INSERT 연산 의사코드 MAX-HEAP-INSERT(A, key) { // A : heapheap_size = heap_size - 1;A[heap_size] =..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Heap Sort(힙 정렬)힙 정렬이란 최대 힙이나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.2. 최대 힙을 구성한다. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 단말 노드를 자노드로 가진 부노드로부터 구성하며 아래 부터 루트까지 올라오며 순차적으로 만들어갈 수 있다.3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.4. 2와..