📖저자님의 책 소개 영상: https://www.youtube.com/watch?v=Q13Uj_5bH9M

🗓️TIL (this week I learned)
월 읽기, 정리
화 정리 - 더 해야 함
토 몸풀기 문제 + ⭐별 한 개 문제
일 여행준비 ㅠㅠㅠㅠ

13-1 정렬 개념 ⭐⭐

정렬이 필요한 이유:

알고리즘의 효율을 크게 높여줌

1. 삽입 정렬(insertion sort)

출처: 삽입정렬 wiki(en)

• 데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역을 나누고,
  정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬함.
• key: 정렬되지 않은 영역의 맨 앞에 있는 값
• 시간복잡도: 최악의 경우 $O(N^2)$, 이미 정렬이 되어 있는 최선의 경우 $O(N)$

2. 병합정렬(merge sort, divide and conquer)

출처: 병합정렬 wiki(en)

• 정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬
• 포인터: 특정 배열의 원소를 가리키기 위한 화살표와 같은 것
• 시간 복잡도: $O(NlogN)$ = 나누는 횟수 $logN$ + 합치는 횟수 $NlogN$($N$개 병합을 $NlogN$번) ➡️ $(N+1)logN$ ➡️ $NlogN$
  - $N$개의 인자를 가진 배열을 2로 h번 나누면 1개의 인자를 가진 배열이 된다.
  • 1(칸) = $N$ * $(1/2)^h$
  • $N$ = $2^h$
  • h = $log_2N$

3. 힙 정렬(heap sort)

출처: wiki(ko)

• 힙: 특정 규칙이 있는 이진 트리.
• 최대힙: 부모 노드가 자식 노드보다 크다.
• 최소힙: 부모 노드가 자식 노드보다 작다.
• 시간복잡도: $O(NlogN)$

4. 우선순위 큐(priority queue)

• 우선순위 큐는 힙으로 구현하는 것이 가장 좋다.
• 그 이유: 최소힙이나 최대힙이 특정 값을 루트 노드에 유지하는 특징이 있고, 우선 순위 큐의 핵심 동작(우선 순위가 높은 데이터부터 먼저 처리하는)과 맞아 떨어져서)
• 파이썬 모듈: heapq

5. 위상정렬

6. 계수 정렬

13-2 문제

1. 문자열 내 마음대로 정렬하기

https://school.programmers.co.kr/learn/courses/30/lessons/12915

2. 정수 내림차순으로 배치하기

https://school.programmers.co.kr/learn/courses/30/lessons/12933

3. K번째 수

https://school.programmers.co.kr/learn/courses/30/lessons/42748

4. 가장 큰 수

https://school.programmers.co.kr/learn/courses/30/lessons/42746

5. 튜플

https://school.programmers.co.kr/learn/courses/30/lessons/64065

6. 지형 이동(어려움)

https://school.programmers.co.kr/learn/courses/30/lessons/62050

14-1 시뮬레이션 ⭐⭐

노하우

1. 푸는 방법
   • 하나의 문제를 최대한 여러 개로 분리
   • 예외 처리가 필요하다면 독립 함수로 구현(구현할 게 너무 많다)
2. 행렬 연산
   • 굉장히 많이 사용함
3. 좌표 연산
   • 2차원 좌표 사용
4. 대칭, 회전 연산
   • 그림 참조

14-2 문제

1. 이진 변환

https://school.programmers.co.kr/learn/courses/30/lessons/70129

2. 롤케이크 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/132265

3. 카펫

https://school.programmers.co.kr/learn/courses/30/lessons/42842

4. 점프와 순간 이동

https://school.programmers.co.kr/learn/courses/30/lessons/12980

5. 캐릭터 좌표

https://school.programmers.co.kr/learn/courses/30/lessons/120861