[알고리듬] 3주차: Homework#1

1. 반복문을 사용하지 않고 재귀로만 다음을 구현한 후 시간 복잡도 분석하기

- 배열에서 최솟값 찾기

- 배열의 모든 원소의 총합 구하기

- 선택 정렬

https://t0pli.tistory.com/199

 

2. Pancake Sorting(Jeff Erickson의 책 <Alogirithms>의 Exercise 9(a),(b) in Chapter 1 of [E])

(a): 팬케이크가 $n$장일 때 $O(n)$번 뒤집는 알고리즘을 구하면 됨

(b): 모든 양의 정수 $n$에 대해 정렬을 위해 $O(n)$ filps가 필요한 배열 구성을 구하면 됨

https://t0pli.tistory.com/200

 

(a)는 그냥 내가 짠 코드를 설명하면 끝이었다.

(b)는 생각이 좀 필요했다. 내가 제시한 답은 내림차순으로 정렬된 배열이다.

내림차순으로 정렬된 배열은 맨 처음에 한 번 flip하고 나면 flip 연산이 수행되지 않는다. 그래서 원래는 $O(n^2)$인데

$O(n)$ 됨

 

(c)는 옵션이라길래 풀까 말까 하다가 결국 안 풀었다. 옵션까지 풀기엔 몸도 마음도 지쳐 있었다.....