크래프톤정글 2주차; TIL 1 - 이진 탐색, 공유기 설치 문제, 함수와 분할정복, 이진 탐색 트리

2022-11-03, 2022-11-04

이진탐색 강의

출처: https://www.edwith.org/knu-algorithm/lecture/170169?isDesc=false

무엇?

binary search.
리스트의 범위를 반씩 줄여나가며 탐색하는 방법.
분할정복 알고리즘 설계법을 이용한 방법 中 하나.

왜?

어떤 값을 탐색하기 위함.
완전탐색보다 시간이 덜 든다 (빅O가 logN)
길이가 80인 리스트를 완전 탐색하면 80번 뒤져야 하지만, 이진 탐색은 log80 (계속 이등분 하기 땜에)

어떻게?

값이 정렬되어 있음을 전제함
low, mid, high 값을 지정하고, mid와 low, high의 값을 비교한 뒤, 오른쪽으로 갈 지 왼쪽으로 갈 지 정함.
그러면서 서서히 리스트의 탐색 범위를 줄여 나가는 것.

백준 공유기 설치 파이썬 참고

https://hongcoding.tistory.com/3

왜?

이분 탐색의 개념을 공부하고 나서, 문제에 적용하기 위해서는
어떤 것을 정렬하고 무엇을 탐색 범위로 잡아야 하는지를 알아야 한다고 생각했다.
공유기 설치 문제는 이걸 생각해내기 어려웠다.

어떻게?

공유기 설치 최소 거리를 탐색 범위로 설정하고 이분 탐색을 해나가야 함.
결론적으로 이분 탐색 함수와 공유기 설치 함수 두 가지를 정의해서 문제 해결

함수의 필요성과 분할정복

https://www.edwith.org/pnu-basicpython/lecture/18889

무엇?

함수는 특정한 기능을 하는 코드의 묶음.

1. 값을 반환하는 함수
2. 값을 반환하지 않는 함수
3. 매개변수가 있는 함수
4. 매개변수가 없는 함수

왜?

함수를 사용하면,

1. 안정성
2. 신뢰성
3. 개발 속도
   면에서 장점이 있음

어떻게?

일정 예약과 이진 탐색 트리

출처:https://www.boostcourse.org/cs113/lecture/540276?isDesc=false

무엇?

이진 탐색 트리의 불변성: 오른쪽의 자식 노드는 항상 부모 노드보다 크고, 왼쪽의 자식 노드는 항상 부모 노드보다 작다

왜?

어떻게?

이진 탐색 트리에서 탐색하고 데이터 삽입하기
'n’보다 작은 값 몇갠지 계산하기