Algorithm17 PriorityQueue (우선순위 큐) Priority Queue (우선순위 큐)는 말 그대로 사용자가 지정한 조건에 따라 우선순위가 정해집니다. 일반적인 Queue는 단지 데이터가 들어오는 순서에 따라 FIFO(First In First Out) 구조를 따르게 되는데, Priority Queue는 우선순위가 높은 데이터부터 pop됩니다. PriorityQueue는 우선순위에 따라 Heap(힙) 자료구조로 데이터를 저장하게 되기 때문에 삽입과 삭제의 시간복잡도는 O(log n)으로 매우 빠른 시간을 자랑합니다. 제가 이 Priority Queue (우선순위 큐)를 Swift로 직접 구현하기 위해 이전 게시물에서 Heap(힙) 자료구조를 공부했었습니다!! Queue도.. Stack도.. PriorityQueue도 없는 Swift는... 사용하려.. 2021. 2. 19. Insertion Sort (삽입 정렬) Insertion Sort (삽입 정렬)은 이름 그대로 적절한 위치에 삽입을 하여 정렬을 하는 알고리즘입니다. 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 하나씩 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성합니다. 요소를 하나씩 비교해나가기 때문에 시간 복잡도는 O(n^2)를 가집니다. 알고리즘 구현 순서는 다음과 같습니다. 비교는 배열의 두 번째 인덱스부터 시작하여 자신의 앞쪽에 있는 요소들과 비교합니다. 비교했을 때, 앞의 요소가 자신보다 크다면 swap 합니다. 비교했을 때, 앞의 요소가 자신보다 작다면 비교를 멈춥니다. 다음 인덱스의 요소부터 다시 2~4를 반복합니다. 아래는 Swift로 구현한 Insertion Sort 입니다. var arr: [Int] = [5,2,4,1.. 2021. 2. 15. Quick Sort (퀵 소트) Quick Sort는 전형적인 분할 정복(divide and conquer) 알고리즘의 하나입니다. 이름만큼 평균적으로 매우 빠른 수행 속도를 자랑하며 시간복잡도 O(n log n)을 가지고, 추가 메모리 공간을 필요로 하지 않기 때문에 O(log n)만큼의 메모리를 필요로 합니다. Merge Sort와 달리 Quick Sort는 비균등 분할을 합니다. 리스트 안에 있는 한 요소를 선택하는데, 이때 이 원소를 pivot이라 합니다. 입력 배열을 pivot을 기준으로 비균등하게 2개의 부분 배열로 분할합니다. 이 때, pivot의 왼쪽은 pivot보다 작은 요소들로, pivot의 오른쪽은 pivot보다 큰 요소로 이루어지게 됩니다. (divide) 이렇게 분할한 부분 배열을 정렬합니다. 부분 배열의 크기가.. 2021. 2. 12. Merge Sort (병합 정렬) Merge Sort는 전형적인 분할 정복(divide and conquer) 알고리즘의 하나입니다. 시간복잡도 O(n^2)을 가지는 일반적인 정렬과 달리 Merge Sort의 시간 복잡도는 O(nlog_2 n) 이 됩니다. 이등분씩 나누는 것을 반복해서 최소 단위까지 분할합니다. (divide) 분할한 부분 리스트를 정렬합니다. (conquer) 정렬된 부분 리스트들을 하나의 리스트에 병합합니다. (combine) 다음은 swift 언어로 구현한 divide, merge 메서드 입니다. func divide(_ start: Int,_ end: Int) { if start >= end { return } let mid = (start + end) / 2 divide(start, mid) divide(mid.. 2021. 2. 11. 2020 삼성SDS 대학생 알고리즘 특강 후기 2020년 7월 중순에 우연히 삼성SDS 대학생 알고리즘 특강 모집 공고를 보게되어 지원했습니다. 몰랐는데 매년 하계 동계 시즌마다 계속 진행해왔던 프로그램인 것 같았고, 이전 후기들을 찾아보니 원래는 지원 할 때 코딩테스트까지 보고 한정된 인원이 선발되어 오프라인으로 진행되던 특강이었습니다. 하지만 이번 알고리즘 특강은 온라인으로 진행되어 그런지 매우 많은 인원이 선정되었습니다. 2주동안 특강을 듣고 나면 프로 시험을 본다고 했는데 후기를 보니 난이도는 삼성SW B형과 비슷하다고 했고, 4시간 동안 1문제를 푸는 시험이라고 한다. 그리고 이 프로 시험은 원래 임직원 대상 시험이라 일반인은 응시하지 못하는 시험이지만, 이 특강 수료 조건에 프로 시험 응시하는 게 있어서 꼭 시험에 응시해야 수료를 할 수 .. 2020. 8. 20. 이전 1 2 다음
