가끔 문제를 풀다 보면 예제도 다 통과했는데 도대체 왜 틀렸는지 알 수 없는 문제들이 있다. (왜맞틀?????) 그럴 때 진짜 답답해서 미쳐버릴 거 같은 심정으로 반례를 찾아 헤매는데 이게 찾기 쉽지 않다. 그럴 때는 반례 생성기를 만들어서 찾으면 된다.
이 반례 생성기는 백준 1654문제를 기준으로 만들었다.
1. 예제 생성 함수
우선 example()
이라는 예제 생성 함수를 만든 뒤, 문제에 맞춰서 randint()
으로 최소 값, 최대 값 주고 예제를 생성하면 된다.
원래 1<=K
<=10,000, 1<=N
<=1,000,000, 랜선의 길이는 <=2,147,483,647인데 그렇게 하면 변수 값이 너무 커지니 임의로 줄였다.
def example():
K = randint(1, 10)
N = randint(K, 20) # K <= N
lines = [0] * K
for i in range(K):
lines[i] = randint(1, 1000)
return [K, N, lines]
2. 맞은 답 & 틀린 답 실행하는 함수
이제 맞은 코드와 틀린 코드를 실행하는 함수를 만들어야 한다.
맞은 답은 인터넷에서 정답 코드를 구하면 되고, 틀린 답 실행하는 함수에다가 틀린 내 코드 넣어서 만들면 된다.
def right_sol(K, N, lines):
s = 1
e = max(lines)
res = 0
while s <= e:
cnt = 0
m = (s+e)//2
for i in lines:
if i >= m:
cnt += i // m
if cnt < N:
e = m - 1
else:
res = m
s = m + 1
return res
def wrong_sol(K, N, lines):
s = 0
e = max(lines)
res = 0
while s <= e:
cnt = 0
m = (s+e)//2
for i in lines:
if i > m:
cnt += i // m
if cnt < N:
e = m - 1
else:
res = m
s = m + 1
return res
3. 반례 출력
이제 반례 출력하는 함수를 만들면 끝이다. ex
라는 변수에다가 예제 생성 함수의 리턴 값을 담고, 그 예제로 맞은 코드와 틀린 코드를 실행하면 된다. 만약 둘의 리턴 값이 같을 경우 다시 실행하고, 아니면 반례를 출력하게 했다.
def check():
ex = example()
right = right_sol(ex[0], ex[1], ex[2])
wrong = wrong_sol(ex[0], ex[1], ex[2])
if right != wrong:
print(ex[0], ex[1])
for i in ex[2]:
print(i)
print("맞은 답:", right)
print("틀린 답:", wrong)
return
else:
check()
전체 코드
Python
from random import randint
# 예제 생성
def example():
K = randint(1, 10)
N = randint(K, 20)
lines = [0] * K
for i in range(K):
lines[i] = randint(1, 1000)
return [K, N, lines]
# 맞은 답
def right_sol(K, N, lines):
s = 1
e = max(lines)
res = 0
while s <= e:
cnt = 0
m = (s+e)//2
for i in lines:
if i >= m:
cnt += i // m
if cnt < N:
e = m - 1
else:
res = m
s = m + 1
return res
# 틀린 답
def wrong_sol(K, N, lines):
s = 0
e = max(lines)
res = 0
while s <= e:
cnt = 0
m = (s+e)//2
for i in lines:
if i > m:
cnt += i // m
if cnt < N:
e = m - 1
else:
res = m
s = m + 1
return res
# 반례 출력
def check():
ex = example()
right = right_sol(ex[0], ex[1], ex[2])
wrong = wrong_sol(ex[0], ex[1], ex[2])
if right != wrong:
print(ex[0], ex[1])
for i in ex[2]:
print(i)
print("맞은 답:", right)
print("틀린 답:", wrong)
return
else:
check()
check()
C
#include <stdio.h>
#include <stdlib.h>
int K, N;
void example(void)
{
K = rand() % 100;
N = rand() % 100;
}
int incorrect(int K, int N, int lines[])
{
int start, end, res, mid;
start = 1;
end = 1;
while (1)
{
res = 0;
mid = (start + end) / 2;
for(int i = 0; i < K; i++)
{
res += (lines[i] / mid);
}
if (res < N)
end = mid - 1;
else
break ;
}
return (0);
}
int correct(int K, int N, int lines[])
{
int res;
int max;
long long int start = 1;
long long int end = 1;
long long int mid = 1;
while (1)
{
res = 0;
mid = (long long int)((start + end) / 2);
for(int i = 0; i < K; i++)
{
res += (lines[i] / mid);
}
if (res < N)
end = mid - 1;
else
{
max = mid;
start = mid + 1;
}
if (start > end)
break ;
}
return (max);
}
int main(void)
{
int right;
int wrong;
example();
int lines[K];
for(int i = 0; i < K; i++)
{
lines[i] = rand() % 100;
}
right = correct(K, N, lines);
wrong = incorrect(K, N, lines);
while (right == wrong)
main();
printf("예제: K = %d, N = %d\n", K, N);
printf("lines: ");
for(int i = 0; i < K; i++)
{
printf("%d ", lines[i]);
}
printf("\n");
printf("맞은 답: %d\n", right);
printf("틀린 답: %d\n", wrong);
return (0);
}
엄청 어려운 것도 아닌데 왜 지금까지 이런 걸 만들 생각을 못했는지 모르겠다. 허허... 이제 만들어 놨으니 요긴하게 써먹어야지!
'알고리즘 PS > 알고리즘' 카테고리의 다른 글
[Python] DFS & BFS (0) | 2022.03.19 |
---|---|
[Python] 이분/이진 탐색 (0) | 2022.03.02 |
[Python] 그래프 (인접 행렬, 인접 리스트) + DFS/BFS를 배우기 앞서 알아야 할 개념들 (탐색 알고리즘, 자료구조) (0) | 2022.01.30 |
[Python] 백트래킹 (+ DFS와 차이) (6) | 2022.01.18 |
[Python] 다이나믹 프로그래밍 (DP) (0) | 2022.01.15 |
댓글