알고리즘 문제해결 전략

1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할지 계획을 세운다.
4. 계획을 검증한다
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 찾아본다.

체계적인 접근을 위한 질문들

• 비슷한 문제를 풀어본 적이 있던가?
• 단순한 방법에서 시작할 수 있을까?
• 내가 문제를 푸는 과정을 수식화할 수 있을까?
• 문제를 단순화 할 수 없을까?
• 그림으로 그려볼 수 있을까?
• 수식으로 표현할 수 있을까?
• 문제를 분해할 수 있을까?
• 뒤에서부터 생각해서 문제를 풀 수 있을까?
• 순서를 강제할 수 있을까?
• 특정 형태의 답만을 고려할 수 있을까?

좋은 코드를 짜기 위한 원칙

• 간결한 코드를 작성하기
• 적극적으로 코드를 재사용하기
• 표준 라이브러리 공부하기
• 항상 같은 형태로 프로그램을 작성하기
• 일관적이고 명료한 명명법 사용하기
• 모든 자료를 정규화해서 저장하기
• 코드와 데이터를 분리하기

자주하는 실수

• 산술 오버플로
• 배열 범위 밖 원소에 접근
• 일관되지 않은 범위 표현 방식 사용하기
• Off-by-one 오류 (계산의 큰 줄기는 맞지만 하나가 모자라거나 하나가 많아서 틀리는 오류들)
  100미터 담장에 10미터 간격으로 울타리 기둥을 세울때, 10개가 아닌 11개가 필요한것과 같다.
• 컴파일러가 잡아주지 못하는 상수 오타
• 스택 오버플로
• 다차원 배열 인덱스 순서 바꿔 쓰기
• 잘못된 비교 함수 작성
• 최대, 최소 예외 잘못 다루기
• 연산자 우선순위 잘못 쓰기
• 너무 느린 입출력 방식 선택
• 변수 초기화 문제

디버깅과 테스팅

디버깅에 관하여

1. 작은 입력에 대해 제대로 실행되나 확인하기
2. 단정문(assertion)을 쓴다.
3. 프로그램의 계산 중간 결과를 출력한다.

테스트에 관하여

• 스캐폴딩

변수 범위의 이해

• 산술 오버플로
• 너무 큰 결과
• 너무 큰 중간 값
• 너무 큰 무한대 값
• 오버플로 피해가기
• 자료형의 프로모션

실수 자료형의 이해

• 실수 연산의 어려움
• 실수와 근사 값
• IEEE 754 표준
• 실수의 이진법 표기
• 부동 소수점 표기
• 실수 비교하기
• 대소 비교
• 정확한 사칙연산
• 코드의 수치적 안정성 파악하기
• 실수 연산 아예 하지 않기

알고리즘의 시간 복잡도 분석

1. 반복문 1개 = o(N)
2. 반복문 안에 반복문 = o(N^2)
3. 선형시간 알고리즘 = o(N) => 선형 시간에 실행되는 알고리즘은 대개 우리가 찾을 수 있는 알고리즘 중 가장 좋은 알고리즘인 경우가 많다. 주어진 입력을 최소한 한 번씩 쳐다보기라도 하려면 선형시간이 걸릴수밖에 없다.
4. 선형 이하 시간 알고리즘 => 이진탐색 => o(logN)
5. 지수시간 알고리즘
   1. 다항 시간 알고리즘 = 반복문의 수행 횟수를 입력 크기의 다항식으로 표현할 수 있는 알고리즘
   2. 지수 시간 알고리즘 = N이 증가할때마다 걸리는시간이 배로 증가하는 알고리즘?