sadang_mofun   1년 전

N-Queen 이라는 잘 알려진 문제는 

https://oeis.org/A000170

문헌에서 확인할 수 있듯 이미 계산된 데이터가 있기에 그 결과값을 1~15까지 입력값에 맞춰 출력만 하는 단순한 풀이들이 있는 것을 확인했습니다.

하지만, 10초라는 시간 제한과 메모리 조건에서 완전탐색이 불가능 한 문제로 설계하여 백트래킹을 이용한 경우의 수 가지치기가 필요한 문제라 생각됩니다.

단순히 해당 테스트케이스에 대한 데이터를 출력하기만 한 것도 올바른 풀이가 맞는걸까요

실제 solved.ac의 기여 페이지를 확인해도 백트래킹으로 푼 사람이 많을지 O(1)으로 푼 사람이 많을지에 대한 논란이 있음을 확인 했습니다.

해당 풀이가 옳은 풀이라면 골드 4로 평가되어있는 이 문제가 적절한 레벨일지 의문이 듭니다.

azruine   1년 전

좀 논란이 많을 수 있는 주제이긴 합니다만, 저는 일단 원본 풀이 기준이 맞는거 같아요. 그냥 출력하기만 해도 맞는 것은 어쩔 수 없는 부분이라고 생각해요.

검색을 모든 문제에 적용한다면 레이팅을 유의미하게 매길 수 없다고 생각합니다.

sadang_mofun   1년 전

큰수 a+b와 같이 특정 언어에서는 매우 쉽다는 이유로 티어가 매우 낮게 분류가 된 케이스도 있긴 한데
그 경우에는 언어제한을 걸 수 있겠지만 이런 문제의 경우 막을 수 있는 방법이 쉽진 않겠군요

의견 감사합니다

djm03178   1년 전

원래 모든 문제의 기여는 풀이를 검색하지 않는 것을 기준으로 합니다. 풀이가 쉽게 검색되는 문제에 해결 경고나 레이팅을 주지 않음 처리가 붙기는 하지만, 그것과 난이도를 무엇으로 투표하느냐는 완전히 별개의 사안입니다.

kjk9704   1년 전

이 문제는 엄청 유명한 문제라서 n=1부터 n=14까지의 답이 이미 다 나와있습니다.
하지만 하드코딩으로 문제를 해결하면 n-queen 문제를 변형한 문제를 절대로 풀 수 없을 것입니다.

온갖 수단을 활용해서 경과 시간(저같은 경우는 Python으로 19초~20초)이 좀 많이 걸려도 어떤 알고리즘이 들어갔는지 알아야 해당 알고리즘에 대한 이해도가 증가하고 이로 인해 다른 알고리즘 문제들을 응용해서 문제를 풀 수 있습니다.

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