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

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

2024 상반기 삼성 SDS 알고리즘 특강 - 입과, 후기 입과 안내 메일: 2024.02.02 연구실에서 Baseline 실험 돌리고 있었던 때에, 우연한 기회로 접하게 된 "삼성 SDS 알고리즘 특강"에 입과하게 되었다는 메일을 받게 되었다! C/C++/JAVA로만 진행한다는 소식에 들을까 말까 ... 고민 많이 했다. 사실 알고리즘 강의를 혼자서 들으면서 백준 조금씩 풀고 있던 와중이었기에 (완전 쪼렙, 실버 3이었나) 단기간에 실력이 많이 늘 수 있다는 후기들을 보고, 일단 밑져도 본전!이라는 생각이 들어서 듣기로 했다. 예상치도 못하게 연구실에서 하던 잔업들을 정리하게 되었다 😢 시원섭섭함 특강 이수 전: ~ 2024.02.12 기존에 듣던 강의에서 그래도 기본적인 자료구조는 python으로라도..

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

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