목표 Hash Table에 대해 설명할 수 있다. Hash Table 과정에 대해 설명할 수 있다. Hash Table를 Python으로 구현할 수 있다. 요약 Hashing 임의의 길이의 값을 해쉬 함수를 사용하여 고정된 크기의 값으로 변환하는 작업 해쉬 함수 Division Method : 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.(주소 = 입력값 % 테이블의 크기) 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다. Digit Folding : 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 향한 데이터를 테이블 내의 주소로 사용한다. Mutiplication Method : 숫자로 된 Key 값 K와 0과 1사이의 실수 A, 보통 2의 제곱수..
목표 Binary Search에 대해 설명할 수 있다. Binary Search 과정에 대해 설명할 수 있다. Binary Search를 Python으로 구현할 수 있다. Binary Search의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다. 요약 탐색 범위를 두 부분으로 분할하면서 찾는 방식 처음부터 끝까지 순회하면서 탐색하는 것보다 훨씬 빠르다. 전체 탐색 : O(N), 이분 탐색 : O(logN) 과정 우선 주어진 배열을 정렬해야 한다. left, right로 mid 값을 구한다. mid와 내가 구하고자 하는 값과 비교하여 구할 값이 mid보다 높으면 left를 mid + 1로 설정한다. 구할 값이 mid보다 낮으면 right를 mid - 1로 설정한다. mid와 구할 값이 일치하..
목표 Counting Sort에 대해 설명할 수 있다. Counting Sort 과정에 대해 설명할 수 있다. Counting Sort를 Python으로 구현할 수 있다. Counting Sort의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다. 요약 시간 복잡도가 O(n+k)로 매우 효율이 좋아보이는 정렬이다. 좋아보인다는 표현을 쓴 이유는 배열 내의 최댓값 k의 크기에 따라 오히려 효율이 나빠지기 때문이다. n이 10일 경우, k가 1000이라면 O(10 + 1000)이기 때문에 O(n^3)이나 다를바 없다. k에 따라서 메모리도 많이 사용하게 된다. 과정 (오름차순) 배열에 있는 숫자 중 가장 큰 값만큼의 배열을 만들어준다. 주어진 배열을 순회하면서 카운팅 배열의 인덱스에 맞는 값의 ..
목표 Radix Sort에 대해 설명할 수 있다. Radix Sort 과정에 대해 설명할 수 있다. Radix Sort를 Python으로 구현할 수 있다. Radix Sort의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다. 요약 Radix Sort는 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 정렬하는 알고리즘이다. 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. (공간 복잡도가 높아진다.) 과정 (오름차순) 0~9 까지의 Bucket(Queue 자료구조)을 준비한다. 주어진 데이터의 숫자를 보고 1의 자리수의 숫자에 해당하는 Bucket에 데이터를 넣는다. Bucket 0부터 9까지 차례대로 데이터를 가져온다..
목표 Heap Sort에 대해 설명할 수 있다. Heap Sort 과정에 대해 설명할 수 있다. Heap Sort를 Kotlin으로 구현할 수 있다. Heap Sort의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다. 요약 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반한 정렬 방식 완전 이진 트리 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리 힙(Heap) 부모 노드가 자식 노드보다 항상 작은 형태의 완전 이진트리(오름차순 기준) 삽입 아래와 그림과 같은 Heap이 있다고 하자. Heap의 삽입은 먼저 가장 끝의 노드에서 이뤄진다. 여기에 2를 추가하게 된다면 다음과 같이 추가된다. 부모 노드는 항상 자식 노드보다 작아야 한다. 새로 추가 된 2 노드의 부모 노드와 비교하..
목표 Merge Sort에 대해 설명할 수 있다. Merge Sort 과정에 대해 설명할 수 있다. Merge Sort를 Kotlin으로 구현할 수 있다. Merge Sort의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다. 요약 Merge Sort는 분할 정복 알고리즘의 하나이다. 분할 정복 알고리즘(Divide and Conquer) : 큰 문제를 2개의 작은 문제로 나눈 다음에 해결한 후 결과를 모아서 원래의 큰 문제를 해결하는 방식 하나의 리스트를 균등하게 두 개의 리스트로 나눈 다음 정렬한 후, 두 개의 정렬된 리스트를 다시 합하여 정렬된 하나의 리스트로 만드는 방법이다. Quick Sort가 피벗을 기준으로 정렬을 수행한 다음에 분할 한다면 Merge Sort는 분할을 먼저 하고..
퀵 정렬 (Quick Sort)
목표 퀵 정렬(quick sort)에 대해 설명할 수 있다. 퀵 정렬(quick sort) 과정에 대해 설명할 수 있다. 퀵 정렬(quick sort)를 Kotlin으로 구현할 수 있다. 퀵 정렬(quick sort) 의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다. 요약 합병 정렬과 같이 분할 정복 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 합병정렬과는 달리 리스트를 비균등하게 분할한다. 분할 정복 (divide and conquer) 방법 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략. 대개 순환 호출을 이용하여 구현한다. 과정 (오름차순) 리스트 안에 있는 한 요소(피벗)을 선택한다. 피벗을 기준..
목표 Insertion Sort에 대해 설명할 수 있다. Insertion Sort 과정에 대해 설명할 수 있다. Insertion Sort를 Kotlin으로 구현할 수 있다. Insertion Sort의 특징을 이해하여 시간 복잡도와 공간 복잡도를 계산할 수 있다. 요약 Insertion Sort는 Selection Sort와 비슷하여 헷갈릴 수 있지만 좀 더 효율적인 정렬 알고리즘이다. Insertion Sort는 2번째 요소부터 시작하여 그 앞의 요소들과 대소 비교하여 삽입할 위치를 지정한 후 삽입할 위치 이후의 요소들을 한 칸씩 뒤로 미루면서 삽입하는 정렬 알고리즘이다. 최선의 경우에는 O(N) 이라는 빠른 효율성을 가지고 있어 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다. 과..