전체 글
-
2024 자료구조개론 & 알고리즘개론 정리 - 7. 최적화 기법 (DP, Greedy, Divide & Conquer)Data Structure & Algorithms 2024. 4. 16. 16:11
2024 자료구조개론 & 알고리즘개론 정리 - 7. 최적화 기법 (DP, Greedy, Divide & Conquer) 1. 배열과 링크드리스트 2. Hash Table 3. Queue & Stack 4. Tree & Graph 5. Sorting 6. Recursion 7. 최적화 기법 (DP, Greedy, Divide & Conquer)
-
2024 자료구조개론 & 알고리즘개론 정리 - 5. SortingData Structure & Algorithms 2024. 4. 16. 16:10
2024 자료구조개론 & 알고리즘개론 정리 - 5. Sorting 1. 배열과 링크드리스트 2. Hash Table 3. Queue & Stack 4. Tree & Graph 5. Sorting 6. Recursion 7. 최적화 기법 (DP, Greedy, Divide & Conquer) 생각해보니까 목차에 Recursion이 먼저 오는 게 맞았을지도 ... ㅎㅎㅎ 정렬은 크게 안정 정렬, 불안정 정렬이 있을 수 있겠다 안정 정렬은 동일한 숫자의 데이터가 여러 개 들어왔을 때, 그 들어온 순서가 변하지 않는 방식으로 정렬된다 합병 정렬, 삽입 정렬, 버블 정렬이 그 예이다. 불안정 정렬은 그 순서를 보장하지 않는다 퀵 정렬, 힙 정렬, 선택 정렬 퀵 정렬 불안정 정렬 시간 복잡도 평균 시간 복잡도는 O..
-
2024 자료구조개론 & 알고리즘개론 정리 - 3. Queue & StackData Structure & Algorithms 2024. 4. 16. 16:07
2024 자료구조개론 & 알고리즘개론 정리 - 3. Queue & Stack 1. 배열과 링크드리스트 2. Hash Table 3. Queue & Stack 4. Tree & Graph 5. Sorting 6. Recursion 7. 최적화 기법 (DP, Greedy, Divide & Conquer) Queue queue는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out)형식으로 데이터를 저장하는 자료구조 구현 방식 Array-Based queue: enqueue와 dequeue 과정에서 남는 메모리가 생깁니다. 따라서 메모리의 낭비를 줄이기 위해 주로 Circular queue형식으로 구현을 합니다. List-Based: 재할당이나 메모리 낭비의 걱..
-
2024 자료구조개론 & 알고리즘개론 정리 - 2. Hash TableData Structure & Algorithms 2024. 4. 16. 16:05
2024 자료구조개론 & 알고리즘개론 정리 - 2. Hash Table 1. 배열과 링크드리스트 2. Hash Table 3. Queue & Stack 4. Tree & Graph 5. Sorting 6. Recursion 7. 최적화 기법 (DP, Greedy, Divide & Conquer) Direct Address Table (DAT) key:value 쌍에서 key값 그 자체를 index로 넣는 방법 문제점 Key값에 다양한 자료형 넣을 수 없음 (string, ... ) 메모리 낭비 -> key가 1, 20000001, 300001일 때 최소 20000001까지 사용됨 이 문제를 해결하기 위한 Hash Table Hash Function을 이용하여 각 Key값에 index번호 부여 이 Hash..
-
2024 자료구조개론 & 알고리즘개론 정리 - 1. 배열과 링크드리스트Data Structure & Algorithms 2024. 4. 16. 16:05
2024 자료구조개론 & 알고리즘개론 정리 - 1. 배열과 링크드리스트 1. 배열과 링크드리스트 2. Hash Table 3. Queue & Stack 4. Tree & Graph 5. Sorting 6. Recursion 7. 최적화 기법 (DP, Greedy, Divide & Conquer) list은 1) array list과 2) linked list로 나뉘어진다 array list는 다시 1) static array와 2) dynamic list로 나뉘어진다 array list 1) Static array 정의 : 메모리 상에 1) 연속적으로 순차적으로 저장할 수 있으며, 2) 고정된 크기의 저장공간에 저장한다 위의 특징 때문에 3) Random Access (=Direct Access)가 가능..
-
[Algorithms/python] 정렬 알고리즘 총정리 (quick sort, merge sort, )Data Structure & Algorithms 2024. 4. 3. 12:37
정렬 알고리즘최선 시간 복잡도평균 시간 복잡도최악 시간 복잡도공간 복잡도안정성비고 버블 정렬 O(n) O(n^2) O(n^2) O(1) 안정 비효율적인 경우가 많음 선택 정렬 O(n^2) O(n^2) O(n^2) O(1) 불안정 간단하지만 비효율적 삽입 정렬 O(n) O(n^2) O(n^2) O(1) 안정 작은 데이터 세트에서 효율적 합병 정렬 O(n log n) O(n log n) O(n log n) O(n) 안정 대규모 데이터에 효율적 퀵 정렬 O(n log n) O(n log n) O(n^2) O(log n) 불안정 대부분의 경우 가장 빠름 힙 정렬 O(n log n) O(n log n) O(n log n) O(1) 불안정 메모리 사용량이 적음 계수 정렬 - O(n + k) O(n + k) O(k)..