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..
1. 기본문제1 n개의 숫자가 오름차순으로 정렬된 상태로 주어집니다. 이후 m개의 숫자가 추가적으로 주어졌을 때, 각각의 숫자가 처음 주어진 n개의 숫자 중 몇 번째로 나온 숫자인지를 구하는 프로그램을 작성해보세요. 2. 풀이 배운대로 기본에 충실하게 만들어보자 Main 클래스 내에서 public static int 함수로 binarysearch를 만들고, mid 포인트는 start + (end - start)/2로 하고 삼분탐색하지 말고, 이분탐색으로 arr[mid] >= target인 경우와, arr[mid] = ..
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//(..
1. parametric search 이분 탐색을 응용하여, "최적화 문제"를 "결정 문제(decision problem)"로 바꿔서 문제를 푸는 알고리즘 최적화 문제는 예를 들면 다음과 같다. "f(x) = True가 되는 x의 최댓값을 구하세요" 이를 결정 문제로 바꾸면 다음과 같을 것이다. "어떤 x에서 f(x) = True인가?" 가능한 모든 x에 대해 f(x)가 True인지, False인지 검사한다면, 최적화 문제를 결정 문제의 집합으로 바꾸어 해결할 수 있을 것이다. 모든 결정 문제의 값 중에서 True인 최댓값을 구하면 되니까 하지만 모든 결정문제를 다 해결하는 것은 당연히 비효율적 그러나 어떤 조건을 만족한다면, 위 과정을 효율적으로 해결할 수 있다. x1 < x2이고, f(x2) = Tr..
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보..
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}$까지가..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
