파인만의 문제 해결 방법
- 칠판에 문제를 적는다.
- 골똘히 생각한다.
- 칠판에 답안을 적는다.
위 문제 해결 방벙은 실제 파인만이 한 말이 아니라 라이벌 물리학자가 한 말이긴 하지만, 실제로 저렇게 문제 해결을 했냐 안했냐와는 관계없이 문제 해결의 단계를 다음과 같이 단순화 한 것으로 볼 때 의미가 있다.
- 문제 인식
- 해법 탐구
- 해법의 적용
이를 더 자세히 나누어 보면 다음과 같다.
- 문제의 인식
- 무슨 말을 하고 있는가?
- 내가 아는 말과 방법으로 정리하면 무엇을 하라는 것인가?
- 해법의 탐구
- 계획을 수립한다.
- 계획이 적확한지 확인한다.
- 해법의 적용
- 계획대로 해법을 적용해 결과를 얻는다.
- 개선점이 있는지 검토해본다.
문제 해결 전략
직관과 체계적인 접근
직관
앞서 말한 파인만은 직관에 의한 문제 파악에 뛰어난 사람이었고, 이는 선망과 비난을 동시에 받았던 부분이다. 한눈에 문제를 파악하는 것은 풀이 시간적으로 유리한 면이 있으나 제대로 된 파악인지 검증하는 단계가 중요하다. 또한 팀으로 해결을 하는데 적합한 방법이라고 보기는 힘들다.
체계적인 접근
체계적으로 접근하는 방법. 직관은 타고나는 것에 가까워서 갖기 힘들다. (우리는 파인만이 아니다.)
비슷한 문제를 풀어본 적이 있는가?
가장 기분 좋은 경우. 전에 같은 형식의 문제를 풀어본 적이 있는 것 같다면 일사천리이다. 물론 약간의 다른점이 있는지 반드시 확인해야 한다. 한문장이 달라졌을 뿐인데 통째로 갈아엎어야 할 경우가 있는데, 그럴때는 예전의 경험이 오히려 방해가 될 것이다.
단순한 방법에서 시작할 수 있을까?
브룻 포스로 풀 수 있다면 그것도 풀 수 있는 것이다. 문제를 너무 어렵게 생각하면 아예 해답을 내지 못하는 불상사가 생길 수 있다.
내가 문제를 푸는 과정을 수식화할 수 있을까?
과정에서 수식화를 할 수 있다면 정당한 과정인지 아닌지 파악하기 쉽게 된다. 언제나 가능한 것이 아니더라도 파악하기 쉬운 형태로 요약 정리 하는 것은 반드시 필요하다.
문제를 단순화할 수 있을까?
문제의 제시괸 경우의 수 – 생각할 수 있는 변수를 모두 생각할 필요가 없는 경우, 혹은 단순화 할 수 있는 규칙이 있는 경우가 있다면 이를 통해 많은 연산시간을 절약할 수 있다.
그림으로 그려볼 수 있을까?
말로 쓰여진 것을 보는 것보다 도식화 했을때 파악이 훨씬 쉬운 경우가 많다. 잘 모르겠으면 그림을 그리자.
수식으로 표현할 수 있을까?
수식은 축약과 정의가 매우 쉬운 형태이다. 우리가 알고 있는 공식 형태의 지식을 바로 사용할 수 있다는 점도 강점이며, 문제의 요지와 단순화가 힘든 사람에게도 도움이 될 수 있다.
문제를 분해할 수 있을까?
나누어 정복하기는 복잡한 과제의 기본 전략이다. 과제를 작은 작업 단위로 나누고 보면, 연결하고 나면 별 일이 아닌 경우들이 종종 발견된다.
뒤에서부터 생각해서 문제를 풀 수 있을까?
발상의 전환의 사례로 나오는 것들 중 거꾸로 생각하는 것은 가장 시도해 보기도 좋고, 의외로 통하는 경우도 많은 방법이다. 지금 현재 상태로 될 확률은 과거에는 몇 %인지 몰라도, 지금과 미래 시점에서는 100%이다.
순서를 강제할 수 있을까?
문제의 분해, 단순화와 관련된 개념이다. 문제의 요구 사항이나 조건에 맞춰 행동한다면 순서가 강제된 것이 답인 경우가 있고, 순서를 강제해 경우의 수를 생각해야 할 수도 있다. 그러니 문제를 꼼꼼하게 읽어보도록 한다.
특정 형태의 답만을 고려할 수 있을까?
더 큰 개념으로, 답이 나오는 군을 고려하는 방법이다. 과연 몇가지의 해법이 존재하는지에 대한 깊은 생각에서 도달하는 최적화 방법으로 통한다면 의외로 답을 깔끔하게 정리할 수 있다. 물론 그렇다고 그 답을 구하는 것이 쉬워지는 것은 아니고 답의 개수가 많을 때 / 많아 보일 때 유용한 개념이다.
코딩과 디버깅
좋은 코딩을 하기 위한 원칙
간결한 코드를 작성하라
지금 내가 읽을 수 있더라도 다른 사람이 읽기 힘든 것은 3개월 뒤의 나도 읽기 힘들다. 결국 재사용하기 힘들어진다.
적극적으로 코드 재사용하기
바퀴를 다시 발명할 필요는 없다.
표준 라이브러리 공부하기
우리가 몇 시간에서 몇 일의 시간을 들이더라도 표준 라이브러리의 함수보다 최적화가 잘 되어있는 방식으로 구현하기란 매우 힘들다. 표준 라이브러리 안에서 문제점 없이 / 혹은 타협을 통해 구할 수 있는 경우라면 사용하도록 해야 한다.
항상 같은 형태로 프로그램을 작성하기
방법의 표현법 (실제 코드) 가 바뀐다면 개념과 똑같이 작용할 지 혼란이 생길 수 있다. 결국 문제 풀이라는 것은 시간과의 싸움이므로 불필요한 낭비를 줄이는 차원에서, 검증된 코드 형식으로만 사용한다. 바꿀게 있으면 시작 이전에 바꾸고 검증하자.
일관적이고 명료한 명명법 사용하기
함수명과 변수명을 알아보기 쉽게 정해야 하는 것은 실무에서나 문제 풀이에서나 마찬가지이다. 스스로 실수할 가능성을 높일 이유는 없다.
모든 자료를 정규화해서 저장하기
정보를 담아두고 표현하는 방법을 하나로 정해두지 않으면 함수들을 작성하기 매우 힘들 수 있다. 정규화 과정은 데이터를 입력받는 과정에서 끝마치도록 하자.
코드와 데이터를 분리하기
출력해야 하는 문자열, 배열 등을 다 써주는 것은 코드의 가독성을 떨어뜨린다.
자주하는 실수
산술 오버플로우
알고리즘을 구성했다면 최대 값으로 주어질 수 있는 경우를 계산해 얼마 만큼까지 범위가 커지는지 확인해야 할 필요가 있따.
배열 범위 밖 원소에 접근
C/C++은 배열 범위 밖으로 마음 대로 나갈 수 있기에 항상 주의해야 한다.
일관되지 않은 범위 표현 방식 사용하기
개구간, 폐구간으로 범위가 주어질 때 어떻게 처리할지에 대해 생각하고 적어도 프로그램 내에서는 하나의 방식으로 통일한 뒤 헷갈리지 않도록 계획을 짜야 한다.
off-by-one 오류 : 큰 줄기는 맞으나 하나가 모자라거나 많아서 틀리는 코드 오류.
어쩌면 구간의 표시와 연결되는 개념인데, 맨 처음 요소나 마지막 요소가 빠져서 문제가 틀리곤 한다. 부등호 기호 뿐 아니라 이상/이하과 초과/미만을 잘못 파악해서 생기기도 한다.
컴파일러가 잡아주지 못하는 상수 오타
숫자를 잘못 쓰면 어떻게 할 수가 없다. 패턴으로 생성되는 배열이라면 자동 생성을 하도록 하고, 지정해 주는 중요한 상수는 매크로를 사용해 한눈에 파악할 수 있도록 하는 등의 조치가 필요하다.
스택 오버플로우
공간 복잡도가 큰 문제를 맞이하게 되면 스택 허용량에 부딪히기 쉽다. 스택 허용량을 컴파일 시 늘리거나, 한계를 몇으로 두어야 하는지 생각해 본다. 아니면 STL을 통해 힙으로만 사용하는 것도 방법이다.
다차원 배열 인덱스 순서 바꿔 쓰기
2차원 이상의 배열은 평소에는 쓸 일이 없지만 문제 풀이에서는 다르다. 여러개 쓰다 보면 하나쯤은 인덱스를 틀릴 수 있고, 이는 오답으로 이어진다. 배열의 인덱스 입력을 한 곳에서 처리하는 것으로 어느정도 해결할 수 있다.
잘못된 비교 함수 작성
비교 과정이 어떤 값을 갖는지, 적확한 비교 방법인지 파악해야 할 필요가 있다. 연산자 오버로딩의 경우 오버로딩 규칙에 따라 해당 연산자의 용법을 따라간다는 점도 주의하자.
최소, 최대 예외 잘못 다루기
예외 처리 중 미흡하기 쉬운 부분 중 하나가 최소와 최대이므로 이에 대해 확인해 보는 것이 좋다.
연산자 우선순위 잘못 쓰기
헷갈리면 무조건 괄호를 쓰자.
너무 느린 입출력 방식 선택
때에 따라서는 입출력 시간 소요가 2배 정도 되기도 한다. 미리 사용할 언어와 환경에서 어떤 방법을 사용할 지 파악해 두는 것이 좋다.
변수 초기화 문제
변수의 초기화를 종종 잊기도 하는데, 이는 예제를 반복해 보거나 다른 예제를 추가하는 방법으로 파악해 볼 수 있다. 물론 확인하는 것 보다는 한 차례 끝나면 바로 초기화되도록 주의하는 것이 더 현명한 길일 것이다.
디버깅과 테스팅
디버깅
디버거로 한 줄씩 확인해나가는 방법
눈으로 직접 확인하는 방법
직접 디버깅
작은 입력에 대해 제대로 실행되는지부터 확인
단정문을 쓴다 : 주어진 조건이 거짓일 때 오류를 내고 프로그램을 강제 종료시키는 함수나 구문
프로그램의 계산 중간 결과를 출력한다.
장점 : 대부분 눈으로 직접 확인하여 디버깅이 빠르다, 재귀나 중복 반복문을 디버깅하기 좋다.
디버거 디버깅
런타임 오류를 내고 종료하는 경우, 스택 기록을 출력해주는 경우가 아니라면 디버거 디버깅이 유용하다.
테스트
스캐폴딩 : 코드를 개발할 때 뼈대를 잡기 위해 임시로 사용하는 코드이다.
변수 범위의 이해
산술 오버플로우
오버플로우를 경고해 주는 것은 매우 드물다. 작성 후에는 찾기 힘든 경우가 많으므로 작성시에 철저히 고려해야 한다.
너무 큰 결과
너무 큰 중간값
출력 결과는 표현범위 이내이지만 중간에 그보다 더 큰 수를 사용해야 하는 경우 실수하기 쉽다.
너무 큰 무한대 값
특수값을 설정할 때는 이 특수값들이 더해지거나 곱해질 일이 없는지, 음수 표현 때문에 숫자가 뒤집힐 일이 없는지 미리 고려해야 한다.
오버플로우 피하기
가장 간단한 방법은 더 큰 자료형을 사용하는 것이다. 하지만 점증하는 구조에서 점화식을 이용하는 방법으로 해결할 수 있고 이쪽이 더 구조적이라고 볼 수 있다.
묵시적 형변화
피연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 자동으로 변환해서 계산한다. unsigned int로 int가 묵시적 형변화 되면 지옥을 맛보게 될 것이다.
실수 자료형의 이해
실수와 근사값
컴퓨터에서 실수 자료형은 항상 근사값이다 (2진수로 저장하므로)
오차범위의 설정, 상대 오차, 대소 비교 등의 방법을 통해 실수가 정확한 값이 아니라는 점을 회피할 수 있다.
하지만 가장 좋은 방법은 – 사용을 하지 않는 것이다.