안녕하세요, 18793번(팰린드롬 덧셈)을 풀기 위해 Python 3를 이용해 코딩을 하였습니다.

이 문제는 언어와 관계없이 0.5초라는 시간 제한이 주어져있습니다. 그런데 파이썬을 사용하면 이 문제는 사실상 풀 수 없다고 판단되어 문의드립니다.

문제의 T값은 최대 250000까지의 값을 가집니다. 그러나 파이썬에서 꼭 팰린드롬 덧셈이 아니라 단순히 입력을 받아 간단한 함수를 실행시키는 for loop도 250000번의 반복을 하면 이미 0.5초에 근접한 시간이 걸리며 더 복잡한 조건분기가 포함되어있는 이 문제의 경우 0.5초안에 해결하는것이 구조적으로 불가능하다고 생각됩니다.

또한, 본 문제의 핵심은 시간 복잡도를 줄이는 것보단 다양한 조건을 정확히 따져 팰린드롬 decomposition(?)을 잘 수행하는 것에 있는것으로 보입니다. 따라서 시간 제한을 크게 완화시키더라도 문제의 난이도나 의도를 크게 훼손시키지 않을것이라고 생각됩니다. 물론 코드를 필요 이상으로  비효율적으로 짜는것은 막아야겠지만 사용 언어가 주어졌을 때 그에 맞춰 해결 가능한 시간제한이 주어지는것은 꼭 필요하다고 생각합니다. 

따라서 이 문제의 시간 제한을 적절히 늘려달라는 부탁을 드립니다. 감사합니다.

dxdydz   5년 전

어떤 문제가 백준에서 사용 가능한 모든 언어로 해결 됨이 보장돼야 할 이유는 없습니다.

djm03178   5년 전

어떤 언어가 가진 장점들을 활용할 수 있는 만큼 그로 인한 페널티도 당연히 감수해야 합니다. 파이썬이 느린 것은 그만큼 프로그래머에게 많은 편의를 제공하기 때문도 있습니다. 이미 BOJ는 대부분의 문제에 대해 느린 언어들에 대한 배려로 보너스 시간을 부여하고 있는데, 이는 기본적으로 이 사이트가 연습을 목적으로 쓰인다는 점을 감안한 것이며 모든 문제에 대해 모든 언어로 풀리게 해주겠다는 뜻은 아닙니다. 이 문제와 같이 출제자가 다른 언어에 대한 '관대함'을 원하지 않았다면 그 의도를 존중해주는 것이 맞다고 생각합니다.

애초에 BOJ의 문제 중에는 제출할 수 있음에도 해결이 아예 불가능한 언어가 있는 경우가 많습니다. Text만 해도 그렇고, 아희를 비롯한 일부 난해한 프로그래밍 언어들은 파이썬보다도 훨씬 느려서 보너스를 아무리 많이 줘도 절대 시간 내에 해결이 안 되는 문제들도 많습니다. 이런 언어들을 모조리 배려해주거나 아니면 문제마다 하나하나 제한 필터를 건다는 건 현실적이지도 않습니다.

cozyyg   5년 전

참고로 이 문제에 제출 가능한 언어 중에 PyPy3가 있습니다. Python 3보다 빠를테니 한 번 시도해보세요. PyPy3조차도 시간 초과가 난다면... 좀 슬프겠네요.

jiminp   5년 전

물론 모든 문제가 파이썬을 배려해 줄 필요가 없는 것은 맞지만, 만약 이 문제에 디폴트 시간 보정(x3+2)이 걸렸었다면 PyPy3으로는 통과가 가능할 것으로 보입니다.
오답 대비 정답의 실행 시간이 압도적으로 짧은데 시간 보정이 걸리면 오답도 통과가 되어서 시간 보정을 빼는 것이라면 모를까, 첫 작성자님 말처럼 이 문제에는 그러한 오답이 있는 것도 아닙니다.

