2023_7_4_TIL

上男子 되는 길

上男子 TIL

이진탐색을 다시 복습하면서 알게 된 것들을 살짝 정리? 하려고한다.

1. 먼저 정렬된 배열에서 특정 수의 개수 구하기문제

• 나는 이 문제를 접근할 때 while 반복문으로 접근하려고 했다. 왜냐하면 반복문으로 접근하는 것이 함수를 여러번 호출하는 것보다 2배 빠르기 떄문이다.(물론 큰차이는 없다.)

• 따라서 While 문으로 접근하는 이진탐색 공식으로 사용하려고 했는데 제한을 주는 부분에서 계속 걸렸다.
  고민고민 하다가 풀이방법을 봤는데 이 문제의 경우
  a. 재귀호출로 푸는 방법이 훨씬 효율적이다.
  b. 그리고 모든 부분은 구현했지만, 가장 구현하기 어려웠던 부분은 왼쪽에 위치하는 or 가장 오른쪽에 위치하는 이 부분이다.
  c. 그냥 푸는 방법 자체를 기억하는 과정이 가장 좋을 것 같다.

• 확실히 지금 그리디, 정렬, 이진탐색, 구현 부분을 최소 6번씩 풀어본 결과, 과정이 머리속에 그려진다.

• 문제 푸는 과정과 어떤 경우에 어떤 방식으로 문제를 풀어야하는지 외우자!

결론: 개수 자체를 Counting 하는 알고리즘 문제의 경우 recursion 함수 이진탐색을 사용하자.

def leftBinarySearch(data, target, start, end):
     if start > end: # 끝까지 했는데 안나온 경우
          return None
     
     mid = (start + end) // 2
     if (mid == 0 or data[mid - 1] < target) and data[mid] == target: # 가장 왼쪽에 해당하는 것만 찾기
          return mid
     elif data[mid] >= target:
          return leftBinarySearch(data, target, start, mid -1)
     else:
          return leftBinarySearch(data, target, mid + 1, end)

def rightBinarySearch(data, target, start, end):
     if start > end: # 끝까지 했는데 안나온 경우
          return None
     
     mid = (start + end) // 2
     if (mid == N - 1 or target < data[mid + 1]) and data[mid] == target: # 가장 오른쪽에 해당하는 것만 찾기
          return mid
     elif data[mid] > target:
          return rightBinarySearch(data, target, start, mid -1)
     else:
          return rightBinarySearch(data, target, mid + 1, end)

上男子

上男子 스케줄

上男子 스케줄

상남자 스케줄

上男子 노션

상남자의 공부 노션