1. 점 고르기모든 n^2개의 점을 잡아서, 두 점을 최대 / 최소로 하는 직사각형이 존재할 수 있는지를 판별하면 간단하게 풀 수 있다. 이 존재성은 단순한 O(1) 식으로 판단할 수 있어서, 시간 복잡도는 n^2이다. 난 n^2lgn에 풀었는데 내 풀이는 부끄러우니 설명을 생략한다... 2. Number SetsP 이상의 모든 prime factor를 열거해야 할 것 같지만, 실제로 필요한 건 P 이상 1000000 이하의 prime factor 뿐이다. 1000001 이상의 prime factor는 중요하지 않은 게, B - A
1. MP3 Songs아무 생각 없이 아스키 순으로 정렬하면 나옴. 앞으로는 셋에 이런 문제를 넣지 않겠습니다. 2. Reconstruction Trees올바른 입력임을 가정할 때 preorder와 inorder가 주어지면 유일하게 트리를 결정할 수 있다. preorder의 맨 앞에 있는 원소가 루트이고, inorder에서 이 루트를 찾으면, 왼쪽 서브트리와 오른쪽 서브트리를 찾을 수 있다. 우리는 여기서 루트와, 왼쪽 서브트리의 preorder / inorder, 오른쪽 서브트리의 preorder / inorder를 찾을 수 있기 때문에 재귀적으로 전체 트리 모형을 유추할 수 있다. 이 트리를 postorder traversal하면 된다. 여담으로 트리를 만든다는 식으로 서술했지만 실제로는 찾아가면서 ..
다음과 같은 문제를 생각해 보자.크기 N의 수열이 있을 때, 길이 K 이상인 구간 중 최대 평균을 계산하라. 식을 전개해 보자. 주어진 입력의 부분합을 Si 라고 하면, j - i >= K 일 때 (Sj - Si) / (j - i) 를 최대화해야 한다. 하지만 그렇게 쉬워 보이지 않는다. 어떻게 해야 할까?1. 답에 대한 이진 탐색어떠한 문제의 가능한 최대 / 최솟값을 계산하기 위해서, 문제를 결정 문제로 바꿔서 이진 탐색을 하는 방법이 잘 알려져 있다. 예를 들면, "가능한 답 중 최댓값을 계산하라" 는 문제를, "X 이상이 이 문제에서 가능한 답인지를 판단하라"는 문제로 바꾸면, 가능한 답 중 최대인 X를 이진 탐색으로 판별할 수 있다. 만약에 최댓값을 계산하는 것은 어렵지만, X 이상이 가능한 답인..
- Total
- Today
- Yesterday