이것만이면 그려러니하고 넘어갈 수 있는데, 이 문제에 명시적으로 제출 가능한 언어 제한이 걸려 있고 그 언어에 파이썬이 포함되어 있는 것도 문제입니다.
입출력 시간 때문에 풀지 못하는데 사용 가능한 언어 제한에 파이썬이 있는게 불합리하게 느껴집니다.

따라서 다음 세 가지 중 한 가지를 제안합니다.

  • "추가 시간 없음" 삭제
  • "제출할 수 있는 언어" 제한 삭제
  • "제출할 수 있는 언어" 제한에 파이썬 (Python/PyPy 2/3) 삭제, 테스트 뒤 자바도 삭제 고려

cozyyg   5년 전

이 문제에 추가 시간을 주지 않은 이유에 대해 생각해보자면, 약간의 잘 최적화된 백트래킹 등의 방법이 있더라도 그걸 최대한 막기 위해서라고 생각합니다. 모든 경우를 잘 커버할 수 있는 case work로 문제를 푸는 것이 정해라는 것이죠. 제가 아는 바에 따르면, 오답 대비 정답의 실행 시간이 압도적으로 짧을 수 있습니다(작은 수에 대한 케이스 워크 부분). 이에 따르면 시간 보정을 안 해주는 것이 전혀 문제가 없다고 생각합니다. 실제로 Python이나 Java가 시간 보너스로 오히려 이득을 보는 문제들도 있고, 이로 인해 "Python에서 naive solution이 통과 / Java에서 naive solution이 통과" 같은 사례들이 실제로도 있었습니다. (TMI: 이 주제는 구데기컵 문제로도 다루어진 바 있습니다.)

설령 이 문제가 C++로만 풀 수 있는 문제라 하더라도, 어쩔 수 없다고 생각합니다. 그게 이 문제의 컨셉이나 아이덴티티가 될 수 있겠죠. 언어 제한에 파이썬이 포함된 건 파이썬으로 풀 수 있는지랑은 관련 없다고 생각합니다. 이런 상황이 바람직한가? 에 대해서는 의견차가 있을 것이라 생각합니다만, 그게 싫다면 이 문제를 안 풀면 됩니다... 이 문제는 well-defined된 문제며, 여러 사람들이 풀어서 검수된 문제입니다. 현재 상태로도 아무 문제 없습니다.

이 문제의 출제자 역시도 추가 시간을 안 주는 현재 방향을 바꿀 생각이 없을 것 같으며, 아직 이 문제를 풀지 않은 저의 의견 역시도 이 문제에 추가시간이 있을 필요는 없다고 생각합니다. 정말 이 문제를 파이썬으로 풀 수 없을까요? 가능하다면, 그리고 제가 시간적인 여유가 좀 많이 남게 된다면, 여러분들의 생각을 깨드리도록 하겠습니다.

jiminp   5년 전

제가 파이썬 입출력을 최적화하는 방법에 대해 잘 모르긴 하지만, 아래 코드처럼 입출력을 하면 PyPy3으로 타임아웃이 뜹니다.
이거보다 더 나은 입출력 방식이 없다면 제 생각에 파이썬으로 통과는 어렵지 않을까 싶습니다.

참로고 같은 코드를 C++로 바꿔서 내면 128ms로 통과합니다. 직접 해 봤습니다...

djm03178   5년 전

입출력 문제라고 단정할 수 있나요? 두 개의 케이스가 있는데 첫 번째 케이스는 시간 내에 통과할 수 있는 데이터고 두 번째는 출력 부분을 제외하더라도 시간 내에 동작하지 않는다면 출력 부분을 지웠을 때 틀렸습니다가 뜨게 되는 것이 맞습니다. 첫 번째 케이스에서 오답이 나왔기 때문에 더 오래 걸리는 두 번째 케이스에서 시간 안에 도는지 확인할 길이 없습니다.

