amdid0   1년 전

문제에 그 문제가 필요한 개념은 명시되어 있어야 합니다.

예를 들어 이진수 덧셈을 하는 문제에서는 이진수 덧셈의 알고리즘이 설명되어 있고, mod(나머지 연산)를 문제 개요에 포함한 문제도 mod에 대해 풀어 설명하는 부분이 있습니다.

시간이 T * f(N)의 방식으로 계산된다는 것을 문제에 포함하거나 시간복잡도의 의미를 풀어 설명하는 부분이 있어야 합니다.

jtw7913   1년 전

저것을 찾는 것이 문재의 의도가 아닐까 싶습니다. 

wlaud   1년 전

문제에서 저것을 포함해야 하는 게 맞다고 생각합니다. O(N^2)이 N^2개의 동작을 함을 뜻하지 않을뿐더러 시간 복잡도가 테스트 케이스 하나 기준인지, 채점에 걸리는 시간이 각 테스트 케이스마다 한 동작의 합이 기준인지 최댓값이 기준인지조차 알 수 없습니다.

adfsfsf   1년 전

문제를 읽어보니 설명에서 적은 목적은 시간초과가 나는지 확인하는지 판별하는 것이지만 실제로 원하는 것은 시간초과가 날 가능성이 있는지 확인하는 것이네요.
그러니까 문제 설명이 잘못된 것이라고 봐야 맞겠어요.

원문(해당 문제의 영어 문제)을 보니 'Just assume that applying N to the function in the parenthesis is what gives you the total number of operations your solution will use.'라고 되어 있습니다. 즉, 주어진 N을 실제 Big O 표기식에 넣었을 때 기준으로 답을 출력하라고 명시되어 있는 거에요.
그런데 한글 번역에서는 해당 부분이 빠져서 문제가 모호해졌어요.

저는 크게 2가지만 수정하면 될 것 같아요.
첫째, '각 테스트 케이스마다 입력의 최대 범위 N'이라고 되어 있는 부분을 '각 테스트 케이스의 최대 입력 크기 N'으로 수정해야 합니다. 범위는 오역입니다.
둘째, '테스트 케이스마다 모든 입력의 크기는 테스트 케이스의 N과 동일하다'라고 명시해줘야 합니다.

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