[TIL/크래프톤 정글] Day 8

---

🖐️[크래프톤 정글] TIL - 240909

아직 시간 분배에 미숙함을 느낀다. TIL에 올리고 있는 내용들은 Notion에서 공부한 내용들이나 당일에 필기한 것들을 간단하게 적은 것들에 불과한데, 막상 핵심적으로 파고드는 부분들을 작성하기에 시간이 부족하다고 느낀다. 예를 들어서 하노이의 탑, N-Queen, Quick Sort, Merge Sort, 등과 같은 내용들을 배워도 제대로 정리를 못하고 있다.

 

확실히 시간을 가져다 버리는 느낌이 없잖아 있다. 블로그에 올리는 TIL을 보여주기식이 아니라 제대로 내가 공부한 내용을 복습할 수 있는 글로 만들어야 겠다.

 

오늘은 오전에 코치님의 Git 강의가 있었고 이후, 오후에 2회차 알고리즘 스터디 진행 및 CS 스터디 진행 방식에 대해서 이야기를 나눴다. 그리고는 계속 알고리즘 책을 보면서 시간을 때웠다. 또 앞선 내용을 다시 작성하는 것 같지만, 내일은 시간을 최대한 아껴서 할 내용들을 할 수 있도록 일정들을 작성해야겠다.

 

...^^ 오늘은 급하게 나가야 할 것 같아서 TIL 정리는 하지 않는다.

---

코치님이 말하는 좋은 공부법이란?

다른 *아직 의견 정리 안함

• 사람마다 라이프사이클이 다르다.
• 만나서 이야기하는 시간을 오전으로 잡도록 노력해봐라
• 만약에 저녁으로 한다면, 아침형 사람들도 13~14시 출근으로 변경된다.
• 사람이 나태해진다. 그래서 아침으로 잡으면 좋아질 것 같다

서론

• 정글은 이렇게 생각하면 좋을 것 같다.
  • 헬스장에 운동을 하러가서 PT를 받으면, PT 쌤들은 (무게를) 같이 들어주지 않는다. 다만, 임계치를 넘어설 수 있도록 도와준다.
  • 정글도 마찬가지다. 본인들의 한계치가 100이라면, 매주마다 한계치의 10%를 증가시켜봐라. 그렇게 20주를 진행하면 한계치가 계속 늘어날 것이다.
    • 그러면 한계치를 넘긴다는 것은 무엇을 의미하는가? 물론 사람마다 주관적인 의견을 나타낼 수 있겠다만….

본론

• (근데 무슨 요일마다 뭐 한다했는데..;;;) 목요일마다 Code Review 진행 → Github에 Commit.
• 그래서 Git 연습을 진행해볼 예정이다.
  • Git을 자주 다뤄보지 않은 분들도 있기 때문에 이야기를 진행한다.
• Jungle Repo에서 코딩 테스트 문제를 풀 것이다. 1시간 30분동안 풀 예정이고 3 SOL을 진행한다.
  • Repo에 내 이름의 폴더를 생성하고 Git에 제출을 하는 것이다.
  • 이번주에는 Merge를 진행하지 않는다.

팁

• 코드에 주석을 작성해서 리뷰어가 읽기 편하게 만들자.

---

서적

Chapter 6. 정렬 알고리즘

06-1 정렬 알고리즘

• 정렬이란?
  • 데이터 집합을 일정한 순서로 변경하는 작업.
  • 작은 데이터를 앞에, 뒤로 갈수록 큰 데이터를 나오게 하는 것은 오름차순(Ascending)
  • 큰 데이터를 앞에, 뒤로 갈수록 작은 데이터를 나오게 하는 것을 내림차순(Descending)
• 정렬 알고리즘은 2 종류로 나눌 수 있다
  • 안정적인(Stable) 알고리즘
    • 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것을 의미한다.
  • 안정적이지 않은 알고리즘
    • 정렬 후에 원래의 순서가 유지된다는 보장을 할 수 없다.
• 내부 정렬과 외부 정렬
  • 최대 30장의 카드를 둘 수 있는 책상에서 정렬하는 것을 가정한다. 30장 이하라면 모든 카드를 책상 위에 늘어놓고 작업을 수행할 수 있다. 만약, 카드가 500장이라면? 더 큰 책상을 필요로 하게 된다.
  • 하나의 배열에서 작업할 수 있는 경우 내부 정렬 사용
  • 하나의 배열에서 작업할 수 없는 경우 외부 정렬 사용

<aside> 💡

정렬 알고리즘의 핵심은 교환, 선택, 삽입이다.

정렬 알고리즘은 데이터를 교환, 선택, 삽입하면서 정렬한다. 대부분의 정렬 알고리즘은 이 3가지 개념을 응용하고 있다.