cozyyg   5년 전

  • PyPy3에서는 join이 더 느릴 수 있습니다. https://www.acmicpc.net/blog/v... 에 따르면, for c in range((l+1)//2): stdout.write(base_str[c])가 더 빠르다고 합니다. 문자열이라서 좀 다를 수도 있겠습니다.
  • 입출력 속도만이 문제인 건 아닐 수도 있겠죠. if문을 최소한으로 거치게 하는 "똑똑한 조건 분기 로직" 역시도 최적화 가능한 영역이라고 봅니다.

jiminp   5년 전

문제 푸는 방법이 방법인지라 코드가 천 줄이 넘어가서 제가 미처 못 보고 지나친 게 있을 수도 있고, 제가 파이썬 최적화에 경험이 부족해서 틀릴 가능성도 있습니다.

그래도 다음과 같은 이유 때문에 전 그렇게 단정지으려 합니다. 제가 틀렸다면 뭔가를 배울 좋을 기회가 되겠죠...

  • 앞서 언급했듯, 같은 로직을 C++로 옮겨서 풀면 통과합니다. 문제 풀이에 영향을 주는 로직 문제일 가능성은 전무합니다.
    • 파이썬 코드 짤 때 별다른 선택의 여지가 없어서 곧이곧대로 짰습니다.
    • C++ 코드 만들 때에도 상황은 똑같아서 파이썬 코드를 복붙한 다음 문법 수정하고 모듈러 연산 수정한 정도로 고치는 식으로 만들었습니다.
  • 입출력을 제외한 코드 자체의 모든 루프는 다음과 같습니다. 이 이외에는 전부 사칙연산, 분기문과 함수 호출 뿐입니다.
    • Algorithm I~IV의, input의 절반 길이만큼 루프 돌면서 세 palindrome에 대한 임시 솔루션 구하기 (테스트 케이스당 최대 한 번)
    • Algorithm V의, input의 절반 길이의 임의 정밀도 숫자에서 11을 빼는 루프 (테스트 케이스당 최대 두 번, carry = 0인 순간 break함)
    • 최대 6자리의 동일한 자릿수의 두 숫자에 대해 뺄셈을 계산 (테스트 케이스당 아마도 한 번, 많아봐야 세 번)
    • 6자리 숫자의 일부 경우에 대해, 절댓값이 {입력 진법} 정도인 정수를 계산하고 {입력 진법}으로 나눈 값이 특정 두 값인지 여부 검사 (테스트 케이스당 최대 세 번)
  • 사용하는 함수는 매우 적으며, 많아봐야 두 세번 꼭 필요한 만큼만 불려집니다. 입출력을 제외하고는 루프를 위한 range만 사용되며, int, str을 포함한 내장함수조차 사용하지 않습니다.
    • 각 팰린드롬의 첫 자리와 길이를 정하는 함수, 메인 solve 함수, Algorithm I~V, 작은 케이스에 대한 함수, 최대 6자리의 동일한 자릿수의 두 숫자 빼기
  • 불필요한 연산은 하지 않습니다.
    • 입력, 정답은 global한 배열을 미리 만들어두고 사용하고 있으며, 복사되지 않습니다.
      • 처음 코드 짤 때의 흔적으로 인해 함수별로 입력값의 reference를 건네주긴 하지만, 복사되지 않습니다.
    • 처음에 제출할 때에는 문자열을 복사하거나 배열에 뭔가를 append/pop하는 연산을 한 코드를 제출했습니다만, 전부 제거해보고 제출해도 그대로 타임아웃 뜹니다.
    • 몇 가지 예외가 있으나 실행시간에 큰 영향을 주지는 않습니다.
      • 뺄샘 계산 함수에서 최대 6자리의 list를 만들어서 인자로 건네줍니다.
      • 코드를 간단히 적기 위해 (l1, l2, l3) = (1, 1, 1)과 같은 unpack assign을 자주 사용하며, 두 가지 상수 값이 들어있는 tuple에 대한 in 연산도 몇 번 씁니다.

