Lecture 9-10: Sorting Algorithms
Quiz 3 – Next week (20%)
Sorting
Level : Leetcode easy
1 problem : Similar with our homework
1 problem : New
Similar with Quiz 1
Evaluation: Testcode
(if pass🡪 get the full score, otherwise 🡪 get 0 score)
Homework 1
Q. Can you implement this with selection sort with recursion?
- 재귀(recursion)을 이용하여 선택 정렬(selection sort) 구현하는 문제
- 기존 문제에서는 반복문 사용 -> 재귀적으로 바꾸기
Homework 2
Q. Please implement merge sort. (# TODO section below)
- 주어진 문제는 Merget Sort 알고리즘을 구현하는 것
- 코드는 이미 기본 구조와 재귀 호출을 포함하고 있음 => 우리가 구현해야 할 부분은 두개의 분할된 리스트(left, right)를 병합하여 정렬된 리스트를 만드는 Merge 과정!!
Homework 3 (Leetcode 268: Missing Number)
- 이 문제는 배열 nums에 있는 값을 바탕으로 주어진 범위 [0,n]에서 빠진 숫자를 찾는 것
문제 풀이 방법 1: 합 공식 사용
- 숫자 0부터 n까지의 합을 계산하고, 배열에 있는 숫자의 합을 뺌
- count 정렬: Time complexity O(n), Space complexity O(n)
- 새 인덱스 num[i]-min(num) 내에서 새 배열에 값을 할당: 시간 복잡도 O(n), 공간 복잡도 O(n)
- 총합 비교: 시간 복잡도 O(n), 공간 복잡도 O(1)
Homework 4 (Leetcode 179: Largest Number)
- 정수 배열 nums가 주어졌을 때, 배열의 숫자를 조합하여 가장 큰 수를 만들어 반환하기(반환되는 숫자는 문자열 형식, 조합된 숫자가 0으로 시작하지 않는다고 가정/ 배열이 모두 0으로 이루어진 경우 0을 반환)
문제 풀이 방법 1
- 숫자 비교 기준 : 숫자들을 문자열로 변환한 후, 두 문자열 x와 y를 비교할 때 x+y와 y+x중 더 큰 값이 만들어지면 x가 앞에 오도록!
- ex. 9+34 = 934, 34+9=349여서 9가 34보다 앞에 와야 한다
- Time complexity : O(nlog(n))
Homework 5 (Leetcode 56: Merge Intervals)
- 배열 intervals가 주어지며 각 요소는 [start, end] 형태의 구간에 있음. 이 구간들이 겹치는 경우를 병합하여 겹치지 않는 구간들만 반환하기
문제 풀이 방법 1
- 정렬
- 구간을 시작값 start를 기준으로 오름차순 정렬
- 정렬하면 겹치는지 확인하기 쉬움
- 병합
- 첫 번째 구간을 기준으로 시작해 다음 구간과 비교하며 병합할지 결정함- 만약 현재 구간의 끝 값(end)이 다음 구간의 시작 값(start)보다 크거나 같다면 병합이 가능함
- 결과 저장
- 병합 가능한 구간은 하나로 합치고, 병합이 불가능하면 결과 리스트에 추가함
Lecture 11: PQ(Priority Queue) and Heap
MinHeap Class 정의하기
-
MinHeap : 최소 힙 (부모노드가 항상 자식 노드보다 작은 값을 가지는 완전 이진트리)
- 가장 작은 값(루트노드)를 효율적으로 찾거나 제거할 수 있는 구조!
- O(logn)
-
주요 메서드
- insert(value): 새로운 값을 heap에 추가하고 추가된 값이 적절한 위치로 이동하도록 조정
- heapify_up(index): 삽입된 값이 부모보다 작다면 부모와 값을 교환하며 위로 올라감
- delete_min(): 힙의 루트(최소값)를 제거한 뒤, 마지막 요소를 루트로 이동시키고 힙 속성을 복구
- heapify_down(index): 루트가 자식보다 크다면 자식과 교환하며 아래로 내려가 힙 속성을 유지함
