구하는 ε의 값이 항상 (b - a) / (2 * n)임이 증명되는 것 같습니다.
14608번 - 구분구적법 (Small)
구하는 ε의 값이 항상 (b - a) / (2 * n)임이 증명되는 것 같습니다.
제가 돌맹이였습니다. 어리석었네요.
Gemini에게 이게 왜 맞아? 라고 물어봤는데,
1차 식 대한 구분구적법이라 epsilon = (b-a)/(2*n)이라고 합니다...
코드의 fall-back 로직은 틀려먹은 생각이었는데,
처음 찍은 epsilon이 항상 통과를 보장하는 값이라 while로 문제가 될 리가 없었다는 걸 알았네요
안녕하세요. 제출하신 코드에 대해 흥미로운 질문을 주셨네요. 말씀하신 대로 해당 코드는 몇 가지 논리적 결함이 있어 통과되면 안 되는 것이 맞습니다. 약한 테스트 케이스 때문에 통과된 것으로 보입니다.
요청하신 대로 코드를 실패하게 만드는 반례와 그 원리를 설명해 드리겠습니다.
제출하신 코드가 가진 가장 큰 문제점은 두 가지입니다.
cnt 변수: while 루프 안에서 cnt+=1을 사용하지만, 루프 진입 전에 cnt를 0으로 초기화하는 코드가 없습니다. 따라서 만약 while 루프의 조건이 참이 되어 루프가 한 번이라도 실행된다면, 코드는 NameError를 발생시키며 즉시 중단됩니다.ε 값을 조정하여 오차(delta)를 줄이려는 시도는 좋지만, 그 방법이 잘못되었습니다. ε의 유효 범위는 0 <= epsilonle <= Deltax 입니다. 하지만 코드에서는 오차가 양수일 때 epslion=(epslion+a)/2, 음수일 때 epslion=(epslion+b)/2로 갱신합니다. 이는 탐색 범위를 완전히 벗어난 잘못된 계산이며, 올바른 ε 값을 찾는 것을 보장할 수 없습니다.결론적으로, 이 코드는 최초에 가정한 epslion = dx/2 값이 우연히 정답이거나 정답에 매우 가까워서 while 루프를 단 한 번도 실행하지 않는 경우에만 통과할 수 있습니다.
그렇다면 왜 이 코드가 통과했을까요? 문제의 핵심인 구분구적법 공식에서 ε = Δx/2로 두는 것을 **중점 법칙(Midpoint rule)**이라고 합니다. 이 중점 법칙은 피적분 함수 f(x)가 일차 함수(직선)일 경우 오차가 0이 되어 항상 정확한 정적분 값을 계산해냅니다.
아마도 백준 14608번 (Small) 문제의 채점용 테스트 케이스가 대부분 일차 다항식으로 구성되어 있었을 가능성이 매우 높습니다. 따라서 epslion = dx/2를 초기값으로 설정했을 때 계산한 summation과 실제 integrate 값이 거의 일치했고, while 루프가 실행되지 않아 코드의 결함이 드러나지 않은 채 정답으로 처리된 것입니다.
@ljw1029boj 무심히 지나갈 수 있는 부분이었는데, 제 부족함을 알게 도와주셔서 너무 감사합니다! 늦었지만 항상 좋은 일 있으시길 바라겠습니다!
댓글을 작성하려면 로그인해야 합니다.
kys9808 2년 전
제출번호 80427096이 정답처리되면 안 되는데 정답처리되었습니다.
https://www.acmicpc.net/source...
25행 cnt+=1이
제출된 코드를 보시면 아시겠지만 cnt 변수가 정의되지 않았음에도 참조하는 오류가 있습니다.
14608번에 앱실론이 (a+b)/2 가 아닌 값이 정답이 될 수 있는 경우에 대해서 테스트 케이스가 추가된다면
틀렸습니다가 나왔을 것입니다.