CHAAANY ARCHIVE
3개의 기록을 주제별로 둘러보세요.
백준 25682번 ‘체스판 다시 칠하기 2’는 모든 K×K 구간마다 다시 칠할 칸을 직접 세면 느리다. 전체 board를 두 가지 chess pattern 중 하나와 비교해 불일치 칸을 1로 표시하고, 2차원 누적합으로 각 구간의 합을 O(1)에 구하면 된다.백준 25682번 체스판 다시 칠하기 2불일치 배열 하나면 충분하다먼저 (1, 1)이 W인 무한 chess pattern을 기준으로 둔다.row + column이 짝수면 예상 색은 Wrow + column이 홀수면 예상 색은 B실제 색이 예상과 다르면 1, 같으면 0이 불일치 값을 2차원 누적합 prefix에 저장한다. 어떤 K×K 구간에서 기준 pattern과 다른 칸이 x개라면, 반대 pattern과 다른 칸은 K×K - x개다. 두 값 중 작은..
백준 11660번을 처음 풀 때는 각 행의 누적합만 만들었다. 제출은 통과했지만, 원문에도 “이거 시간 초과가 나야 정상인 것 같은데”라고 적어 두었다. 최악에는 쿼리마다 최대 1,024개 행을 다시 훑으므로 약 1억 번의 덧셈이 필요했다.백준 11660번 구간 합 구하기 5통과 여부가 실행 환경의 여유에 좌우되지 않게 하려면 2차원 누적합을 만들어야 한다. 전처리는 O(N²), 각 직사각형 쿼리는 O(1)이 된다.2차원 누적합의 기준을 먼저 정하기prefix[row][col]을 (1, 1)부터 (row, col)까지의 합으로 정의한다. 현재 칸의 값을 value라고 하면 다음 식으로 채울 수 있다.prefix[row][col]= value + prefix[row - 1][col] + prefix[row..
백준 16139번 ‘인간-컴퓨터 상호작용’은 문자열의 구간 [left, right]에 특정 알파벳이 몇 번 등장하는지 여러 번 묻는다. 매 query마다 구간을 다시 세면 최악 O(NQ)이므로, 알파벳별 누적 등장 횟수를 먼저 만든다.백준 16139번 인간-컴퓨터 상호작용prefix index를 한 칸 밀어 두기prefix[c][i]를 문자열의 앞 i개 문자에 알파벳 c가 등장한 횟수라고 정의한다.prefix[c][0] = 0prefix[c][i + 1] = s[0..i]에서 c의 개수문제의 query index는 0부터 시작하고 양끝을 모두 포함한다. 그러면 [left, right]의 답은 다음 한 줄이다.prefix[c][right + 1] - prefix[c][left]right + 1이 들어가는 ..