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

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)가 가능..

정렬 알고리즘최선 시간 복잡도평균 시간 복잡도최악 시간 복잡도공간 복잡도안정성비고 버블 정렬 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] Union Find (Disjoint Set, 서로소 집합) Union Find (Disjoint Set, 서로소 집합) Union Find : 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘 (서로소 집합을 찾아내는 알고리즘) 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어짐 코테 활용 Union Find를 활용하여 양방향 그래프에서 cycle 여부를 판단할 수 있다. 각 간선의 두 노드의 루트 노드를 확인한다. 루트노드가 서로 다르면 union 연산 실행 루트노드가 서로 같으면 cycle 발생한 것 1. 개념 및 기본 원리 1) init 연산 arr = [i for i in range(N+1)] 2) Union 연산 def unio..

[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)을 가지지 않는 "방향" 그래프 위상 ..

2024 알고리즘 공부 순서 - 코딩테스트 및 면접 대비 취업 준비를 하다 보니, 알고리즘 공부를 필수로 해야 되는데 공부하는 재미가 쏠쏠해서 공유하고자 한다 아래는 공부한 문제들 기록 남기는 github repo https://github.com/AAISSJ/AlgorithmStudy/tree/main/2024 AlgorithmStudy/2024 at main · AAISSJ/AlgorithmStudy [2022.11 ~] Problem Sloving with algorithms ✍️. Contribute to AAISSJ/AlgorithmStudy development by creating an account on GitHub. github.com 일정 [23.12.01~23.12.31] 코테 기초 ..

당시에는 고통받으면서 공부했는데, 다 피가 되고 살이 되는구나.... ૮ ˃̣̣̥᷄ᴥ˂̣̣̥᷅ ა

[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..