어떤 문제가 백준에서 사용 가능한 모든 언어로 해결 됨이 보장돼야 할 이유는 없습니다.
18793번 - 팰린드롬 덧셈
어떤 언어가 가진 장점들을 활용할 수 있는 만큼 그로 인한 페널티도 당연히 감수해야 합니다. 파이썬이 느린 것은 그만큼 프로그래머에게 많은 편의를 제공하기 때문도 있습니다. 이미 BOJ는 대부분의 문제에 대해 느린 언어들에 대한 배려로 보너스 시간을 부여하고 있는데, 이는 기본적으로 이 사이트가 연습을 목적으로 쓰인다는 점을 감안한 것이며 모든 문제에 대해 모든 언어로 풀리게 해주겠다는 뜻은 아닙니다. 이 문제와 같이 출제자가 다른 언어에 대한 '관대함'을 원하지 않았다면 그 의도를 존중해주는 것이 맞다고 생각합니다.
애초에 BOJ의 문제 중에는 제출할 수 있음에도 해결이 아예 불가능한 언어가 있는 경우가 많습니다. Text만 해도 그렇고, 아희를 비롯한 일부 난해한 프로그래밍 언어들은 파이썬보다도 훨씬 느려서 보너스를 아무리 많이 줘도 절대 시간 내에 해결이 안 되는 문제들도 많습니다. 이런 언어들을 모조리 배려해주거나 아니면 문제마다 하나하나 제한 필터를 건다는 건 현실적이지도 않습니다.
물론 모든 문제가 파이썬을 배려해 줄 필요가 없는 것은 맞지만, 만약 이 문제에 디폴트 시간 보정(x3+2)이 걸렸었다면 PyPy3으로는 통과가 가능할 것으로 보입니다.
오답 대비 정답의 실행 시간이 압도적으로 짧은데 시간 보정이 걸리면 오답도 통과가 되어서 시간 보정을 빼는 것이라면 모를까, 첫 작성자님 말처럼 이 문제에는 그러한 오답이 있는 것도 아닙니다.
이것만이면 그려러니하고 넘어갈 수 있는데, 이 문제에 명시적으로 제출 가능한 언어 제한이 걸려 있고 그 언어에 파이썬이 포함되어 있는 것도 문제입니다.
입출력 시간 때문에 풀지 못하는데 사용 가능한 언어 제한에 파이썬이 있는게 불합리하게 느껴집니다.
따라서 다음 세 가지 중 한 가지를 제안합니다.
이 문제에 추가 시간을 주지 않은 이유에 대해 생각해보자면, 약간의 잘 최적화된 백트래킹 등의 방법이 있더라도 그걸 최대한 막기 위해서라고 생각합니다. 모든 경우를 잘 커버할 수 있는 case work로 문제를 푸는 것이 정해라는 것이죠. 제가 아는 바에 따르면, 오답 대비 정답의 실행 시간이 압도적으로 짧을 수 있습니다(작은 수에 대한 케이스 워크 부분). 이에 따르면 시간 보정을 안 해주는 것이 전혀 문제가 없다고 생각합니다. 실제로 Python이나 Java가 시간 보너스로 오히려 이득을 보는 문제들도 있고, 이로 인해 "Python에서 naive solution이 통과 / Java에서 naive solution이 통과" 같은 사례들이 실제로도 있었습니다. (TMI: 이 주제는 구데기컵 문제로도 다루어진 바 있습니다.)
설령 이 문제가 C++로만 풀 수 있는 문제라 하더라도, 어쩔 수 없다고 생각합니다. 그게 이 문제의 컨셉이나 아이덴티티가 될 수 있겠죠. 언어 제한에 파이썬이 포함된 건 파이썬으로 풀 수 있는지랑은 관련 없다고 생각합니다. 이런 상황이 바람직한가? 에 대해서는 의견차가 있을 것이라 생각합니다만, 그게 싫다면 이 문제를 안 풀면 됩니다... 이 문제는 well-defined된 문제며, 여러 사람들이 풀어서 검수된 문제입니다. 현재 상태로도 아무 문제 없습니다.
이 문제의 출제자 역시도 추가 시간을 안 주는 현재 방향을 바꿀 생각이 없을 것 같으며, 아직 이 문제를 풀지 않은 저의 의견 역시도 이 문제에 추가시간이 있을 필요는 없다고 생각합니다. 정말 이 문제를 파이썬으로 풀 수 없을까요? 가능하다면, 그리고 제가 시간적인 여유가 좀 많이 남게 된다면, 여러분들의 생각을 깨드리도록 하겠습니다.
문제 푸는 방법이 방법인지라 코드가 천 줄이 넘어가서 제가 미처 못 보고 지나친 게 있을 수도 있고, 제가 파이썬 최적화에 경험이 부족해서 틀릴 가능성도 있습니다.
그래도 다음과 같은 이유 때문에 전 그렇게 단정지으려 합니다. 제가 틀렸다면 뭔가를 배울 좋을 기회가 되겠죠...
제가 생각할 수 있는 가능한 최적화 여지는 몇 가지 조건을 중복 체크하는 것을 줄이는 것, in 연산을 두 개의 ==로 바꾸는 것이나 수식 최적화 (mod 연산을 조건문으로 바꾼다던가) 정도인데, 이 정도로 시간 초과 날 만한 코드가 통과될 코드로 바뀔 것 같지는 않습니다.
우선 제 생각으로는 입출력만으로 0.5초가 넘지는 않을 것 같습니다.
http://boj.kr/48fcf5525be74389...
이 문제의 입출력 양은 각각 최대 약 700만 자로, 이 문제에서의 최대 입력량의 1/5 정도이며, 출력량도 반 정도에 불과합니다. 정렬 시간 역시 무시할 수 없 약 0.4초 안에 실행될 수 있을 거라고 생각할 수 있습니다.
제가 말씀드린 게 그 다른 글의 댓글로 다신 걸 보고 말씀드린 건데, 말씀하신 것만으로는 그 원인이 입출력 때문이라고 단정할 수가 없습니다. 말씀드렸듯이, 출력을 제거한 상태에서 시간 내에 실행이 되는 입력을 넣었다면 오답(아무 답을 출력 안 한 것)을 출력했으니 틀렸습니다로 나오게 됩니다. 마지막에 무한 루프를 넣으셨다면 무한 루프에 걸려 시간을 초과했으므로 답에 대한 판정 자체를 하지 않을 것이니 시간 초과가 나올 것이고요. 정상적으로 출력했을 때 그 케이스를 통과한 뒤, 다음 케이스를 실행했는데 그게 너무 오래 걸리는 케이스여서 시간 초과가 난 것일 가능성을 배제할 수 없습니다.
제가 보기에는 지금 입력 + 알고리즘을 돌리는 시간 단독이나, 출력만에 걸리는 시간으로는 0.5초 이내에 돌아갈 수 있으나, 둘을 합치면 0.5초가 넘어가는 케이스인 것 같습니다.
다만 이 문제의 경우 절반을 출력하는 것은 맞으나 입출력에 추가적인 처리(자리수<->문자열 변환)를 하고 있는데, 지금 그 과정에서 완전히 최적화가 이루어졌다고 자신있게 말할 수는 없기 때문에 제가 틀렸을 여지는 있습니다...
첫 번째 테스트 케이스를 통과했는데 다음 테스트 케이스에서 시간 초과가 뜨는 경우의 가능성이 없지는 않은데, 여러 정황상 가능성은 좀 낮게 보고 있습니다. (파이썬으로 퍼센트가 올라가는 것을 본 적이 없다던지 등...)
그런 케이스를 배제할 수 없다는 것은 알겠습니다.
댓글을 작성하려면 로그인해야 합니다.
eulermascheroni99 5년 전 2
안녕하세요, 18793번(팰린드롬 덧셈)을 풀기 위해 Python 3를 이용해 코딩을 하였습니다.
이 문제는 언어와 관계없이 0.5초라는 시간 제한이 주어져있습니다. 그런데 파이썬을 사용하면 이 문제는 사실상 풀 수 없다고 판단되어 문의드립니다.
문제의 T값은 최대 250000까지의 값을 가집니다. 그러나 파이썬에서 꼭 팰린드롬 덧셈이 아니라 단순히 입력을 받아 간단한 함수를 실행시키는 for loop도 250000번의 반복을 하면 이미 0.5초에 근접한 시간이 걸리며 더 복잡한 조건분기가 포함되어있는 이 문제의 경우 0.5초안에 해결하는것이 구조적으로 불가능하다고 생각됩니다.
또한, 본 문제의 핵심은 시간 복잡도를 줄이는 것보단 다양한 조건을 정확히 따져 팰린드롬 decomposition(?)을 잘 수행하는 것에 있는것으로 보입니다. 따라서 시간 제한을 크게 완화시키더라도 문제의 난이도나 의도를 크게 훼손시키지 않을것이라고 생각됩니다. 물론 코드를 필요 이상으로 비효율적으로 짜는것은 막아야겠지만 사용 언어가 주어졌을 때 그에 맞춰 해결 가능한 시간제한이 주어지는것은 꼭 필요하다고 생각합니다.
따라서 이 문제의 시간 제한을 적절히 늘려달라는 부탁을 드립니다. 감사합니다.