[Algorithm] 깊이 우선 탐색과 넓이 우선 탐색 (DFS and BFS) 그래프 알고리즘으로, 각 상황에 맞춰 잘 사용하자. 경로 찾는 문제에서 자주 쓰인다. DFS(Depth-First Search) 깊이 우선 탐색. 루트 노드 혹은 임의의 노드에서 다음 브랜치로 넘어가기 전 해당 브랜치를 모두 탐색하는 방법. ...

[BIT] Bit Mask 집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉 왜 Bit Mask를 사용하는가? DP나 순열 등 배열 활용 만으로 해결할 수 없는 문제 작은 메모리와 빠른 수행 시간으로 해결 가능 (원소 개수 많으면 안 됨) 집합을 배열인 인덱스로 표현 가능 코드가 간결해짐 Bit? 컴퓨터에서 사용하...

[Algorithm] 이진 탐색 이진 탐색(이분 탐색) 처음부터 끝까지 돌면서 탐색하기 보단 탐색 범위를 두 부분으로 나눠 분할해서 찾는 방식. 이미 정렬된 배열에서 특정 값을 찾을 때 빠르게 찾을 수 있다. 시간 복잡도 O(logn) 진행 순서 우선 배열을 정렬 (해당 배열을 arr이라 하겠음) 0을 left, arr...

[Algorithm] 힙 정렬 (Heap Sort) 완전 이진 트리를 기본으로 하는 Heap 자료구조 기반 정렬. HeapSort는 불안정 정렬에 속한다. 시간 복잡도 O(nlogn) 완전 이진 트리? 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리. 과정 maxheap을 구성한다. root node의 요소(...

[Algorithm] 병합 정렬 (Merge Sort) 병합 정렬. Divide and Conquer(분할 정복) 방법을 이용해 구현. 안정 정렬에 속한다. 시간복잡도 O(nlogn) QS Pivot을 통해 정렬(partition) > 영역을 쪼갬 Pivot을 임의로 정하므로 L...

[Algorithm] 삽입 정렬 (Insertion Sort) 해당 index에 있는 원소를 앞에 정렬된 원소의 값과 비교해 적절한 위치를 찾아가는 알고리즘 k번째 원소를 정렬한다고 하면 0에서 k - 1번째까지 원소들은 정렬된 상태이다. 안전 정렬에 속한다. 시간 복잡도 O(n^2) 과정 배열 arr을 오름차순으...

[Algorithm] 퀵 정렬 (Quick Sort) 안전 정렬 : 동일한 값에 기존 순서가 유지(버블, 삽입) 불안정 정렬 : 동일한 값에 기존 순서가 유지X(선택, 퀵) 시간복잡도 평균 : O(nlogn) 최악 : O(n^2) 장단점 장점 불필요한 데이터 이동을 줄이고 먼 거리의 데이터를 교환, 사용한 pivot을 ...

[Data Structure] 해시 테이블 (Hash Table) 브루트포스(완전 탐색, O(n^2))로 시간 초과에 빠지게 되는 문제에 사용. 각 값의 의미 HashTable[HASH_SIZE][HASH_LEN] 테이블을 2차원 배열로 구현해 해당 값을 key를 이용해 몇 번 중복해서 들어왔는지 저장한다. TableLen[HAS...

[Algorithm] 거품 정렬 각 index를 비교하며 가장 마지막, 혹은 가장 앞에서부터 순서대로 배치한다. 구현이 단순하나 비효율적이다. 시간 복잡도 O(n^2) 과정 구현마다 다르나 오름차순으로 바로 옆 index끼리 비교하는 것으로 한다. 배열 arr이 n의 크기를 가진다 하자. k = 0 to n -1까...