Computer Science/Data structure & Algorithm
오랜만에 자료구조 내용이다. 우선순위 큐를 하기 전에 다양한 자료구조들에 대해 간략하게 짚고 넘어가자 Stack First In Last Out 방식이다. 가장 먼저 들어간 데이터가 가장 나중에 나온다. Queue First In First Out 방식으로 큐와는 반대로 가장 먼저 들어간 데이터가 가장 먼저 나온다. Deque stack 과 queue의 중간 성질을 가진다. 양방향으로 input, output이 가능하다. Priority Queue Priority Queue(우선순위 큐)는 '가장 우선순위가 높은 원소'를 먼저 나오게 하는 자료구조이다. 이때, 우선순위는 Total Order를 지키는 어떠한 키로도 설정할 수 있다. 가장 기본적으로 가장 작은 값을 출력하는 min priority queu..
https://www.toptal.com/developers/sorting-algorithms Sorting Algorithms Animations Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions. www.toptal.com 위 사이트는 여러 정렬 기법의 속도를 비교할 수 있는 곳이다. 교수님께서 소개해주셨는데 여러 케이스를 한 눈에 볼 수 있어 매우 유용하다. Quick Sort 기본 개념 정렬할 원소 중 하나를 기준값 v로 정한 후 =인 원소를 v의 오른쪽에 두는 분할을 반복 적용하는 정렬 방법이다. merge sort와 함께 정렬에서 가장 많이 쓰이는 방법이다. merge sort에 대해..
세상에는 다양한 정렬 기법이 있다. 이 중 가장 많이 사용되는 것은 Quick Sort와 Merge Sort이다. 오늘은 이 중 Merge Sort에 대해 정리해보겠다. Merge Sort(병합정렬) 기본 개념 Merge Sort는 두 정렬된 배열을 ~N시간에 하나의 배열에 정렬된 상태로 병합할 수 있다는 사실에 기반한 방법이다. 병합정렬은 정렬한 결과를 다른 배열에 담아야하기 때문에 ~N 만큼의 추가 공간이 필요하다는 단점이 있다. 위와 같이 주어진 배열을 하나짜리 배열로 나눈 뒤 순서대로 병합해 나간다. 시간복잡도 N개 값을 Merge해야하기 때문에 N에 비례한 비교를 진행한다. 그리고 이 과정을 log2(N)회 반복하기 때문에 (반으로 잘라 나가기 때문에) ~Nlog2(N) 의 시간복잡도를 가진다...
Shuffle Sort 에 대해 알아볼 것이다. 이름에 Sort가 들어가서 단순히 '정렬'문제인가 착각할 수 있는데 정렬을 이용하여 uniformly random한 값을 얻는 방법을 의미한다. Shuffle Sort Shuffle의 개념 셔플은 말 그대로 섞는 것이다. 입력 데이터의 순서를 임의로 섞어야 한다. N = [1,2,3] 이 주어졌으면, 나올 수 있는 순서는 어떤 것이 있을까? => [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]로 총 6가지이다. 일반적으로 N개의 데이터를 입력 받으면 N! 개의 경우의 수가 발생한다. 그리고 이 중 하나를 얻을 확률은 1/N!이다. 가장 쉽게 Shuffle하여 uniformly random한 결과를 얻는 방법은 ..
정렬이란, 임의의 순서가 있는 데이터가 무작위로 주어졌을 때 이를 순서대로 나열하는 것을 의미한다. 정렬 방식은 여러가지가 있으며 오늘은 그 중 Shell Sort에 대해 알아보자. Insertion Sort 기본 개념 Shell sort를 알기 위해서는 Insertion Sort부터 알아야한다. Insertion Sort 는 이미 정렬된 상태에 새로운 데이터의 위치를 찾아 넣는 방식이다. 위 이미지에서 파란 부분이 이미 정렬된 부분, 붉은 부분이 새로 넣고자 하는 원소이다. 붉은 원소를 파란 부분의 어느 위치에 넣을 것인지 찾아 '삽입'하는 형태로 정렬을 진행하기 때문에 '삽입 정렬'이라고 부른다. 코드 # input : 정렬되지 않은 list # output : 정렬된 list def insertio..
Union Find 문제 상황 N개의 정점 ( 0 ~ V-1 ) 이 주어졌을 때 두 정점 a, b ( 0 ids[3] = 0 -> ids[0] = 0 == 0 (root = 0) 즉, 두 개의 root가 0으로 같으니 connected의 결과는 True이다. 핵심 알고리즘 1. 자료구조 정의 및 초기화 connected component를 tree 형태로 봄 ids[i] : 객체 i 의 parent ids[i] == i 이면 root root(i) = ids[ids[ ... ids[i] ...]] 2. union(a, b) root(a)를 root(b) 아래로 붙이기 3. connected(a, b) root(a) == root(b) : True else False 코드 # Quick Union V = ..
그리디 알고리즘에 해당하는 Scheduling 문제들에 대해 정리해보았다. Job Scheduling 문제는 크게 3가지 유형이 있다. Interval Scheduling Interval Partitioning Scheduling to Minimize Lateness Interval Scheduling 시작시간과 종료시간이 존재하는 job이 여러 개 있을 때 시간이 겹치는 job은 overlab될 수 없다. 이 때 최대로 실행할 수 있는 job subset을 구하는 문제이다. 이 문제에 대해서는 Greedy 알고리즘을 소개하면서 '활동 선택 문제' 라고 해서 설명한 적이 있다. 그렇기 때문에 아래 글을 참고하길 바란다. 2023.06.08 - [Computer Science/Data structure &..
2023.06.13 - [Computer Science/Data structure & Algorithm] - [Algorithm] Minimum Spanning Tree - Kruskals [Algorithm] Minimum Spanning Tree - Kruskals Spanning Tree Spanning Tree는 어떤 그래프의 정점을 모두 포함한 가장 작은 subgraph를 의미한다. spanning tree를 찾는 가장 쉬운 방법은 DFS와 BFS를 이용하는 것이다. 2023.06.13 - [Computer Science/Data structure & Algo mobuk.tistory.com 위 글과 이어진 글이다. 먄약 MST가 무엇인지 궁금해서 들어왔다면 위 글을 참고하시길 바란다. Prim..
Spanning Tree Spanning Tree는 어떤 그래프의 정점을 모두 포함한 가장 작은 subgraph를 의미한다. spanning tree를 찾는 가장 쉬운 방법은 DFS와 BFS를 이용하는 것이다. 2023.06.13 - [Computer Science/Data structure & Algorithm] - [Algorithm] BFS, DFS [Algorithm] BFS, DFS 그래프를 탐색하는 대표적인 방식에는 BFS와 DFS가 있다. 그래프 관련 알고리즘, 동적 프로그래밍 등 다양한 알고리즘 과정에서 응용된 형태로 많이 사용하기 때문에 알고리즘 공부를 할 때에는 mobuk.tistory.com Minimum Spanning tree 모든 정점 사이의 비용 (weight) 이 있다고 해보..
Connected Components 적어도 한 개 이상의 경로로 연결된 정점들로 구성된 종속 그래프이다. connected components는 단순히 연결되었는지 아닌지만 판단하면 되기 때문에 BFS나 DFS로 찾을 수 있다. ( Search가 가능하면 연결된거니까) 2023.06.13 - [Computer Science/Data structure & Algorithm] - [Algorithm] BFS, DFS [Algorithm] BFS, DFS 그래프를 탐색하는 대표적인 방식에는 BFS와 DFS가 있다. 그래프 관련 알고리즘, 동적 프로그래밍 등 다양한 알고리즘 과정에서 응용된 형태로 많이 사용하기 때문에 알고리즘 공부를 할 때에는 mobuk.tistory.com Strongly Connected..
