[종만북] 책 내용 정리

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

알고리즘 문제를 푸는 방법

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

1. 문제를 읽고 이해한다
   • 초보~고수까지 문제를 잘못읽는 경우가 다반사
   • 문제의 궁극적인 목적, 사소한 제약조건까지 완벽하게 이해해야함

2. 재정의와 추상화
   • 자신이 다루기 쉬운 개념을 이용해서 자신의 언어로 풀어쓰기
   • 현실세계의 개념을 우리가 다루기 쉬운 수학적/전산학점 개념으로 옮겨 표현

3. 계획 세우기
   • 사용할 알고리즘, 자료구조 선택

4. 계획 검증하기
   • 설계한 알고리즘이 모든 경우에 요구조건을 정확히 수행하는지 증명
   • 수행에 걸리는 시간과 메모리가 문제의 제한 내에 들어가는지 확인

5. 계획 수행하기
   • 정확히 구현하기

6. 회고하기
   • 자신이 문제를 해결한 과정을 돌이켜보고 개선하기
   • 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남겨야 함
   • 문제의 간단한 해법과, 어떤 방식으로 접근했는지, 문제의 해법을 찾는데 결정적이었던 깨달음
   • 한번에 맞추지 못한 경우는 오답 원인도 적는게 좋음
   • 다른 사람의 코드를 보면서 공부하는것도 좋음

문제를 풀지 못할 때

# 직관과 체계적인 접근

• 직관은 해당 문제를 해결하는 알고리즘이 대략 어떤 형태를 가질지 짐작하게 함
• 어려운 문제들은 체계적으로 접근해야 함

1. 비슷한 문제를 풀어본 적이 있던가?
   • 비슷한 문제를 풀어봤으면 이전 방법과 비슷한 접근방법을 사용할 것임
   • 기존 문제를 경험으로 만들려면 원리를 완전히 이해하고 변형할 수 있어야 함
   • 형태가 비슷하지 않더라도 문제의 목표가 같은 경우 또한 이에 소함
   • 어떤 사건의 발생확률/경우의 수를 계산하는 문제는 대부분 동적계획법으로 해결 가능

2. 단순한 방법에서 시작할 수 있을까?
   • 무식하게 풀 수 있을까?
   • 시간과 공간 제약을 생각하지 않고 문제를 해결해봄
   • 점진적인 개선을 통해 알고리즘의 효율성을 증가시킴

3. 내가 손으로 문제를 푸는 과정을 수식화 할 수 있을까?
   • 번뜩이는 영감이 필요한 문제를 만났을때는 다른 방법을 시도해봐야한다.
   • 손으로 여러 간단한 입력(문제에 주어진 예제 입력)을 직접 해결
   • 문제를 해결하는 방법을 공식화해서 답을 만드는 알고리즘을 만들수 있는 경우가 있음
   • 이 과정에서 알고리즘이 어떤 점을 고려해야하는지를 알게됨

4. 문제를 단순화할 수 있을까?
   • 좀더 쉬운 변형판을 먼저 풀어보기.
   • 제약조건을 없애거나, 계산해야하는 변수를 줄이거나, 다차원의 문제를 1차원으로 줄이기도 함

5. 그림으로 그려볼 수 있을까?
   • 관련된 그림을 그려보면 더 쉬움

6. 수식으로 표현할 수 있을까?
   • 평문으로 쓰여있는 문제를 수식으로 표현하는 것도 도움이 됨

7. 문제를 분해할 수 있을까?
   • 문제의 제약조건을 분해할 수 있음

8. 뒤에서 생각해서 문제를 풀 수 있을까?
   • 모든 선택지를 위에서 아래로 내려가 보는 대신에 아래에서 위로 딱 한번만 하면 해결 가능

9. 순서를 강제할 수 있을까?
   • 순서가 없는 문제에 순서를 강제함
   • 경우의 수를 셀 때도 유용함. 특정 조건을 만족하는 답들의 수를 세는 경우

10. 특정 형태의 답만을 고려할 수 있을까?
    • 정규화 기법이 있음
    • 정규화란 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로 똑같은것들을 그룹으로 묶은 뒤, 각 그룹의 대표만을 고려하는 방법

좋은 코드를 짜기 위한 원칙

1. 간결한 코드를 작성하기
   • 가장 간결한 코드를 작성해야 오타나 버그가 생길 가능성이 적다

2. 적극적으로 코드 재사용하기
   • 같은 코드가 세번 이상 등장한다면 해당 코드를 함수로 분리해 재사용한다

3. 표준 라이브러리 공부하기
   • 시간낭비를 줄일 수 있으나 표준적인 알고리즘 구현 사용법을 잘 알아두기

4. 항상 같은 형태로 프로그램을 작성하기
   • 여러 종류의 반복적인 코드들(BFS, 2차원 자료구조 등)은 항상 같은것으로 사용하기

