먼저 문제를 알고리즘 지식으로 풀고
모든 입력에 대해 브루트포스를 돌려서 입력:출력을 저장하고
저장한 입출력으로 입력에 따라 출력을 내놓는 코드를 새로 짜서 내면 TLE 안 걸리는 대신 저격맞으면 죽는 O(1) 코드잖아요
대회에서는 요런거 어떻게 방지해요..? 모든 문제의 입력을 무한으로 잡나요?
모든 입력에 대해 브루트포스를 돌려서 입력:출력을 저장하고
저장한 입출력으로 입력에 따라 출력을 내놓는 코드를 새로 짜서 내면 TLE 안 걸리는 대신 저격맞으면 죽는 O(1) 코드잖아요
대회에서는 요런거 어떻게 방지해요..? 모든 문제의 입력을 무한으로 잡나요?
니가 모르는 입력을 넣지 근데 PS 사이트면 다 그렇게 할건데?
자료형이 정해진 언어들 탓인지 문제들이 주로 입력에 대해 0<N<50000 이런식으로 범위를 제공해서 생긴 궁금증이었어요
모든 문제의 입력은 유한범위 아닌가? 무한범위 입력이 들어올수가 있나? 뭐 제일 간단하게 생각해보면 그런식으로 DB풀이를 못하게 코드 길이 제한이 있겠지
아 코드길이가 있겠군요 감사합니다!
범위가 max(int) 정도 되는 다변수 문제먼 브루트포스 돌리는게 불가능하여 범위가 가산적인 걸 지칭하고자 ”유한한“이었어요
BOJ같은 경우는 따로 문구가 없으면 512kb 제한임. 그래서 50000범위라면 입력 하다망 10바이트밖에 못 쓰니 힘들지 물론 범위가 작은 문제면 님이 말한 풀이가 가능한데, 막 딴사람들 막 수십~수백ms 나오는데 코드길이 길고 0ms 이런 제출이 보인다면 그런 방식으로 푼거임
사실 그렇게 전처리하는게 정해일 수도 있음
재밌는 질문인데, 이론적으로 맞음. 이거 암호학적 엔트로피의 관점으로도 해석해볼 여지가 있는데, 만약 어떤 입력 범위로 주워질 수 있는 값의 경우의 수가 막 100 정도로 매우 적다면, 입력 값을 모르더라도 그냥 미리 100개의 케이스를 구해버리면 되잖음? 이러면 문제의 입력에 대한 엔트로피가 매우 적은거임. 정량적으로 보자면 10비트도 안되는 입력 엔트로피인거지.
백준에서도 입력 엔트로피가 낮은 문제이면서, 코드길이 제한이 없으면, 굉장한 코드 길이의 O(1) 코드가 나오기도 함. 실제로 O(1)이 PS갤 밈이기도 했고. 근데, 보통 문제에서 나오는 문제의 입력은 엔트로피가 굉장히 큼. 당장 상상 가능한건 N을 크게 잡는 문제를 만들거나, N말고도 다른 입력을 넣어서 엔트로피를 많이 늘림. 예를들어 N, M, K가 각각 1000 미만의 값을 가진다고 하면, 순수히 O(1)로 풀려고 할 때 모든 조합으로 다 해봐야 하는거와 같잖음. 문제 유출이 없는이상.
결론적으로 입력이 유한한 이상 O(1)로 풀 순 있는데, 실질적으로 해볼만한 방법은 아님
그리고 모든 입력의 종류가 많지 않으면 그게 통하겠지만 입력의 종류가 좀 많이 커지면 메모리 제한에 걸릴꺼고...
간선 정점 제한이 100 000인 그래프 문제라고 했을 때 입력으로 들어올 수 있는 경우의 수 대충 따져보면 간선을 잇는 방법만 10^12 C 10^6 언저리니 진짜 대충 경우의 수만 (10^6)^(10^6)보다는 큼이 보장됨. 대충 10의 600만승 이상의 경우의 수를 미리 구할 수만 있다면야...
* 100 000말고 1 000 000
사실 2^128만 넘어가도 말도 안되게 큰 수긴 함 ㅋㅋㅋ 결정론적 암호체계에서 안전하다고 여길 수 있는 엔트로피가 128비트이니 그정도만 넘어도 미친거 같음
Nqueen을그런식으로 풀지
런타임 전의 전처리 태그 풀어보면 그 말이 실제 풀이에 이용된다는걸 알게될거임
메모리제한