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

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 자료구조개론 & 알고리즘개론 정리 - 4. Tree & Graph 1. 배열과 링크드리스트 2. Hash Table 3. Queue & Stack 4. Tree & Graph 5. Sorting 6. Recursion 7. 최적화 기법 (DP, Greedy, Divide & Conquer)

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 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. 배열과 링크드리스트 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)을 가지지 않는 "방향" 그래프 위상 ..