Data Structure & Algorithms
-
[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)..
-
[Algorithms/python] Union Find (Disjoint Set, 서로소 집합)Data Structure & Algorithms 2024. 4. 2. 20:16
[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)Data Structure & Algorithms 2024. 4. 2. 20:07
[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 알고리즘 공부 순서 - 코딩테스트 및 면접 대비Data Structure & Algorithms 2024. 3. 23. 19:42
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] 코테 기초 ..
-
2024 상반기 삼성 SDS 알고리즘 특강 - 수강 후기Data Structure & Algorithms 2024. 3. 9. 12:53
2024 상반기 삼성 SDS 알고리즘 특강 - 입과, 후기 입과 안내 메일: 2024.02.02 연구실에서 Baseline 실험 돌리고 있었던 때에, 우연한 기회로 접하게 된 "삼성 SDS 알고리즘 특강"에 입과하게 되었다는 메일을 받게 되었다! C/C++/JAVA로만 진행한다는 소식에 들을까 말까 ... 고민 많이 했다. 사실 알고리즘 강의를 혼자서 들으면서 백준 조금씩 풀고 있던 와중이었기에 (완전 쪼렙, 실버 3이었나) 단기간에 실력이 많이 늘 수 있다는 후기들을 보고, 일단 밑져도 본전!이라는 생각이 들어서 듣기로 했다. 예상치도 못하게 연구실에서 하던 잔업들을 정리하게 되었다 😢 시원섭섭함 특강 이수 전: ~ 2024.02.12 기존에 듣던 강의에서 그래도 기본적인 자료구조는 python으로라도..
-
[Algorithms/python] Greedy AlgorithmData Structure & Algorithms 2023. 1. 18. 18:44
자료구조의 선택 각각의 값이 서로 다른 값에 영향을 주지 않을 것 그리디 알고리즘으로 풀어낸 값이 모든 경우의 수에서 최적의 해일 것 주어진 상위의 값이 하위 값의 배수일 것 그리디 알고리즘은 현재 상황을 기준으로 적합한 해를 찾는 방법이지 최적의 해를 찾는 방법은 아니다. 최적의 해를 찾기 위해서는 동적계획법(Dynamic Programming)을 사용한다. Greedy VS DP Greedy 문제 해결 방안 나열된 값의 정렬이 매우 중요하다. 즉, 경우의 수(주어질 지, 내가 만들어야될지는 모르겠지만)를 잘 정렬하여 현재 상황이 원하는 순서대로 나타날 수 있도록 해야한다. 문제의 최적의 부분 문제를 결정한다 Prove that it is always safe to make the greedy choi..
-
[Data Structure/python] Hash Table (DAT, Collision, Open Addressing, Seperate Chaining)Data Structure & Algorithms 2023. 1. 18. 15:19
[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..