알고리즘 문제 해결 전략

[1. 문제 해결 단계]

1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의 한다. (= 재정의와 추상화)
   => 문제를 자신만의 언어로 풀어 써본다.
3. 어떻게 해결할지 계획을 세운다.
   => 사용할 알고리즘과 자료구조를 선택한다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 어떻게 풀었는지 돌아보고, 개선할 방법이 있는지 확인한다.

 

[2. 문제 해결 전략]

1. 직관과 체계적인 접근
2. 단순한 방법에서 시작 할 수 있는가? => 무식하게 풀 수 있는가? => Bruteforce
   => 알고리즘 효율성의 기준선을 정해주는 효과가 있다.
3. 문제 풀이 과정을 수식화 할 수 있는가?
   => 손으로 문제를 풀어보는 습관
4. 문제를 단순화 할 수 있는가?
   => 문제의 좀더 쉬운 변형판?
   => 문제의 제약 조건을 제거해본다.

 

[3. 좋은 코드를 짜기 위한 원칙]

1. 간결한 코드 작성하기
   => 프로그래밍 문제에 한해서는 전역변수를 쓰더라도 잃는 것이 많지 않다.
2. 코드 재사용하기
   => 반복되는 코드를 함수화 시킨다.
3. 표준 라이브러리 적극 사용
   => C++ 기준으로 STL
4. 항상 같은 패턴으로 코드 작성하기
   => ex) while / do~while / for 문 중 가급적 한가지 패턴으로만 반복문 작성
5. 일관적이고 명료한 명명법 사용
   => 함수/변수 이름을 직관적으로
6. 모든 자료를 정규화하여 저장
7. 코드와 데이터 분리

 

[4. 자주 하는 실수]

1. 산술 오버플로
2. 배열 범위 밖 원소에 접근
3. 일관되지 않은 범위 표현 사용
   => STL 은 [a, b) 와 같은 half-open 형태의 범위를 사용하므로, 가급적 같은 형태의 범위를 사용하도록 한다.
   => 장점
        A) empty 구간을  쉽게 표현 할 수 있다. => [2, 2) 는 공집합을 의미함.
        B) 두 구간이 연속해 있는지 쉽게 확인 가능 => [a, b), [c, d) 가 연속하려면 b==c 또는 a==d 를 확인
        C) 구간의 크기를 쉽게 알 수 있다.
4. Off-by-one 오류
   => 하나가 모자라거나 많아서 틀리는 유형
5. Stack overflow
   => 재귀가 너무 깊어지거나 너무 많은 지역변수가 할당 된 경우
   => 자동으로 힙에 메모리를 할당하는 STL Container 또는 전역 변수를 사용하도록
6. 다차원 배열 인덱스 순서 바꿔 쓰기
7. 잘못된 비교 함수 작성
8. 최소/최대 예외 잘못 다루기
9. 연산자 우선순위 잘못 쓰기
   => 괄호를 가급적 많이 쓰도록 한다.
10. 너무 느린 입출력 방식
    => C++ 기준 std::cin / std::cout 대신 scanf / printf 사용 할 것
11. 변수 초기화 문제

 

[5. 디버깅]

눈으로 디버깅하는 쪽이 Line-by-Line 디버깅 보다 훨씬 빠른 경우가 적지 않다.

재귀 호출이나 중복 반복문은 디버깅하기에 적절치 않다.

1. C++ 기준 ASSERT 를 사용하는 것이 바람직 할 수 있음.
2. printf 디버깅

 

[6. 테스트]

스캐폴딩 (= Scaffolding)

임의의 입력을 프로그램적으로 만들어 테스트 해보는 방식

작은 입력에서만 동작하는 더 느리지만 단순한 알고리즘을 사용해 답안을 검증해본다.