본문 바로가기
반응형

누적합5

[백준/C++] 동작 그만. 밑장 빼기냐? (No.20159) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 밑장을 뺄 경우 어떻게 수가 분배 되는지를 파악하면 누적합을 이용해 쉽게 풀 수 있는 문제다. 그림을 통해 한번 알아보자  B카드를 받아야 하는 상태에서 밑장을 빼면, A카드를 받고 그 뒤에 z, b, c, d ...카드를 받게 된다.즉, 내가 카드를 받을 순서에서 밑장을 빼면 그때부터 나는 원래 받을 카드가 아니라, 상대방의 카드를 전부 받게 된다. 이를 이용하면 내가 받을 i번째 카드의 밑장을 빼면 내가 원래 받을 i-1번째 카드까지의 합 + 상대방이 받을 i번째 카드부터 N/2번째 카드까지의 합으로 나.. 2024. 9. 25.
[프로그래머스/C++] 문자열의 아름다움 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 풀이를 잘 생각해 구현하면 되는 문제다. 단, 크기가 300000이기 때문에 O(n^2)의 시간복잡도로는 해결할 수 없다. 그러므로 누적합을 활용해 O(n)의 시간복잡도로 문제를 해결했다. "aabba" 와 같은 문자열이 있다고 생각하자 이제 문자를 크게 두개로 나눠서 생각을 한다. 1. 양 끝 문자가 다른 경우 이 경우는 항상 문자열의 크기만큼의 아름다움을 갖게 된다. 2. 양 끝 문자가 같은 경우 이 경우는 양 끝 문자를 사이에 가장 아름다움을 갖는 문자를 찾아야 한다. 이제 아래와 그림을 보자 첫 문자 a부터 왼쪽으로 탐색을 시작한다. 탐색을 하다가 현재 문자가 b인데, 이전 문자가 a가 됐다. .. 2024. 4. 2.
[백준/C++] 수열 회전과 쿼리 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 수열의 회전에 관한 문제다. 문제의 내용을 보면 수열을 이동하는 쿼리와 수열의 특정 범위의 합을 묻는 쿼리에 대해 답을 출력하는 문제다. 여기서 특정 범위의 합은 매번 계산하기보다 누적합을 이용하면 한번의 계산으로 답을 출력할 수 있다. 수열의 이동은 원순열을 생각하면 편하다. (한쪽 끝으로 이동하다가 범위를 넘어서면 반대쪽으로 넘어간다) 먼저 처음에 시작 index를 정한다. 이제 수열의 시작 부분이 k만큼 증가하면 이는 시작 index가 오른쪽으로 이동한 것과 같다. 만약 시작 부분이 k만큼 감소하면 이는 시작 index가 왼쪽으로 이동한 것과 같다. 여기서 합을 구하는 범위가 N을 넘어가지 않기 .. 2024. 3. 12.
[프로그래머스/C++] 광고 삽입 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] HTML 삽입 미리보기할 수 없는 소스 그렇게 별 생각 없이 문제를 풀려고 했더니 전혀 다른 문제라는 것을 알게 됐다. 이 문제는 광고는 길이가 포함되어 있기 때문에, 실제로 광고를 시청한 시간이 가장 긴 부분을 계산해야 됐기 때문이다. 그래서 어떻게 문제를 풀까? 고민을 하다가 어차피 특정 구간에 광고를 시청했는지 파악을 하려면 누적합을 이용하면 총 [3600*100(시간) - 광고길이] 만큼만 크기 비교를 하면 되니까 풀리겠다는 생각이 들었다. 문제는 여기서도 고민이 생겼다. 누적합으로 문제를 해결하는 것은 어렵지 않은데, 누적합을 구하기 위해 특정 구간에 몇명이 광고를 보고 있는지 표시를 해야했다. 영상을 .. 2024. 2. 25.
[프로그래머스/C++] 파괴되지 않은 건물 (2022 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 단순히 각 구간에 계산을 전부 해주면 250,000*1,000*1000이 되어 시간을 초과하게 된다. 그래서 구간을 전부 계산하는 것이 아닌, 시작 부분과 끝나는 부분에만 숫자를 더해 누적합으로 풀면 된다. 예를 들어 스킬이 [0,5,5,5,5,0]과 같이 데미지가 들어간다면, 이를 [0,5,0,0,0,-5]와 같이 표시할 수 있는 것이다. 이를 2차원으로도 확장 시킬 수 있는데 아래와 같이 변환 할 수 있다. 오른쪽의 변환된 정보를 x 축 기준으로 누적합을 계산한 다음 y축을 따라 다시 누적합을 계산하면 왼쪽과 같은 형태가 된다. 아래와 같은 순서로 압축 압축한 정보를 이용할 경우는 아래와 같이 압축해제 모든 .. 2024. 1. 29.
반응형

티스토리툴바