osh8242   3년 전

이 문제는 '에라토스테네스의 체'를 이용하여 소수를 걸러내야하는데

소수를 걸러낼 범위가 주어져있지 않습니다.

입력되는 자연수 N(최대 1,000,000)보다 큰 소수(1,003,001)까지 찾아야하는데,

'에라토스테네스의 체'를 적용할 범위가 주어져있지 않으므로

푸는 사람이  훨씬 큰 범위를 잡아서 풀고, 

최적화를 위해서 코드를 돌려본 뒤 직접 찾아내야합니다.

어차피 훨씬 큰 범위를 잡아도 풀어지기 때문에 큰 상관은 없는데

최적화를 위해서 문제를 푸는 사람이 코드를 돌려보고 직접 범위를 찾는 것이 출제의도와는 멀다고 생각됩니다.

따라서 아래와 같은 예제입출력이 추가되어야한다고 생각합니다.

예제 입력2

1000000

예제 출력2

1003001

protarie   3년 전

N이 최대 100만이라는 범위가 있으니까 필요없는 것 아닌가요.

제한시간이 2초나 되기 때문에 최적화를 해야 한다는 조건은 고려할 필요가 없을 것 같습니다.

N과 2N사이에는 소수가 항상 존재하므로 200만을 상한으로 잡아서 풀리면 충분하다고 봅니다.

osh8242   3년 전

저도 굳이 최적화까지는 필수조건은 아니라서 상관없다고 생각은 합니다만..

100만보다 큰 소수를 찾으려면,

어느 범위까지 설정을 해야하는지 일반적인 고등학교 수학의 배경지식으로는 알기 어렵다고 생각되어서

저 예제입출력을 넣어주는 것이 좀 더 낫지 않을까 생각해봤습니다..

djm03178   3년 전

조건에 모호한 부분이 없기 때문에, 코드가 어디까지 계산해야 할지 알아내는 것은 문제를 푸는 사람의 몫이라고 생각합니다. 직접 코드를 돌리고 어디까지 계산해야 모든 답을 구할 수 있는지 찾는 건 어렵지 않고, 출제 의도와 정확히 부합한다고 생각합니다.

osh8242   3년 전

오래된 문제이기도 하고 이 문제가 추가 입출력예제가 없어도

범위를 1000만 이상으로 매우 크게 잡아도 풀리기 때문에 추가 입출력예제가 없어도 사실 큰 상관은 없습니다.

그런데 이 문제를 처음 푸는 사람의 입장에서 생각해봤을 때는 

추가 입출력예제가 있는 것이 좀 더 

출제의도 자체('에라토스테네스의 체'를 이용한 소수판별 + 펠린드롬 판별)에 부합한다는 느낌이 들었습니다. 

'에라토스테네스의 체'를 이용해서 탐색범위를 적용하려고할 때

굳이 소수의 존재범위에 관한 수학적 배경지식이 필요할 이유가 있을까?

처음 푸는 사람의 입장에서 크게 범위를 잡아서 풀 때 시간 초과가 난다면,

이 사람은 시간 초과의 원인이 자신의 로직이 불필요한 것이 많아서 난 것인지, 

범위를 잘못 설정해서 난 것인지 알 수 없지 않을까?

라는 생각에서 추가 입출력예제를 건의해보았습니다..

djm03178   3년 전

1. 출제자는 이 문제의 의도가 에라토스테네스의 체라고 한 적이 없습니다. 오히려 말씀하신 예제를 주지 않았다는 점에서, 어떤 방식으로 푸는 게 좋을지를 알아내는 것이 의도에 포함된 것이라고 보는 것이 맞지 않을까요? 참고로 알고리즘 분류에 있는 에라토스테네스의 체는 출제자가 정한 것이 아니라, solved.ac에서 유저들의 투표로 붙은 것으로 이 알고리즘으로 풀 수 있다 정도의 의미입니다.

2. 문제는 로컬에서 풀고 제출은 정답 여부를 확인하기 위해서만 하는 것이 기본입니다. 시간 초과가 날 정도로 범위를 크게 잡고 제출을 한 것은 문제를 제대로 풀지 않고 제출했다는 말과 같은 것입니다. 제대로 문제를 푼다고 하려면 시간 초과를 받고 왜 시간 초과가 났는지를 고민할 게 아니라 처음부터 문제의 답이 어디까지 갈지를 로컬에서 확인한 뒤에 제출하는 것이 맞습니다.

