반응형 투포인터2 [백준/C++] 소수의 연속합 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때, N까지의 소수를 구한 다음에 투 포인터로 연속합을 계산하면 되겠다고 생각했다. 하지만 여기서 간과한 점이 소수를 구하는데 걸리는 시간이었다. 처음에는 2~4,000,000까지 하나씩 전부 소수인지 검사했다.그렇기 때문에 시간복잡도가 O(N^3/2)이 됐다. 그래서 이 시간을 줄이기 위해 예전에 에라토스테네스의 체를 이용했다.에라토스테네스의 체를 이용하면 (n/1 ~ n/n)을 전부 더한 시간복잡도로 O(NlogN)으로 소수들을 구할 수 있다. 그래서 에라토스테네스의 체로 소수들을 구해 빠르.. 2024. 5. 4. [백준/C++] 두 용액 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 두 용액의 합이 0에 가까운 경우를 구하는 문제다.만약 0에 가장 가까운 경우가 여러개라면 아무 경우나 출력하면 된다. 단순히 2중 for문으로 문제를 풀면 O(n^2)의 시간복잡도가 걸린다. 하지만 이 문제는 정렬을 하면 O(nLogn)의 시간복잡도로 문제를 풀 수 있게 된다. 오름차순으로 정렬을 한 다음 양쪽 끝에서 탐색을 시작한다. 이후 양쪽의 용액의 합이 0보다 작다면 왼쪽에 있는 용액을 오른쪽으로 이동시키면 된다. 정렬 돼 있기 때문에 왼쪽의 용액과 오른쪽 끝에 있는 용액을 더한 값이 0보다 작다면,.. 2024. 4. 30. 이전 1 다음 반응형