부분 합. [2167]
[1. 문제 설명]https://www.acmicpc.net/problem/2167[2. 풀이 접근]문제의 요구 사항은 다음과 같다.입력으로 주어진 i, j, x, y 가 배열 상에서 아래와 같은 그림과 같을 때다음과 같은 영역의 존재하는 원소들의 합을 구하는 것 이다.단순한 풀이, 매 TC 마다 배열의 구간 [i, j] ~ [x, y] 를 iterate 하면서 그 합을 구한다면,전체 시간복잡도가 O(N*M*10000) 이고, 대략 300*300*10000 = 9*108 ==> 1초가 넘어 갈 수 있다. 그러나 각 행마다 그 부분 합 들을 따로 구해 놓으면,300*10000 = 3*106 으로 시간 복잡도를 대폭 줄일 수 있다. 각 행에 대해서는 루프를 돌지만, 그 행의 합은 O(1) 에 구할 수 있게 ..
이분탐색 솔루션
[1. 개요] 보통 매우 큰 범위를 갖는 어떤 값 중 최적 값을 찾을 때 유용하다. N 이 [0, 1,000,000,000] 사이의 값일 때, 어떤 식을 최대 혹은 최소로 만드는 N 을 구한다. 완전 탐색 시, 시간 초과가 당연하다. 그러나 이 범위에서 이분 탐색을 하면, 32번 이내로 찾을 수 있다. => 어떤 조건을 만족하는 최대 N 을 구해야 할 때 => 먼저 중간 값을 찾고, 이 값을 주어진 식에 대입 => 특정 조건을 만족하면 상위 구간에서 이분 탐색 진행 => 만족하지 않으면 하위 구간에서 이분 탐색 진행 주의 할점 범위와 반복문 조건이 중요하다. (구간 및, 반복문 조건 (등호 유무) 등이 다르면 틀린다.) => 구간은 보통 [a, b], 폐구간 이어야 한다. => 그래서 반복문 조건은 wh..