3. 수학적 배경지식을 요구하는 문제도 아닙니다. 그냥 로컬에서 답이 어디까지 가는지 테스트를 해보면 됩니다. 이 과정에서 수학적 배경지식이 왜 언급되는지 모르겠습니다.

osh8242   3년 전

1. 알고리즘 분류가 '에라토스테네스의 체'로 되어있어서 출제자의 의도라고 생각했습니다.

2~3. 

저는 적절한 탐색범위를 설정하는 단계가 문제를 풀기전에 주어져야된다고 보는데

문제를 다 풀어서 올바른 답을 낼 수 있는 다음에 코드를 돌려서 탐색범위를 자기가 찾을 수 있는 것은 문제를 풀어나가는 과정순서가 역전되었다고 생각합니다.

(탐색범위를 크게 잡음) -> (문제를 풀어냄) -> (탐색범위를 적절하게 수정)

이미 탐색범위를 크게 잡아도 문제가 풀어지기 때문에 탐색범위를 수정하는 과정은 애초에 이 문제에서 필요치않습니다만

처음부터 탐색범위를 주어서

(탐색범위를 적절히 잡음) -> (문제를 풀어냄)

으로 가는 식으로 유도하는게 맞다고 생각하기에 의견을 제시해보았습니다..

djm03178   3년 전

내용을 추가하는 게 늦었는데, 알고리즘 분류는 출제자가 정한 것이 아니라, solved.ac에서 유저들의 투표로 붙은 것으로 이 알고리즘으로 풀 수 있다 정도의 의미입니다. 출제 의도와는 관계가 없습니다.

설령 출제자가 에라토스테네스의 체를 유일한 정해로 생각하고 출제를 했다고 하더라도, 범위는 직접 찾아내라는 걸 의도로 하지 않았으리란 법도 없습니다.

djm03178   3년 전

탐색범위를 문제에서 제시해주지 않아서 직접 그 범위를 찾아야 한다면, 그 범위를 찾는 것 또한 문제의 의도이자 문제의 일부입니다. 탐색 범위를 문제가 제시해줘야 한다는 건 문제의 역할을 지나치게 제한하는 거라고 생각합니다. 첫 댓글에서도 말씀드렸지만 조건에 문제가 없다면 지문은 그 자체로 완성이며, 출제 의도가 무엇인지, 그를 위해 어떤 것들을 알아야 하는지, 무엇을 구현해봐야 하는지 등은 모두 문제를 푸는 사람의 몫입니다. 부족한 정보로 인해 난이도가 상승할 수도 있는 것도 자연스러운 일이며, 실제로 어려운 문제들일수록 이런 식으로 직접 탐색 범위를 구해야 하는 문제들이 점점 많아집니다. 그 범위를 문제에서 제시해주는 건 문제 난이도를 낮추고 문제 푸는 사람의 편의를 봐줄 뿐, 그 자체로 결함이 있는 부분이 아닙니다.

탐색 범위를 직접 알아내야 하는 부분이 문제의 일부로서 존재하면 안 될 이유가 없습니다.

djm03178   3년 전

추가로 말씀드리자면, 저는 편의를 위해 그러한 예제를 추가한다고 하더라도 딱히 상관은 없다는 입장입니다. 다만 그것이 "현재 상태가 문제의 의도와 맞지 않기 때문에 반드시 추가되어야 한다"는 아니라고 생각합니다.

osh8242   3년 전

탐색범위를 직접 찾는 것 또한 공부하는 과정의 일부가 될 수 있기 때문에

저도 굳이 필요하지 않다는데 동의합니다.


그러나 이 문제에서 탐색범위를 매우 크게 잡아도 풀어지기 때문에

탐색범위를 찾는 과정 자체가 무의미해서

기왕이면 처음부터 입출력예제를 주어지는 것이 낫지 않을까 하는 생각이었습니다..

zenith82114   3년 전

범위를 아주 크게 잡아도 풀린다면 문제에서 도움을 줄 필요는 더더욱 없지 않나요?

djm03178   3년 전

답의 최댓값을 정확하게 찾고 문제를 풀 것이냐, 얼마나 최대인지 모르니 적당히 크게 잡고 제출해서 충분하기를 바라고 도박을 할 것이냐, 정답을 받는 것과 무관하게 범위를 찾고 증명하는 과정 자체에서 의미를 찾을 것이냐는 모두 본인의 선택입니다.

나는 적당히 크게 내서 맞았는데 그거면 됐다고 넘어갈 사람은 넘어가고, 그래도 나는 정확하게 상한을 계산해보고 제출해야겠다 싶은 사람은 그렇게 하면 될 일입니다.

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