이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강의를 듣고 정리한 내용입니다. 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..