인프런 커뮤니티 질문&답변
작성한 질문수
8-Z 질문드립니다.
작성
·
41
0
다른 분께서 이전에 질문하신 내용과 비슷한 내용인데요,
https://www.acmicpc.net/source/share/ed3075b3f88b464bb600588f9f64a245
위의 큰돌님께서 올려주신 코드에서 23 ~ 25번째 줄, 29번째 ~ 31번째 줄을 보면 아래처럼 선분에 해당하는 좌표별로 일일이 1을 더하는 로직인데요.
// line 23 ~ 25
for(int j = x1 + 1; j <= x2; j++){
_x[j]++;
}
// line 29 ~ 31
for(int j = y1 + 1; j <= y2; j++){
_y[j]++;
}이 경우 길이가 매우 긴 선분이 매우 많은 경우 시간초과가 날 것이라 생각했습니다. 다른 사람의 코드도 보고 chat gpt도 괴롭혀보니 difference array(차분 배열)를 이용해 풀더군요.
그래서 제가 테스트를 좀 해봤는데요,
선분의 길이가 90만에서 100만 정도 되는게 5만개 정도 되는 데이터를 만들어서 시간을 측정해보았습니다.
diff.exe는 차분배열을 이용한 코드를 컴파일한 실행파일이고 nodiff.exe는 차분배열을 이용하지 않은 겁니다.
https://github.com/myc0603/CodingTestStudy/tree/main/week8/Z
위 링크는 차분배열을 이용한 코드, 이용하지 않은 코드 입력파일 만든 코드, 입력 파일에 대한 깃헙 링크입니다.
그리고 백준 게시판에 데이터 추가 요청 글 올렸습니다. (https://www.acmicpc.net/board/view/160093)
큰돌님께서 한번 봐주실 수 있을까요??
답변 1
0
안녕하세요 예찬님 ㅎㅎ
정확한 추가데이터인것같습니다.
만약 제코드가 차분배열 + 누적합을 이용한다면 다음과 같이 되겠죠?
#include <bits/stdc++.h>
using namespace std;
#define y1 aaaa
vector<int> check_x, check_y;
int n, x, y, x1, y1, x2, y2;
int _y[1000004], _x[1000004], ret;
pair<int, int> a[100004];
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x >> y;
x += 500000;
y += 500000;
a[i] = {x, y};
check_x.push_back(x);
check_y.push_back(y);
}
a[n] = a[0];
for (int i = 0; i < n; i++) {
tie(x1, y1) = a[i];
tie(x2, y2) = a[i + 1];
if (x1 != x2) {
if (x1 > x2) swap(x1, x2);
_x[x1 + 1]++;
_x[x2 + 1]--;
}
if (y1 != y2) {
if (y1 > y2) swap(y1, y2);
_y[y1 + 1]++;
_y[y2 + 1]--;
}
}
for (int i = 1; i < 1000004; i++) {
_x[i] += _x[i - 1];
_y[i] += _y[i - 1];
}
for (int a : check_y) ret = max(ret, _y[a]);
for (int a : check_x) ret = max(ret, _x[a]);
cout << ret << "\n";
}
저조차도 생각못한 부분인데 생각하시다니 정말 대단하십니다. ㅎㅎ
추가데이터 관련 리뷰
보통 백준에서 TC를 설정할 때 다음과 같은 조건이 들어갑니다.
"모든 케이스를 통틀어서 1초 내에 끝나야 합니다."
지금 보면 1초이하긴 해서 해당 TC가 반영될 가능성이 높지만 출제자가 동의해야 아마 넣는게 가능해서 조금 기다려봐야 할 것 같아요 ㅎㅎ
TC는 좋습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
x1, x2, y1, y2범위가 0이상이라 차분배열인 x, y배열을 누적합하기 위해서 인덱스가 1부터 시작하는거라 생각되는데 맞나요?
-> 네 맞습니다.
돌님 코드에서 x, y배열에 +1, -1할 때 왜 x1,x2,y1,y2에 1을 더하나요??
->
이거는 이렇게 생각하시면 됩니다.
예를 들어
(2, y) → (5, y) 라는 수평선이 있을 때,실제로 영향을 주는 x좌표는: 3, 4, 5겠죠?
이 때 이를 적용하려면 다음과 같은 식이 완성됩니다.
_x[3]++;
_x[6]--;
이렇게 하면 누적합을 통해 x = 3, 4, 5 에서만 값이 1 증가하게 됩니다.
감사합니다.
항상 좋은 답변 감사드립니다!!
별개로 큰돌님 코드에서 _x, _y배열에 +1, -1할 때 왜 x1,x2,y1,y2에 1을 더하나요??
x1, x2, y1, y2범위가 0이상이라 차분배열인 _x, _y배열을 누적합하기 위해서 인덱스가 1부터 시작하는거라 생각되는데 맞나요?