목표가 생기면 무작정 달려들어야지. 실패를 두려워 할 여유같은 건 없을 때니까

[주제]- 이진 탐색 트리의 개념 [정의]- 이진 탐색 트리에는 데이터를 저장하는 규칙이 있음. 그 규칙은 특정 데이터의 위치를 찾는데 사용됨- 이진 트리 + 데이터의 저장 규칙 = 이진 탐색 트리 [중요]- 이진 탐색 트리의 노드에 저장된 키(Key)는 유일- 루트 노드의 키는 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크며, 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작음- 왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키- 왼쪽/오른쪽 서브 트리도 이진 탐색 트리- 삽입 과정과 탐색 과정은 동일하게 진행 ※ 키는 정수 값으로 설정했다는 가정 ■ 그림(이진 탐색 트리) ■ 그림(이진 탐색 트리의 데이터 삽입 과정) - 비교대상이 없을 때까지 내려감- 비교대상이 없는 때 ..

[주제]- 보간 탐색의 개념 [정의]- 이진 탐색의 비효율성을 개선시킨 알고리즘 [중요]- 효율적인 탐색을 위해서는 '어떻게 찾을까'가 아닌, 효율적인 탐색을 위한 '저장방법'이 무엇인지를 우선 고민해야 함- 탐색 대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작 ※ 예) 고길동이라는 사람의 전화번호를 찾을 때, 전화번호부의 인덱스를 보고 'ㄱ'에 해당하는 앞쪽에서 찾기 ■ 그림(보간 탐색) - 보간 탐색은 찾아야 하는 값이 상대적으로 앞에 위치한다고 판단하면 앞쪽에 탐색 - low: 탐색 대상의 '시작' 인덱스 값- high: 탐색 대상의 '끝' 인덱스 값- S: 찾는 데이터가 저장된 위치의 인덱스 값- 보간 탐색은 데이터의 값과 그 데이터가 저장된 위치의 인덱스 값이 비례한다고 가정 ■ 1차 공식 A..

[주제]- 기수 정렬에 대한 개념 [정의]- 기수(Radix)란 '주어진 데이터를 구성하는 기본 요소'를 말함 ※ 예) 2진수의 기수: 0, 1, 10진수의 기수: 0 ~ 9 1. LSD(Least Significant Digit) 방식의 정렬- '가장 작은 자릿수'부터 정렬을 진행 ※ 가장 오른쪽부터(숫자로 치면 1의 자리수부터) - 가장 작은 자릿수부터 가장 큰 자릿수까지 비교해야 된다는 단점이 존재하지만, 코드 구현은 MSD에 비해 간결 2. MSD(Most Significant Digit) 방식의 정렬- '가장 큰 자릿수'부터 정렬을 진행 ※ 가장 왼쪽부터 - 코드 구현은 LSD에 비해 추가 작업(정렬 상태 확인)이 필요하지만, 중간에 정렬이 완료될 수 있는 장점이 존재 [중요]- 기수 정렬은 정..

[주제]- 퀵 정렬에 대한 개념과 구현 [중요]- 피벗의 시작 위치는 '맨 왼쪽 or 중간 or 맨 오른쪽'이 될 수 있음- 좀 더 효율적이기 위해 처음:중간:마지막 숫자끼리 비교해서 중간 값을 피벗으로 설정하는 것이 효율적임 또는, 맨 왼쪽(오른쪽) 3개 숫자를 비교- 피벗을 중심으로 영역을 두 개로 분할하여 정렬 ※ 재귀 ■ 그림(퀵 정렬 과정)- 숫자 '5, 7, 4, 2, 1, 8, 3, 6'을 오름차순으로 정렬 - 맨 왼쪽 숫자를 피벗으로 결정- 비교 숫자(low)는 피벗 숫자의 오른쪽부터 시작 - 'low'는 해당 위치의 숫자가 피벗 위치의 숫자보다 높을 때까지 오른쪽으로 이동- 'high'는 해당 위치의 숫자가 피벗 위치의 숫자보다 낮을 때까지 왼쪽으로 이동 ※ 'low'의 이동이 끝나야 '..