</aside>

06-2 버블 정렬(Bubble Sort)

1. 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘
2. 단순 교환 정렬이라고도 한다.

• 코드
• from typing import MutableSequence def bubble_sort(a: MutableSequence) -> None: n = len(a) for i in range(n - 1): for j in range(n - 1, i, -1): if a[j - 1] > a[j]: a[j - 1], a[j] = a[j], a[j - 1] if __name__ == '__main__': num = int(input()) x = [None] * num for i in range(num): x[i] = int(input(f'x[{i}] : ')) bubble_sort(x) for i in range(num): print(f'x[{i}] = {x[i]}')

06-6 퀵 정렬

가장 빠른 정렬 알고리즘으로 알려져 있으며 널리 사용된다. 참고로 퀵 정렬은 서로 이웃하지 않는 원소를 교환하기 때문에 불안전 알고리즘에 속하게 된다.

• 개념
  1. 키가 168cm인 학생 A를 선택하고 학생들을 2 그룹으로 나눈다. 이때, 그룹을 나누는 기준을 피벗(Pivot)이라고 한다.
     • 168cm 이상의 키를 가진 학생 그룹
     • 168cm 미만의 키를 가진 학생 그룹
  2. 이제 나눠진 그룹에서 1번과 동일하게 피벗을 찾고 두 그룹으로 나누는 것을 반복한다.
     • 해당 행동은 나눠진 그룹에 원소가 하나 남았을 때 종료된다.
• 퀵 정렬 알고리즘을 사용해서 학생 그룹을 키 순서로 정렬하는 과정
• 다른 예제를 통한 퀵 정렬 소개피벗(Pivot) : 6오른쪽 끝 원소 Index : pr
  1. 그룹을 나누기 위해서 피벗 이하인 원소를 배열 왼쪽(맨 앞쪽)으로, 이상인 원소를 배열 오른쪽(맨 뒤쪽)으로 이동시켜야 한다.
  2. a[pl] ≥ x가 성립하는 원소를 찾을 때 까지 pl을 오른쪽 방향 스캔 a[pr] ≤ x가 성립하는 원소를 찾을 때 까지 pr를 왼쪽 방향 스캔
• 왼쪽 끝 원소 Index : pl
• 배열 A가 있으며 내부적으로는 [5, 7, 1, 4, 6, 2, 3, 9, 8]와 같이 이루어져 있는 상태.
• 그룹 나누기 코드
  • 위 코드는 Pivot을 가운데에 있는 원소로 선택함
    • 선택하는 Pivot에 의해서 정렬 알고리즘 성능에 영향을 미침
• from typing import MutableSequence def partition(a: MutableSequence) -> None: n = len(a) pl = 0 pr = n -1 x = a[n // 2] while pl <= pr: while a[pl] < x: pl += 1 while a[pr] > x: pr -= 1 if pl <= pr: a[pl], a[pr] = a[pr], a[pl] pl += 1 pr -= 1 print(f'Pivot : {x}') print(*a[0 : pl]) if pl > pr + 1: print(*a[pr + 1 : pl]) print(*a[pr+1:n]) if __name__ == '__main__': num = int(input()) x = [None] * num for i in range(num): x[i] = int(input(f'x[{i}]')) partition(x)
• 퀵 정렬 만들기
  • 위 ‘그룹 나누기’ 코드를 수정해서 퀵 정렬 알고리즘을 만들 수 있다.
  • 원소 수가 1개인 그룹이 나타날 때 까지 그룹을 나눈다.
    • pr이 a[0]보다 오른쪽에 위치하면 left < pr 왼쪽 그룹
    • pl이 a[8]보다 왼쪽에 위치하면 pl < right 오른쪽 그룹
• 퀵 정렬 코드 (재귀)
  • Main에 위치한 quick_sort 함수를 통해서 본문의 일관성을 유지할 수 있다.
• from typing import MutableSequence def qsort(a: MutableSequence, left: int, right: int) -> None: pl = left pr = right x = a[(left + right) // 2] while pl <= pr: while a[pl] < x: pl += 1 while a[pr] > x: pr -= 1 if pl <= pr: a[pl], a[pr] = a[pr], a[pl] pl += 1 pr -= 1 if left < pr : qsort(a, left, pr) if pl < right: qsort(a, pl, right) def quick_sort(a: MutableSequence) -> None: qsort(a, 0, len(a) - 1) if __name__ == '__main__': num = int(input()) x = [None] * num for i in range(num): x[i] = int(input(f'x[{i}]')) quick_sort(x) for i in range(num) : print(f'x[{i}] = {x[i]}')

병합 정렬(Merge Sort)

배열의 앞과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘

• 병합에 필요한 시간 : $O(n)$