Search
Duplicate
🧐

[Python&C] 맞왜틀 이제 그만, 반례 생성기!

간단소개
오늘도 맞왜틀로 고통받고 있는 당신, 반례 생성기 만들어보세요!
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
Problem Solving
Algorithm
Tester
태그
Scrap
8 more properties
아니 그래서 왜 틀렸는데ㅠㅠ 맞왜틀ㅠㅠ
가끔 백준이라던지, 프로그래머스라던지 이런 알고리즘 사이트에서 문제를 풀다 보면 예제도 다 통과했고 다른 사람들이 알려준 반례도 다 통과했는데 도대체 왜 틀렸는지 알 수 없는 문제들이 있습니다. (맞왜틀????)
그럴 때 진짜 답답해서 미쳐버릴 거 같은 심정으로 반례를 찾아 헤매는데 이게 참 찾기가 쉽지 않죠… 그래서 준비했습니다! 반례 생성기!
이 반례 생성기는 백준 1654번 문제를 기준으로 만들었습니다.

예제 생성 함수

우선 example()이라는 예제 생성 함수를 만든 뒤, 문제에 맞춰서 randint()으로 최소 값, 최대 값 주고 예제를 생성하면 됩니다.
원래 1<=K<=10,000, 1<=N<=1,000,000, 랜선의 길이는 <=2,147,483,647인데 그렇게 하면 변수 값이 너무 커지니 임의로 줄였습니다.
python
C

코드 실행 함수

이제 맞은 코드와 틀린 코드를 실행하는 함수를 만들어야 합니다.
맞은 답은 인터넷에서 정답 코드를 구해 만들면 되고, 틀린 답 실행하는 함수에다가 틀린 코드 집어넣어서 만들면 됩니다.
python
C

반례 출력

이제 반례 출력하는 함수를 만들면 끝입니다. ex라는 변수에 예제 생성 함수의 리턴 값을 담고, 그 예제로 맞은 코드와 틀린 코드를 실행하면 됩니다. 만약 둘의 리턴 값이 같을 경우 다시 실행하고, 아니면 반례를 출력하게 했습니다.
python
C

전체 코드

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()
Python
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); }
C
알고리즘 공부 파이팅!!!