[Java]자바로 이진탐색 연습2 -올바르게 사고하기-

1. 문제 n개의 점과 m개의 선분이 주어질 때, 각 선분 위에 몇개의 점이 있는지 구하는 프로그램을 작성해보세요. 첫 번째 줄에 n과 m이 공백을 두고 주어집니다. 두 번째 줄에는 점의 좌표가 공백을 사이에 두고 주어집니다. 세 번째 줄부터 m개의 줄에 걸쳐 선분의 시작점과 끝점이 공백을 두고 한 줄에 하나씩 주어집니다. 1 ≤ n, m ≤ 100,000 1 ≤ 주어지는 수 ≤ 1,000,000,000 3 4 10 30 50 1 5 5 21 22 59 210 293 2. 풀이 아무 생각없이 사고 한다면... 선분의 시작점 끝점 예를 들어 1 5를 기준으로, 여기에 점의 좌표 10,30,50이 들어있는지 검사해보는 식으로 이렇게하면 O(MN)인가? 사실 이러면 이진탐색이고 뭐고 점의 좌표 10,30,50..

• format_list_bulleted 이분 탐색
• · 2023. 4. 2.
• textsms

[Java]자바로 이분탐색 연습 -기본, lower bound, upper bound-

1. 기본문제1 n개의 숫자가 오름차순으로 정렬된 상태로 주어집니다. 이후 m개의 숫자가 추가적으로 주어졌을 때, 각각의 숫자가 처음 주어진 n개의 숫자 중 몇 번째로 나온 숫자인지를 구하는 프로그램을 작성해보세요. 2. 풀이 배운대로 기본에 충실하게 만들어보자 Main 클래스 내에서 public static int 함수로 binarysearch를 만들고, mid 포인트는 start + (end - start)/2로 하고 삼분탐색하지 말고, 이분탐색으로 arr[mid] >= target인 경우와, arr[mid] = ..

• format_list_bulleted 이분 탐색
• · 2023. 4. 1.
• textsms

이분탐색 올바른 사고 연습하기 1편

1. 문제1 1072번: 게임 (acmicpc.net) 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 2. 풀이1 탐색범위는 x+1부터 충분히 큰 수까지.. x가 제한이 10의 9제곱인데.. 이는 입력으로 주어지는 x가 10의 9제곱이지 가능한 제한이 10의 9제곱이라는 뜻은 아니다. 그래서 대충 10의 18제곱까지 탐색하도록 범위를 잡았다 그리고 절대로 지지 않는다고 했기 때문에... x 기준으로 현재 x+k를 잡았다면... y값은 y+k로 바뀌겠지 그리고 그때 변화된 승률도 (y+k)*100//(..

• format_list_bulleted 이분 탐색
• · 2023. 4. 1.
• textsms

처음 배우는 parametric search 이해해보기

1. parametric search 이분 탐색을 응용하여, "최적화 문제"를 "결정 문제(decision problem)"로 바꿔서 문제를 푸는 알고리즘 최적화 문제는 예를 들면 다음과 같다. "f(x) = True가 되는 x의 최댓값을 구하세요" 이를 결정 문제로 바꾸면 다음과 같을 것이다. "어떤 x에서 f(x) = True인가?" 가능한 모든 x에 대해 f(x)가 True인지, False인지 검사한다면, 최적화 문제를 결정 문제의 집합으로 바꾸어 해결할 수 있을 것이다. 모든 결정 문제의 값 중에서 True인 최댓값을 구하면 되니까 하지만 모든 결정문제를 다 해결하는 것은 당연히 비효율적 그러나 어떤 조건을 만족한다면, 위 과정을 효율적으로 해결할 수 있다. x1 < x2이고, f(x2) = Tr..

• format_list_bulleted 이분 탐색
• · 2023. 3. 29.
• textsms

이분탐색의 올바른 사고방식 익히고 lower_bound, upper_bound 가볍게 복기하기

1. 이분 탐색(binary search) False 구간, True 구간 2개의 partition으로 분할된 구간에서, 분할 경계의 위치를 O(logN)에 찾는 알고리즘이다. STL로 구현된 lower_bound와 upper_bound는 가장 유명한 이분 탐색 함수중 하나이다. 정렬된 배열에서 x의 lower bound는 정렬 상태를 유지한 채 x를 삽입할 수 있는 첫번째 위치이고 upper_bound는 마지막 위치이다. 위 그림에서 lower_bound(20)은 20을 넣을 수 있는 첫번째 위치로, 1번에 넣을 수 있다.. upper_bound(20)은 20을 넣을 수 있는 마지막 위치로, 4번에 넣을 수 있다..(원래 4번은 5번으로 이동하겠지) 이분 탐색적 설명으로는, lower_bound는 x보..

• format_list_bulleted 이분 탐색
• · 2023. 3. 29.
• textsms

이분탐색 응용력 키우기 연습1 -차이가 가장 가까운 값을 찾는 방법-

1. 문제 2428번: 표절 (acmicpc.net) 2428번: 표절 첫째 줄에 제출한 솔루션의 개수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ..., size(FN)이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) 솔루션 파일의 크기는 정수이 www.acmicpc.net 2. 풀이 $F_{1}, F_{2}, ... , F_{n}$이 주어질때, $F_{i} = 0.9*F_{j}$인 $(F_{i}, F_{j})$의 개수를 구하는 문제 조건이 2개가 있는데.. 사실 $F_{i} = 0.9*F_{j}$을 만족하는 최대 인덱스 j를 찾는다 그러면 $F_{i}, F_{i+1}$, ..., $F_{i}, F_{j}$까지가..

• format_list_bulleted 이분 탐색
• · 2023. 3. 28.
• textsms