hinoky   9달 전

풀이과정을 대충 떠올리긴 했는데,

입력값 제한이 64비트 정수범위인 거 외 다른 제한이 없고, 모듈러 연산 하라는 말도 없어서 손도 못대고 있습니다..

입력값중에 -2^63만 없었어도 어찌어찌 모듈러로 구해볼 수 있을 거 같은데

쟤때문에 모듈러연산으로도 못구하고 있어요..

근데 질문게시판 읽어보니깐 다들 세그트리 기초문제라고 하는데

듣도보도 못한 오버플로우 예외처리까지 요구하는 게 좀 이상해서 질문드립니다.

bigint나 int128동원하시나요? 아니면 정수를 이진수로 바꿔서 비트연산 하시나요?

그것도 아니면 세그트리라는 알고리즘 자체에 중간합이 오버플로우 나더라도 결과합은 멀정하게 나오게 설계된 건가요?

제가 생각한 알고리즘은

1. 배열완전이진트리 생성 

2. 리프노드에 입력된 배열 넣고 부모노드에 자식배열의 합 넣기 O(n)

3. 변경일 때 리프노드 값 변경하고 따라 올라가면서 부모노드 값 변경하기O(mlogn)

4. 호출일 땐 앞서 트리에서 구간합[1,종료값], 구간합[1,시작값-1]을 구하고 두 수를 빼서 출력하기O(klogn)

입니다


만약 배열이

-2^63 // -2^63 // 2^63-1 // 1이라면 구간합 [1,4] 값이 -2^63으로 64비트 범위 내지만, 트리 만드는 과정에서 오버플로우가 발생하죠. 

sshs19071   9달 전

정답이 범위 내에 있다는 보장이 있다면 중간합이 오버플로우가 나도 문제는 없다고 생각합니다.

질문자께서 보이신 예시를 생각하면 (-2^63) + (-2^63)을 계산하면 0으로 원래 정답보다 2^64 크게 나오게 되지만 역시 (2^63 - 1) + 1을 계산하면 -2^63으로 원래 답보다 2^64만큼 작게 나오게 되기 때문에 총합은 그냥 64비트 정수 덧셈으로 구해도 똑같이 나옵니다.

즉 정답이 범위 내에 나온다는 보장이 있다면 중간에 오버플로우가 나더라도 앞의 보장으로 인해 다시 오프셋이 맞춰질 것이라고 보고 해결하셔도 될 것 같습니다.

다만 이는 문제가 정답 범위를 보장했기 때문에 가능한 풀이겠네요.

zenith82114   9달 전

C, C++의 경우 단 한 번이라도 (그 값이 출력 대상인지 여부에 관계없이) overflow가 나면 UB인 것이 맞고, 예전에도 있었던 지적인데 딱히 수정되지 않았나 봅니다.

djm03178   9달 전

오버플로우가 나면 undefined behavior가 맞는데 실제로 그런 데이터가 들어있는지는 확인해보지 않았습니다. 조건을 명확히 하거나 오버플로우가 나는 데이터를 추가하는 것이 좋다고 생각하지만, 오버플로우가 나더라도 undefined behavior임에도 불구하고 실제로 그 때문에 틀리는 코드는 사실상 없을 거라고 봅니다. 이는 long long의 덧셈, 뺄셈, 그리고 곱셈은 마치 ~로 나눈 나머지를 구하는 문제에서 중간에 나머지를 아무때나 취해도 되는 것과 같은 원리로 -2^63 ~ 2^63-1 범위 내를 움직이도록 대체로 동작(절대로 언어 차원에서 보장된 것이 아니지만, 거의 대부분 그렇습니다)하기 때문입니다. 그래서 이 문제에 오버플로우를 무시하고 세그먼트 트리를 쓰더라도 오버플로우로 인해 틀리는 일은 없을 거라고 생각하셔도 됩니다.

doju   9달 전

오버플로우를 피하는 방법 중 하나로는 부호 없는 정수 자료형(unsigned long long)을 사용해 답을 264로 나눈 나머지를 대신 구하는 방법이 있습니다. 이 문제에서는 답의 범위가 정해져 있기 때문에, 이렇게 답을 구했을 때 263 이상의 값이 나온다면 실제 답은 그 값에서 264를 뺀 음수값임을 확신할 수 있습니다.

hinoky   9달 전

doju님 아이디어는 생각해보았으나, -2^63과 0을 구분할 수 없는 문제점이 있습니다

0// 0// -2^63 // -2^63 // -2^63 // 2^62 // 2^62 // 2^62 // 2^62인 경우

a1+a2 = 0mod2^64

-(a3 + a4)mod2^64 = -(2^64)mod2^64 =0

(a5 + a6)mod2^64 = (2^63)mod2^64 = 2^63

(a7 + a8)mod2^64 = (2^63)mod2^64 = 2^63

a1+a2+a3+a4 = 0

a5+a6+a7+a8 = (2^64)mod2^64 =0

구간합[1,8] 은 -2^63이어야 하나 0이 되어 모순입니다

doju   9달 전

인덱스를 헷갈리신 것 같습니다. 일단 제시하신 수열에 수가 8개가 아니라 9개 들어 있습니다.

hinoky   9달 전

그러네요

저렇게 하면 결과값 구해서 0은 0으로, 2^63은 -2^63으로 치환하면 되겠네요

댓글을 작성하려면 로그인해야 합니다.