🤔Merge Sort(병합정렬) 이란 ? 병합 정렬은 분할 정복 (Divide and Conquer) 방식을 이용해서 하나의 리스트를 두 개의 리스트로 분할한 다음 각각의 분할된 리스트를 정렬한 후에 합해서 정렬된 하나의 리스트로 만드는 정렬 알고리즘 💡 과정 주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (Divide : 분할) → mergeSort() 메소드 해당 부분리스트의 길이가 1이 아니라면 1번 과정을 되풀이한다. → if (start == end) return; 인접한 부분리스트끼리 정렬하여 합친다. (Conqure : 정복) → merge() 메소드 ⚡ 특징 시간 복잡도 : 최선, 평균, 최악 모두 $O(NlogN)$ 데이터를 “비교”하면서 찾기 때문에 비교정렬 추가 메모리 필요 ..

Binary Search (이분탐색) 이란? "정렬"되어 있는 배열에서 특정 값의 위치를 찾는 탐색알고리즘이다. 탐색하는 배열을 둘로 나누고 찾고자하는 값이 존재하는 영역만 탐색하기 때문에 전체를 탐색하는 경우보다 당연히 빠르게 찾을 수 있다. 더보기 백준 문제 1. 수 찾기 https://www.acmicpc.net/problem/1920 과정 내가 찾고자하는 값을 '타겟'이라고 하자. 이분탐색은 주로 배열에서 타겟의 위치(인덱스)를 찾고자 할 때 많이 사용된다. 1. 탐색할 배열을 정렬한다. 2. 탐색할 영역의 중앙값( = (시작점 + 끝점)/2)이 타겟과 비교한다. 2-1. 중앙값이 타겟과 같다면 중앙값의 위치를 반환하고 탐색을 종료한다. 2-2. 타겟이 중앙값보다 작다면 다음엔 중앙값을 기준으로 ..

Topology Sort (위상 정렬) 이란? 위상 정렬은 사이클이 없는 방향그래프 (DAG: Directed Acyclic Graph)에서 각 정점의 선후를 위배하지 않고 정렬하는 알고리즘이다. 정해진 선후만 위배하지 않으면 되기 때문에 정렬된 결과가 여러개가 나올 수 있다. 작업의 순서가 정해져 있을때 일직선의 순서를 찾는 알고리즘이라고 생각하면 편하다. ex ) 집도착 → 손발 씻기 → 밥먹기 → 설거지하기 → 과제하기 → 유튜브 보기 → 잠자기 이때 주어진 엣지의 방향만 지키면 된다. 만약 기초수학 → 물리 기초수학 → 화학 이라는 선후가 주어진다면 기초수학→물리 → 화학 도 괜찮고 기초 수학 →화학 →물리 도 괜찮다 같이보면 좋은 백준 문제 더보기 백준 문제 https://www.acmicpc...

Counting Sort (계수 정렬) 이란? 계수 정렬은 값을 비교하지 않고 각 값들의 개수를 세어서 그 값들이 몇번째 인덱스 부터 몇번째 인덱스까지 위치하는 지를 알아내 정렬하는 알고리즘이다. 더보기 백준 문제 https://www.acmicpc.net/problem/2751 과정 과정은 간단하다. 1. 가장 큰 값 찾기 -> 큰 값까지 인덱스를 가지는 배열 만들기 2. 만든 배열에 인덱스를 값으로 하는 값의 개수 담기 3. 각 값의 개수를 누적으로 바꾸기 4. 뒤에서부터 자리 찾아주기 위 순서에 따라서 위 arr 배열을 정렬해보자 1. 가장 큰 값을 찾는다. ➡️ max = 5 2. 각 값의 개수를 담는다. arr값을 인덱스로 하여 arr의 값의 개수를 담는 count 배열을 만든다. 3. 각 값의..

10진 문자 0 NULL 48 0 65 A 97 a