260828(금)
함수로 케이스 4개를 제대로 판별하는지를 check.py 가 체크하나봐?
-> 케이스 4개가 아니라, 무한한 케이스를 잘 판별해야 수학적으로 완벽한 함수 아닌가?
-> 함수를 작성했는데 반례가 실재함에도 케이스 4개로 걸러내지 못할 수도 있잖아
-> 알고리즘 문제에서 인간이 아니라 기계가 판단하는 것의 근본적인 문제 아닐까?
-> 즉, 귀납적 방법에는 한계가 있다.
[LLM의 답변]
프로그램이 모든 케이스에서 올바르다는 것을 증명하려면 어떻게 해야 할까요?
컴퓨터 과학에서는 2가지 방법이 있습니다.
-
정형 검증(Formal Verification):
테스트 케이스를 돌려보는 게 아니라, 수학적 논리와 명제(Hoare Logic 등)를 사용해
"이 코드는 모든 가능한 입력 s에 대해 수학적으로 팰린드롬을 판별한다"는 것을 증명하는 분야입니다.
항공우주, 원자력 제어, OS 커널 핵심부 등 절대 버그가 나면 안 되는 곳에 쓰입니다. -
수학적 귀납법과 불변식(Invariant):
알고리즘을 짤 때 루프 안에서 항상 참이 되는 조건(Loop Invariant)을 증명합니다.
불변식이 유지됨을 증명하면 모든 케이스를 커버할 수 있게 됩니다.
자동 채점기는 흔히 놓치는 대표적인 Edge Case를 기계적으로 방어했는지를 빠르게 필터링한다.
사람이 직접 검토하기 귀찮은 영역을 시뮬레이션한다.
가능성 있는 반례:
메모리를 터뜨리는 대용량 문자열, 유니코드, 이모지, 기계가 검증할 수 없는 semantic 반례
(언어마다 띄어쓰기나 철자규정이 다를 수 있다. 자연어는 문맥, 악센트, 음소 단위의 팰린드롬을 기계가 검증하기 어려울 수 있다.)
테스트를 통과했다는 건,
작성한 코드가 출제자가 예상한 범주 안의 모든 입력에 대해 정답을 낸다는 뜻일 뿐이고,
"버그가 전혀 없는 완벽한 코드" 라는 수학적 증명이 아니다.
- check.py의 True 표시에 연연하지 마라.
문제를 마주했을 때 메모리와 연산의 흐름을 시뮬레이션하는 능력을 기르세요.
실무에서 맞닥뜨리는 버그나 시스템 설계 문제는
채점기처럼 친절한 테스트 케이스가 없습니다.
알고리즘 문제를 푸는 행위는 내 머릿속의 논리적 허점을 찾아내고 수정하는 훈련을 하세요.
- 완벽을 추구하는 대신 실패 지점을 예측하는 감각을 기른다
내 코드가 어디서 터질지를 먼저 고민하는 방어적 태도
"입력값이 무한대로 커지면(Scale-up)?",
"메모리 한계를 넘어서면?",
"특수문자나 예외 데이터가 들어오면?"
완벽한 프로그램은 존재하지 않습니다.
훌륭한 시스템을 만들기 위해서 반례를 고민하는 과정 자체가 공부
- 알고리즘과 자료구조는 비용(Cost)을 지불하는 방식
모든 알고리즘과 자료구조는 시간과 공간(메모리)이라는
한정된 resource를 어떻게분배할 것인가?라는 문제에 대한 해결.
이 코드는 어떤 비용을 치르고 있는가?를 저수준의 시각으로 바라보아야 합니다.
"이 코드가 맞았는가?" 더 나아가,
"이 코드가 왜 이런 메모리 상태를 만들며, 어떤 제약 조건에서 무너지는가?"
컴퓨터 공학은 추상화의 탑이다.
모든 non-trivial 추상화는 결국 Leaks가 발생한다 (Joel Spolsky)
(추상화는 세부 사항을 감춰주지만, 문제가 생겼을 때 그 밑바닥을 모르면 해결할 수 없다.)