5. 일관적이고 명료한 명명법 사용하기
   • 모호하지 않은 변수명과 함수명을 사용하는 버릇을 들이기
   • 사용하는 언어의 표준 라이브러리에서 사용하는 명명규약을 익히기

6. 모든 자료를 정규화해서 저장하기
   • 같은 자료를 두가지 형태로 저장하지 않기
   • 정규화는 프로그램이 자료를 입력받거나 계산하자마자 곧장 이루어져야 함
   • 이상적으로는 자료를 표현하는 클래스의 생성자에서 정규화를 수행하거나 외부에서 자료를 입력받자마자 정규화를 하는게 좋음

7. 코드와 데이터를 분리하기
   • 정적 데이터 내용을 함수로 따로 만드는 행위를 하지 않기

자주 하는 실수

1. 산술 오버플로
   • 계산 과정에서 변수의 표현범위를 벗어나는 값을 사용

2. 배열 범위 밖 원소에 접근
   • 배열 크기를 정할때 계산을 신중하게 하기
   • 0 시작범위와 1 시작범위 혼동하지않기

3. 일관되지않은 범위표현방식 사용하기
   • [2,12] -> 2~12 까지 자연수 표현, (2,12) -> 3~11까지 자연수 표현
   • 절충안으로 [lo, hi)를 사용함

4. Off-by-one 오류
   • 반복문을 한번 더 많이 순회하거나 열린구간과 닫힌구간을 혼용해서 쓴 경우 많이 발생
   • 입력이 주어졌을 때 코드가 어떻게 동작할지 되새겨보면서 프로그램 짜야함

5. 컴파일러가 잡아주지 못하는 상수 오타
   • 상수를 잘못 입력해서 생기는 오류

6. 스택 오버플로
   • call stack이 오버플로해서 프로그램이 강제종료 되는것
   • 재귀호출의 깊이가 너무 깊어지는게 대개 원인
   • 스택 메모리가 적을때는 힙에 메모리를 할당하는게 좋음

7. 다차원 배열 인덱스 순서 바꿔서 쓰기
   • 특정 배열에 접근하는 위치를 하나로 통일하는것이 좋음

8. 잘못된 비교 함수 작성

9. 최소, 최대 예외 잘못 다루기
   • 예외를 잘 처리해야 한다

10. 연산자 우선순위 잘못 쓰기
    • 시프트 연산자나 비트 단위 연산자들은 종종 헷갈림

11. 너무 느린 입출력 방식 선택
    • gets()로 한꺼번에 받거나 cin으로 고수준 입력방식을 받을수도 있지만 느릴수 있기때문에 잘 선택해야함

12. 변수 초기화 문제
    • 이전 입력에 사용한 전역변수값을 초기화하지않고 그대로 사용함

디버깅과 테스팅

1. 디버깅에 관하여
   • 프로그래밍 대회용 소스코드는 대부분 짧기때문에 눈으로 하는것이 훨씬 빠름
   • 재귀호출이나 중복 반복문을 자주 쓰면 디버깅하기에 힘듬
   • 디버거 사용 대신 해야할 단계
   1. 작은 입력에 대해 제대로 실행되나 확인하기
      • 오동작하는 가장 작은 입력을 먼저 찾아내면 디버깅하기 훨씬 용이함
   2. 단정문을 쓴다
      • 주어진 조건이 거짓일때 오류를 내고 프로그램을 강제 종료시키는 함수 또는 구문
   3. 프로그램의 계산 중간겨로가를 출력한다
      • 중간과정 값들을 출력하고 자신이 예상하는 바와 맞아들어가는지 검사하기
   • 디버거를 사용하는 좋은 예는 프로그램이 런타임 오류를 내고 종료하는 경우

2. 테스트에 관하여
   • 제출 전에 예제 입력을 만들어 가능한 많이 프로그램을 테스트하는것이 좋음
   • 스캐폴딩 방법을 이용해 검증한다.(다른 코드를 개발할때 뼈대를 잡기위해 임시로 사용하는 코드)

변수 범위의 이해

1. 산술 오버플로
   • 어떤 식의 계산값이 반환되는 자료형의 표현 가능한 범위를 벗어나는 경우

2. 너무 큰 결과
   • 프로그램이 출력해야할 결과가 너무 크면 안됨

3. 너무 큰 중간값
   • 계산식 도중에 값이 자료형의 크기를 넘는 경우가 있음

4. 너무 큰 무한대값
   • 무한대 값을 이용해 특수한값으로 사용할때는 무한대값들이 서로 더해지거나 곱해지는 경우가 없는지 잘 살펴봐야함.

5. 오버플로 피해가기
   • 자료형 큰거로 바꾸기
   • 계산 순서 바꾸기
   • 점화식 이용하기

6. 자료형의 프로모션
   • 자료형이 다르거나 자료형의 범위가 너무 작은 경우 컴파일러가 자동으로 변환하는것을 프로모션이라 함
   • 자동으로 형변환되는 숫자들에 대한 주의가 필요함