제가 생각할 수 있는 가능한 최적화 여지는 몇 가지 조건을 중복 체크하는 것을 줄이는 것, in 연산을 두 개의 ==로 바꾸는 것이나 수식 최적화 (mod 연산을 조건문으로 바꾼다던가) 정도인데, 이 정도로 시간 초과 날 만한 코드가 통과될 코드로 바뀔 것 같지는 않습니다.

jiminp   5년 전

게다가, 다른 글의 댓글로도 달긴 했는데 시간초과가 뜨는 코드에서 출력만 전부 제거하면 틀렸습니다가 뜹니다.

그 상태에서 코드 마지막에 while True: pass를 붙이면 시간 초과가 뜨고요. (무한 루프를 돌면서 잘못된 값을 출력해서 "틀렸습니다"가 뜨는 건 아니라는 근거입니다.)

심지어 출력값 string을 만든 뒤 전부 한 list에 담아도 출력하려고 하면 시간초과, 출력하지 않으면 틀렸습니다가 뜨네요...

cozyyg   5년 전

뭐... 이런 문제에 너무 과몰입하지 않는 거로...

djm03178   5년 전

우선 제 생각으로는 입출력만으로 0.5초가 넘지는 않을 것 같습니다.

http://boj.kr/48fcf5525be74389...

이 문제의 입출력 양은 각각 최대 약 700만 자로, 이 문제에서의 최대 입력량의 1/5 정도이며, 출력량도 반 정도에 불과합니다. 정렬 시간 역시 무시할 수 없 약 0.4초 안에 실행될 수 있을 거라고 생각할 수 있습니다.

제가 말씀드린 게 그 다른 글의 댓글로 다신 걸 보고 말씀드린 건데, 말씀하신 것만으로는 그 원인이 입출력 때문이라고 단정할 수가 없습니다. 말씀드렸듯이, 출력을 제거한 상태에서 시간 내에 실행이 되는 입력을 넣었다면 오답(아무 답을 출력 안 한 것)을 출력했으니 틀렸습니다로 나오게 됩니다. 마지막에 무한 루프를 넣으셨다면 무한 루프에 걸려 시간을 초과했으므로 답에 대한 판정 자체를 하지 않을 것이니 시간 초과가 나올 것이고요. 정상적으로 출력했을 때 그 케이스를 통과한 뒤, 다음 케이스를 실행했는데 그게 너무 오래 걸리는 케이스여서 시간 초과가 난 것일 가능성을 배제할 수 없습니다.

djm03178   5년 전

제가 직접 테스트를 해봤습니다.

이 문제에서 나올 수 있는 최대 입력량을 생각해서 입력은 25만 개 케이스에 매 케이스마다 "62 abcd"를 입력으로 주고, 출력으로는 9999 9999 9999가 케이스 수만큼 출력되도록 아래와 같이 짜봤습니다. 그러고 stack.acmicpc.net에서 실행했을 때 232ms가 나왔습니다.

jiminp   5년 전

제가 보기에는 지금 입력 + 알고리즘을 돌리는 시간 단독이나, 출력만에 걸리는 시간으로는 0.5초 이내에 돌아갈 수 있으나, 둘을 합치면 0.5초가 넘어가는 케이스인 것 같습니다.

다만 이 문제의 경우 절반을 출력하는 것은 맞으나 입출력에 추가적인 처리(자리수<->문자열 변환)를 하고 있는데, 지금 그 과정에서 완전히 최적화가 이루어졌다고 자신있게 말할 수는 없기 때문에 제가 틀렸을 여지는 있습니다...

첫 번째 테스트 케이스를 통과했는데 다음 테스트 케이스에서 시간 초과가 뜨는 경우의 가능성이 없지는 않은데, 여러 정황상 가능성은 좀 낮게 보고 있습니다. (파이썬으로 퍼센트가 올라가는 것을 본 적이 없다던지 등...)
그런 케이스를 배제할 수 없다는 것은 알겠습니다.

jiminp   5년 전

저게 232ms가 걸렸다면 대단히 빡빡해 보이네요;;;

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