20181028

책 : 알고리즘 문제 해결 전략

자주하는 실수

1. 산술 오버플로
2. 배열 범위 밖 원소에 접근
3. 일관되지 않은 범위 표현 방식 사용하기
4. Off-by-one 오류
5. 컴파일러가 잡아주지 못하는 상수 오타
6. 스택 오버플로
7. 다차원 배열 인덱스 순서 바꿔 쓰기
8. 잘못된 비교 함수 작성
9. 최소, 최대 예외 잘못 다루기
10. 연산자 우선순위 잘못 쓰기
11. 너무 느린 입출력 방식 선택
12. 변수 초기화 문제

디버깅과 테스팅

• 디버깅
  • 작은 입력에 대해 제대로 실행되나 확인하기
  • Aseertion(단정문) 사용
  • 프로그램의 계산 중간 결과를 출력

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

• 계산 복잡도 이론 : 빠른 알고리즘이 존재 한다 = 쉬운 문제
• P 문제 : 다항 시간 알고리즘이 존재하는 문제들의 알고리즘의 집합
• 계산 복잡도 클래스 : 같은 성질을 갖는 문제들을 모아놓은 집합
• NP : 다항 시간 알고리즘이 존재하지 않는 문제들의 집합이 아니다
• 이게 다 대체 무슨말이야
• 마스터 정리
  • 어떤 함수의 수행 시간이 특정 형태로 함수로 표현될 때 이함수의 O()표기법을 쉽게 계산할 수 있도록 도와줌
    참고

알고리즘의 정당성 증명

• 귀납법
  • 단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눈다.
  • 첫 단계 증명 : 그중 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다.
  • 귀납 증명 : 한 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보인다.

• 반복문 불변식 : 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지 명시하는 조건

  • 반복문 진입시에 불변식이 성립함을 보인다.
  • 반복문 내용이 시작할 때 불변식이 성립했다면 내용이 끝날 때도 불변식이 항상 성립함을 보인다.
  • 반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음을 보인다.

    // (*) 불변식은 여기서 성립해야한다
    while(어떤조건) {
        // 반복문 내용의 시작
        ...
        // 반복문 내용의 끝
        //(**) 불변식은 여기에서도 성립해야 한다.
    }

• 귀류법