파이썬 알고리즘-22~31(탐색, 그리디) 배운 것 정리

(이진탐색)

22. 이진탐색

• 이진탐색은 반드시 정렬된 상태에서 사용하며, 원하는 값이 중간값보다 큰지 작은지 확인해서 중간값이 크면 mid=lt, 중간값이 작으면 mid=rt로 조정한다. lt>rt가 될 때까지 반복

23. 랜선 자르기

• 이진탐색을 사용하는 조건은, 문제의 답이 주어진 숫자들의 범위 안에 있다는 것이다.

24. 뮤직비디오

• 반복문에서 숫자들을 더하면서 일정 범위를 넘지 않게 하는 방법: if sum+x>범위이면 cnt+=1, sum=x로 초기화

25. 마구간 정하기

• 리스트 요소 사이의 거리를 구해서 기준치보다 클 때만 cnt+1하는 법: 시작 값을 변수에 저장하고, 반복문 안에서 원소값-시작값이 기준치보다 크거나 같으면 cnt+1, 시작 값을 바꿔준다.

(그리디)

26. 회의실 배정

• 그리디 알고리즘 적용: 정렬 방법을 제대로 해야 문제가 풀린다. 최대한 많은 회의를 넣으려면 끝나는 시간이 가장 빠른 순으로 정렬.
• 람다 표현식 in sort(): key=으로 람다함수를 사용하면 정렬을 정교하게 실행할 수 있다.

27. 씨름 선수

• 모든 지원자를 일 대 일 비교해서 두 조건 중 하나라도 클 때만 합격인 경우, 하나의 조건을 내림차순으로 정렬하면 나머지 하나의 조건만 largest에 넣어서 그 값보다 클 때만 합격시키고, largest를 다시 그 값으로 바꿔준다.

28. 창고 정리

29. 침몰하는 타이타닉

• 큐를 사용해야 하면 deque를 사용하는 것이 좋다.
• 두 개를 더했을 때 일정 범위 안에서 가장 크게 만드는 법은 양 끝을 더하는 것.

30. 증가수열 만들기

• 증가수열을 만드는 법은 양 끝의 숫자가 마지막 숫자보다 크거나 하나만 크다면 큰 숫자들을 tmp에 넣어서 정렬한 후 그 중 작은 숫자를 먼저 추출한다. 이 과정을 반복해서 tmp에 아무것도 없을 때(= 마지막 숫자보다 큰 숫자가 더이상 없음) 반복을 끝낸다.

31. 역수열

• 역수열이 주어졌을 때 원래 수열을 찾는 방법은 역수열을 내림차순으로 정렬 후 처음부터(큰 수부터) 그 숫자보다 큰 숫자의 개수를 인덱스로 생각하여 그 위치에 insert한다. 큰 숫자부터 집어넣으므로 자기보다 큰 숫자의 개수가 같아도 작은 숫자가 앞으로 오게 된다.