dion

목차1. 기수 정렬2. 계수 정렬3. 셸 정렬  1. 기수 정렬 (Radix Sort)  - 낮은 자리 수부터 정렬하는 방식  * 123 > 3(일의 자리)  - 각 원소 간의 비교 연산을 하지 않아 빠른 대신, 기수 테이블을 위한 메모리 필요  - 알고리즘 복잡도 : O(dn) *d : 최대 자릿수  2. 계수 정렬 (Counting Sort)  - 숫자 끼리 비교하지 않고 카운트를 세서 정렬하는 방식  - 카운팅을 위한 메모리 필요  - 알고리즘 복잡도 : O(n + k)  *k : 정렬 대상 데이터 중 최대값  3. 셸 정렬 (Shell Sort)  - 삽입 정렬의 약점을 보완한 정렬 방식  - 삽입 정렬의 약점 : 오름차순 정렬 기준, 내림차순으로 구성된 데이터에 대해서는 앞의 데이터와 하나씩 비..

알고리즘 2024. 9. 24. 15:40

목차1. 합병 정렬2. 힙 정렬3. 퀵 정렬4. 트리 정렬  1. 합병 정렬 (Merge Sort)  - 배열을 계속 분할해서 길이가 1이 되도록 만들고, 인접한 부분끼리 정렬하면서 합병하는 방식  - 추가저장을 위한 메모리 필요 (인플레이스 정렬과 반대)  - 알고리즘 복잡도 : O(nlogn)  2. 힙 정렬 (Heap Sort)  - 힙 자료구조 형태의 정렬 방식  - 기존 배열을 최대 힙으로 구조 변경 후 정렬 진행  - 알고리즘 복잡도 : O(nlogn)   3. 퀵 정렬 (Quick Sort)  - 임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식  - 한번 정렬 후 기준 값 왼쪽에는 기준값보다 작은 수만, 오른쪽에는 기준 값보다 큰 수만 존재  - 알고리즘 복잡도 : ..

알고리즘 2024. 9. 24. 15:27

목차1. 정렬2. 버블 정렬3. 삽입 정렬4. 선택 정렬  1. 정렬  - 특정 값을 기준으로 데이터를 순서대로 배치하는 방법  - 구현 난이도는 쉽지만, 속도는 느린 알고리즘      - 버블 정렬, 삽입 정렬, 선택 정렬  -  구현 난이도는 조금 더 어렵지만, 속도는 빠른 알고리즘      - 합병 정렬, 힙 정렬, 퀵 정렬, 트리 정렬  - 하이브리드 정렬      - 팀 정렬, 블록 병합 정렬, 인트로 정렬  - 기타 정렬 알고리즘      - 기수 정렬, 카운팅 정렬, 셸 정렬, 보고 정렬  * 인플레이스 정렬 : 제자리 정렬, 추가적인 메모리 필요 없이 메모리 공간 내에서 해결 (버블, 삽입, 선택) 2. 버블 정렬 (Bubble Sort)  - 인접한 데이터를 비교하며 자리 바꾸는 방식  ..

알고리즘 2024. 9. 24. 15:07

목차1. 알고리즘2. 알고리즘의 조건3. 좋은 알고리즘4. 알고리즘 Part Summary  1. 알고리즘 (Algorithm)  - 어떤 문제 해결을 위한 절차나 방법  - 각각의 알고리즘에는 정형화된 플로우가 존재  2. 알고리즘의 조건  - 입력  - 출력  - 명확성  - 유한성 : 정해진 시간 내에 알고리즘이 동작해야함  - 효율성 : 시간 복잡도 혹은 공간 복잡도가 효율적으로 짜여진 것  3. 좋은 알고리즘  - 정확성  - 시간 복잡도  - 공간 복잡도  4. 알고리즘 Part Summary  - 정렬  - 이진 탐색 / 투 포인터  - 그리디 알고리즘  - 분할 정복 / 다이나믹 프로그래밍  - 백 트래킹  - 최단 경로  - 최소 신장 트리

알고리즘 2024. 9. 24. 13:54