[주제]- 병합 정렬에 대한 개념과 구현 [중요]- 정렬의 과정 => 1단계: 복합(Divide) → 2단계: 정복(Conquer) → 3단계: 결합(Combine)- 정렬할 배열을 중간을 기준으로 2개로 나눠서 따로 정렬- 1:1로 비교될 때까지 분할- 다시 거꾸로 숫자를 비교해가면서 정렬 ※ 재귀 ■ 그림(병합 정렬 과정)- 숫자 '5, 7, 4, 2, 1, 8, 3, 6'을 오름차순으로 정렬 [소스]■ Merge.javapackage sortMerge; public class Merge { public Merge() {} ///// 분할된 숫자들을 병합 public void MergeTwoArea(int arr[], int left, int mid, int right) { int fIdx = lef..

[주제]- 정렬 알고리즘 종류 중 선택 정렬에 대한 개념과 구현 [중요]- 첫 번째 위치에 있는 숫자는 정렬된 상태로 간주 ※ 자신보다 앞에 비교할 대상이 없기 때문 - 자신보다 앞에 위치한 숫자랑 비교해가면서 배치(정렬)을 같이 진행 ■ 그림(삽입 정렬 과정)- 숫자 '2, 4, 3, 1'을 오름차순으로 정렬 - 두 번째 위치의 숫자를 임시 공간에 저장- 임시 공간의 숫자와 앞에 위치한 숫자와 비교- 임시 공간의 숫자가 더 높으므로 앞에 위치한 숫자 뒤에 배치 - 다음 위치의 숫자를 임시 공간에 저장- 임시 공간의 숫자와 앞에 위치한 숫자와 비교- 임시 공간의 숫자가 더 낮으므로 앞에 위치한 숫자는 뒤로 이동 - 다시 임시 공간의 숫자와 더 앞에 위치한 숫자와 비교- 임시 공간의 숫자가 더 높으므로 앞..

[주제]- 정렬 알고리즘 종류 중 선택 정렬에 대한 개념과 구현 [중요]- 모든 비교를 끝낸 뒤 맨 왼쪽으로 이동- 이동된 숫자는 정렬이 완료된 상태이기 때문에 다음 정렬된 숫자는 완료된 숫자 다음의 위치로 이동됨 ■ 그림(선택 정렬 과정)- 숫자 '3, 4, 2, 1'을 오름차순으로 정렬 - 전체 값 중에 가장 작은 숫자를 찾을 때까지 비교- 찾은 값의 위치와 맨 왼쪽 위치와 교체 - 정렬된 숫자를 제외하고 남은 숫자 중 작은 값을 찾을 때까지 비교- 찾은 값의 위치를 정렬 완료된 숫자의 오른쪽 위치에 있던 숫자와 교체 - 위와 같음 ■ 실행결과 [첨부 파일]

[주제]- 정렬 알고리즘 종류 중 버블 정렬에 대한 개념과 구현 [중요]- 오름차순 정렬 시(내림차순 정렬 시) 가장 큰(작은) 값을 오른쪽으로 이동- 마지막 숫자는 정렬이 완료된 상태기 때문에 더 이상 정렬 진행하지 않음 ※ 전체 길이의 '-1'한 만큼 정렬 진행 ■ 그림(버블 정렬 과정)- 숫자 '4, 2, 1, 3'을 오름차순으로 정렬 - 첫 번째 숫자와 두 번째 숫자 비교- 첫 번째 숫자가 더 높으니 위치 교체 - 두 번째 숫자와 세 번째 숫자 비교- 두 번째 숫자가 더 높으니 위치 교체 - 세 번째 숫자와 네 번째 숫자 비교- 세 번째 숫자가 더 높으니 위치 교체 - 1회전 정렬 종료- 다시 처음부터 반복 [소스]■ BubbleSort.javapackage sortBubble; public cl..