공부 기록

✏️ 문제 문제 파악처음에는 a 배열을 기준으로 이분 탐색을 하려했는데 생각해보니 a 배열의 각 요소가 b 배열의 요소보다 큰 지 안 큰 지에 대해서 정답을 구하는 것이므로 b 배열을 기준으로 이분 탐색을 하는 것이 맞다!이분 탐색을 하기 위해선 배열이 정렬되어 있어야한다. 위의 예시를 보면 쌍의 개수는 b 배열의 인덱스+1 한 값과 같다는 걸 알 수 있다.while ... if b[mid]  또한 큰 쌍의 개수를 구하므로 end + 1을 해주어야 한다. 알고리즘두 포인터정렬이분 탐색  코드for _ in range(int(input())): n,m = map(int, input().split()) a = sorted(list(map(int, input().split()))) b = sorted..

✏️ 문제 문제 파악이분 탐색을 사용해야 하는 거의 대표적인 문제!!!!!이분 탐색을 안 사용하면 보통.. 아니 대개 "시간 초과" 가 뜬다... ^^ 알고리즘이분 탐색매개 변수 탐색 코드n, m = map(int, input().split()) trees = list(map(int, input().split())) def binary_search(trees, target): left, right = 0, max(trees) while left mid: total += h - mid if total     ⭐️ 이분 / 이진 탐색에 대해 잘 모른다면?2024.07.25 - [알고리즘] - [알고리즘] 이분 / 이진 탐색 (Binary Search) 알고리즘

이분 / 이진 탐색 (Binary Search) ?정렬된 리스트에서 특정 값을 찾는 데 사용되는 효율적인 알고리즘이다. 리스트의 중앙값과 목표 값을 비교하여 목표 값이 중앙값보다 작으면 리스트의 왼쪽 절반을 탐색하고 크면 리스트의 오른쪽 절반을 탐색하는 방식으로 진행된다. 이렇게 계속해서 리스트를 반씩 줄여 나가면서 값을 찾는다.  이분 / 이진 탐색 알고리즘의 단계초기화: 리스트의 처음과 끝 인덱스 설정반복 또는 재귀: 중앙값을 계산하고 이 값을 목표 값과 비교값 비교:목표 값 = 중앙값 → 해당 인덱스 반환목표 값 목표 값이 > 중앙값 → 리스트의 오른쪽 절반 탐색반복 종료: 리스트의 탐색 범위가 0이 되면 목표 값이 리스트에 없는 것으로 간주하고 탐색 종료 이분 / 이진 탐색 알고리즘의 시간 복잡도..