게으름뱅이의 앞구르기

트리 나무 형태를 뒤집은 것과 같은 형태의 자료구조 루트 : 최상단 노드 리프 : 가장 끝 노드 길이(length): 출발 노드에서 목적지 노드까지 거쳐야하는 가지 수 높이(height): 루트노드에서 가장 깊은 노드까지의 길이 부모 - 자식관계를 가지며, 같은 부모면 형제노드라고함 이진 트리(Binary tree) 최대 2개의 자식을 가질 수 있는 트리 포화 이진 트리(Full Binary Tree) : 리프노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리 완전 이진 트리(Complete Binary Tree) : 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리 높이 균형 트리(Height Binary Tree) 편향트리 : 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1이상 차이나지 않는 트리 ..

순차 탐색(Sequential search) 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색 O(N)의 시간복잡도를 가짐 검색할 리스트의 길이가 길면 비효율적 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있음 이진탐색(Binary search) 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 O(logN)의 시간 복잡도를 가짐 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 됨 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있음 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 참고..

기수정렬이란? 낮은 자리수부터 비교하여 차례대로 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘 자릿수 배열(자릿수에 대한 값의 배열을 담음) 누적으로 값을구함 원소값 뒤에서부터 결과 배열에 자릿수를 기준으로 정렬을 함(1의자리까지 정렬) 10의자리를 기준으로 자릿수 누적값 구함 원소로 만듦 각 데이터의 자릿수를 기준으로 분류하므로 가장큰 자릿수를 D라고 했을때 O(DN)의 시간 복잡도를 가짐(1의 자리, 10의 자리...) 실제로 D는 그렇게 큰 값이 아니게 형성이되어 O(N)에 가까운 시간 복잡도를 가지므로 제법 빠른 알고리즘 계수정렬보다는 약간 느리지만 숫자가 큰 상황에서도 사용가능 부동소수점 실수 등에는 사용할 수 없음 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수

계수정렬이란? 계수정렬(Counting sort)은 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘. 배열의 크기를 인덱스로 삼고, 해당 인덱스에 속하는 데이터의 수를 저장한 뒤, 순서대로 나열함. 데이터를 바로 크기 기준으로 분류하므로 O(N)의 시간 복잡도를 가짐 배열의 크기를 기준으로 배열을 세기 때문에 인덱스를 넘어가는 수는 정렬못함(→ 메모리소모가 큼) 참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수

퀵정렬이란? "빠른" 정렬 알고리즘. 피벗을 기준으로 큰 값과 작은값을 서로 비교하고 교체하는 정렬. 리스트 가운데서 피벗이라고 하는 하나의 원소를 고름 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 함. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않음 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복하며 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복됨 값을 서로 교체하는데 N번, (엇갈렸을때) 전체 원소 나누는데 평균 logN번이 소요되므로 평균적으로 O(NlogN)의 시간복잡도를 가짐 최악의 경우에는 O(N²)번의 비교를 수행함 퀵정렬은 완전..

버블정렬이란? 두 인접한 원소를 검사하여 정렬하는 방법. 시간복잡도가 O(N²)로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용됨 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름

삽입정렬이란? 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 "삽입"함으로써 정렬을 완성하는 알고리즘 들어갈 위치를 선택하는데 N번, 선택하는 횟수 N번으로 O(N²)의 시간 복잡도를 가짐 배열이 길어질수록 효율이 떨어지지만, 구현이 간단함 선택정렬이나 버블 정렬에 비해 빠름 void insertion_sort ( int *data, int n ) { int i, j, remember; for ( i = 1; i = 0 && remember < data[j] ){ data[j+1] = data[j]; data[j] = remember; } } } 참고 | Wiki..

선택정렬이란? 제자리 알고리즘의 하나로 제일 작은 값을 "선택"해서 앞으로 보내는 정렬 주어진 리스트 중에 최소값을 찾음 그 값을 맨 앞에 위치한 값과 교체 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체 가장 작은 것을 선택하는데 N번, 앞으로 보내는데 N번의 연산으로 O(N²)의 시간 복잡도를 가짐 가장 작은 수를 앞으로 보내줄 때, 선택된 수가 현재 있는 위치와 맞바꿈 이중포문을 이용해 정렬 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있음 참고 | Wikipedia, Fast Campus 컴퓨터 공학 전공 필수