본문 바로가기

이진탐색5

[Java] 알고리즘 이진 탐색 [Java] 알고리즘 이진 탐색 이진 탐색은 정렬된 데이터에서 특정 데이터를 빠르게 찾는 방법이다 데이터를 정렬을 한다 정렬 후, 중간 인덱스를 찾고, 해당 값이, 구하려는 값과 같은 값인지 본다 찾으려는 값이 더 작다면, 중간 인덱스 기준 왼쪽으로 / 크다면 중간 인덱스 기준으로 오른쪽으로 탐색을 한다 위와 같이 왼쪽 또는 오른쪽 기준에서 중간 지점을 찾고, 중간에 있는 숫자보다 작은지 큰지, 또는 같은지 탐색을 한다 그리고 숫자 하나가 남을때까지 탐색을 한다 (마지막 숫자 하나가 답이 아니면, 찾으려는 숫자가 없는 것이다) // ========== loop문으로 구현 ================= public static int binarySearch(int[] array, int target) {.. 2023. 7. 4.
[Python] 백준 1300 K번째 수 🧑‍💻 [Python] 백준 1300 Gold 2 - 이진 탐색 이 문제를 통해 더 많은 고민을 하고, 문제를 풀어야겠다는 생각을 했다 그냥 이진 배열을 만들고, 그 배열을 다시 일차원으로 만들어서, 정렬을 한 후에, k번째 숫자를 구할 수 있다 하지만 테스트를 통과하지 않는다 이진 배열을 만들고, 또 일차원 배열로 만드는 것이 메모리 면에서, 굉장히 많이 잡아 먹는다 하지만 A[i][j]는 패턴이 있다 첫 열은, 모든 수를 1로 곱하면 된다 [1, 2, 3, 4, 5] 두 번째 열은, 모든 수를 2로 곱하면 된다 [2, 4, 6, 8, 10] 세 번째 열은 ,모든 수를 3으로 곱하면 된다 [3, 6, 9, 12, 15] 이런 식인 패턴이 있다 위의 패턴을 보게 된다면 특정 숫자를 만들 때에, 그 숫자보.. 2023. 2. 27.
[Python] 백준 2343 기타 레슨 🧑‍💻 [Python] 백준 2343 Silver 1 - 이진 탐색 블루레이의 개수를 구하고, 개수가 작거나 같으면 right = mid - 1 크면 left = mid + 1을 해준다 이유는, 블루레이는 강의들의 묶음으로 이루어져 있다 블루레이의 개수가 맞춰야 하는 개수보다 적다는 말은, 하나의 블루레이에 너무 많은 강의를 넣었다는 것이다 즉 강의를 더 분포를 시켜야 한다 즉 하나의 블루레이에 들어갈 수 있는 강의의 시간은 더 줄어든다는 것 반대로 블루레이의 개수가 맞춰야 하는 개수보다 크다는 것은, 하나의 블루레이에 너무 적은 강의를 넣었다는 것 코드 N, M = map(int, input().split()) def count_cd(time): count = 0 temp = 0 for lecture .. 2023. 2. 27.
[Python] 백준 2467 용액 🧑‍💻 [Python] 백준 2467 용액 Gold 5 - 이진 탐색 산성 용액과, 알칼리성 용액이 있으면, 어떠한 두 용액을 섞어서 0과 제일 가까운 용액을 만드는 것이다 여기서 산성은 산성끼리, 알칼리성은 알칼리성 용액끼리 섞을 수 있다 이진 탐색을 하기 위해서는 정렬을 꼭 해야 한다 두 용액을 섞어서, 전에 섞은 용액보다 0과 가깝다면, 두 용액과, 용액들을 섞어서 나온 숫자를 저장해야 한다 즉 3개의 변수를 지속적으로 수정해야 하는 것이다 코드 N = int(input()) array = list(map(int, input().split())) array.sort() left = 0 right = N - 1 current_min = abs(array[left] + array[right]) left.. 2023. 2. 18.
[Python] 백준 2512 예산 🧑‍💻 [Python] 백준 2512 예산 Silver 3 - 이진 탐색 예산 요청이 리스트로 주어진다. 그리고 국가가 사용할 수 있는 예산이 주어진다 요청 된 모든 예산들이 국가가 사용할 수 있은 예산 안에 들어가야 한다 그러기 위해서, 상한액을 정해서, 요청 리스트 안에 있는 예산들을 수정한다 코드 N = int(input()) array = list(map(int, input().split())) budget = int(input()) array.sort() left, right = 0, array[-1] if sum(array) 2023. 2. 18.

티스토리툴바