세상은 내가 정하는 대로 세상은 내가 정하는 대로

정렬 알고리즘최선 시간 복잡도평균 시간 복잡도최악 시간 복잡도공간 복잡도안정성비고 버블 정렬 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)..

[Algorithms/python] 위상 정렬(Topological Sort) DAG : Directed Acyclic Graph 사이클이 없는 방향 그래프 → 일의 선후 관계 등을 표현할 때 사용하기 용이함 Topological Sort란 DAG에서 그래프의 방향성을 거스르지 않고 정점을 나열하는 정렬방법 Topological Sort의 방법 : 시간복잡도 : O(V+E) 그래프 그리기, 진입 차수 세기 가장 먼저 진입차수가 0인 노드들 queue에 넣기 queue를 돌며 해당 노드와 연결되어 있는 다른 노드들의 진입 차수를 하나씩 낮춰주고, 이 진입 차수가 0이 되었다면 또 queue에 삽입 Directed Acyclic Graph (DAG) : 순환(Cycle)을 가지지 않는 "방향" 그래프 위상 ..

[Data Structure/python] Hash Table (DAT, Collision, Open Addressing, Seperate Chaining) Direct Address Table (DAT) key:value 쌍에서 key값 그 자체를 index로 넣는 방법 문제점 Key값에 다양한 자료형 넣을 수 없음 (string, ... ) 메모리 낭비 -> key가 1, 20000001, 300001일 때 최소 20000001까지 사용됨 이 문제를 해결하기 위한 Hash Table Hash Function을 이용하여 각 Key값에 index번호 부여 이 Hash Function을 어떻게 정의하느냐에 따라 효율성 달라짐 좋은 Hash Function의 기준 연산 속도가 빨라야 하며, 충돌(Collis..