프로그래밍 대회에서 배우는 알고리즘 문제해결전략 1장

2. 문제 해결 개관

파인만의 문제 해결 방법

- 칠판에 문제를 적는다. 

- 골똘히 생각한다.

- 칠판에 답안을 적는다.

문제 해결의 고전 HOW TO SOLVE IT?

- 문제를 이해한다.

- 어떻게 풀지 계획을 세운다.

- 계획을 수행해서 문제를 해결한다.

- 어떻게 풀었는지 돌아보고, 개선할 ㅅ방법이 있는지 찾아본다.

파인만과 HTS를 합한 알고리즘

- 문제를 읽고 이해하기

- 재정의와 추상화 : 자신이 다루기 쉬운 개념을 이용하여 문제를 자신의 언어로 풀어쓴다.

- 계획 세우기

- 계획을 검증하기

- 계획 수행하기 : 위 과정을 거치고 계획을 수행, 프로그램을 작성한다.

- 회고하기 : 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 확인한다.

문제 해결 전략

- 직관과 체계적인 접근

직관 : 해당 문제를 해결하는 알고리즘이 대략적으로 어떤 형태를 가질지 짐작할 수 있게 해준다.

체계적인 접근 : 백지에서부터 시작해 문제를 해결하기 위한 기반을 쌓아올리고 점진적으로 접근하는 것을 의미한다.

> 비슷한 문제를 풀어본 적이 있는가?

> 단순한 방법에서 시작할 수 있을까?

> 내가 문제를 푸는 과정을 수식화할 수 있을까?

> 문제를 단순화할 수 있을까?

> 그림으로 그려볼 수 잇을까?

> 수식으로 표현할 수 있을까?

> 문제를 분해할 수 있을까?

> 뒤에서부터 생각해서 문제를 풀 수 있을까?

> 순서를 강제할 수 있을까?

> 특정 형태의 답만을 고려할 수 있을까?

3. 코딩과 디버깅에 관하여

좋은 코딩을 하기 위한 원칙

- 간결한 코드를 작성하라 : 코드가 간결할수록 단순한 버그가 생길 우려가 줄어들고 디버깅이 쉬워진다.

- 적극적으로 코드 재사용하기

- 표준 라이브러리 공부하기

- 항상 같은 형태로 프로그램을 작성하기

- 일관적이고 명료한 명명법 사용하기

- 모든 자료를 정규화해서 저장하기

- 코드와 데이터를 분리하기

자주하는 실수

- 산술 오버플로우

- 배열 범위 밖 원소에 접근

- 일관되지 않은 범위 표현 방식 사용하기

- off-by-one 오류 : 큰 줄기는 맞으나 하나가 모자라거나 많아서 틀리는 코드 오류.

- 컴파일러가 잡아주지 못하는 상수 오타

- 스택 오버플로우

- 다차원 배열 인덱스 순서 바꿔 쓰기

- 잘못된 비교 함수 작성

- 최소, 최대 예외 잘못 다루기

- 연산자 우선순위 잘못 쓰기

- 너무 느린 입출력 방식 선택

- 변수 초기화 문제

디버깅과 테스팅

디버깅

- 디버거로 한 줄씩 확인해나가는 방법

- 눈으로 직접 확인하는 방법

직접 디버깅

- 작은 입력에 대해 제대로 실행되는지부터 확인

- 단정문을 쓴다 : 주어진 조건이 거짓일 때 오류를 내고 프로그램을 강제 종료시키는 함수나 구문

- 프로그램의 계산 중간 결과를 출력한다.

- 장점 : 대부분 눈으로 직접 확인하여 디버깅이 빠르다, 재귀나 중복 반복문을 디버깅하기 좋다.

디버거 디버깅

- 런타임 오류를 내고 종료하는 경우, 스택 기록을 출력해주는 경우가 아니라면 디버거 디버깅이 유용하다.

테스트

- 스캐폴딩 : 코드를 개발할 때 뼈대를 잡기 위해 임시로 사용하는 코드이다.

변수 범위의 이해

- 산술 오버플로우 : 어떤 식의 계싼값이 변환되는 자료형의 표현 가능한 범위를 넘어가는 경우

- 너무 큰 결과 : 큰 정수를 다룰 때는 항상 변수의 형태에 주의하는 습관을 길러야 한다.

- 너무 큰 중간값

- 너무 큰 무한대 값

- 오버플로우 피하기 : 더 큰 범위의 자료형을 사용하 ㄹ것

- 자료형의 프로모션 : 피연산자의 자료형이 다르거나 자료형의 범위가 너무 작은 경우 자동으로 변환해서 계산

실수 자료형의 이해

- 실수와 근사값 : 컴퓨터의 모든 실수 변수는 정확도가 제한된 근사값을 저장하기 때문에 정확한 실수 값을 담을 수 없다.

- IEEE 754 표준이 가장 많이 사용되는 실수 표기 방식