[알고리즘 문제해결전략 #1] 자주 하는 실수

책 공부하면서 중요하다고 생각되는 부분 정리하고,

내가 자주 쓰는 코드도 정리할 생각이다!

 

이번 주제는 "자주하는 실수 모음"

 

• 산술 오버플로우
  항상 문제 읽을 때 입력으로 들어오는 값의 범위 확인하면서 변수 타입 정하자! 문제 읽으면서 선행해야 할 필수 작업으로 머리에 상기시켜서 실수줄이기
  1) 너무 큰 결과 값
  2) 너무 큰 중간 값
  최소공배수 같은 것들을 계산할 때 중간 계산과정에서 overflow가 일어날 수도 있다! 계산 과정도 확인한기
  3) 너무 큰 무한대 값
  INF값 잡을 때 무턱대고 큰 값 잡지말기 (무한대끼리 계산하다가 오버플로우가 날 수도 있다) 저자가 추천하는 값은 987654321이다! (어쩐지 사람들이 많이쓰더라..)
• 배열 범위 밖 원소에 접근
  - 배열에 입력을 받을 때 인덱스를 1부터 사용할 것인지, 0부터 사용할 것인지 잘 생각하고 문제 풀기
• 일관되지 않은 범위 표현 방식
  1) 닫힌 구간
  [2,12] 같이 표현되는 방식. 범위 내의 첫 번째 값과 마지막 값을 이용해서 해당 범위를 표현하는 방식이다.
  공집합을 표현하기 힘들다는 단점이 있다. 굳이 표현하려면 [3, 2] 이런식으로 앞뒤를 뒤집어서 표현 해야한다.
  2) 열린 구간
  (2, 12) 처럼 표현되는 방식. 3부터 11까지를 포함한다. 첫 번째 값과 마지막 값을 포함하지 않는 표현 방식이다.
  단점은 배열의 첫번째 원소를 표현하려면 음수를 써야하고, 마지막 원소를 표현하려면 가상의 마지막의 마지막(?) 원소를 도입해야 한다는 것이다.
  
  그래서 우리는 자주 반 열린 구간을 이용하는데, C++에서 사용하는 방식이다. begin()은 첫번째 원소를 가르키지만, end()는 마지막 원소가 아닌 가상의 마지막의 마지막 원소를 가르킨다!
• 스택 오버플로
  재귀함수를 깊게 깊게 쓰다보면 스택이 넘쳐서 발생할 수 있는 문제이다. 이런 경우가 아니더라도 지역변수를 크게 잡으면 스택이 금방 넘쳐서 발생할 수 있다. (재귀 잘 안쓰게되던데...)
• 최소 최대 예외 잘못 다루기
  내가 항상 불안해 하는 실수이다. 테스트케이스를 일부만 주고 최종 결과를 모르는 대회나 시험같은 경우에 특히 불안하다. 최대값이나 최솟값에서 히든 테스트케이스가 있을까봐..ㅠ
• 너무 느린 입출력 방식 선택
  입출력이 만개가 넘어가면 우선 입력과 출력에 들어가는 시간을 줄여야한다. 
  백준에 있는 블로그 글을 참고해서 출력 속도가 빠른 순서대로 정리해 보았다. (나는 알고리즘에 C++을 쓰니까 C++만 기준으로 정리함)
  - ios_base::sync_with_stdio(false); cout << i << '\n';
  - ios_base::sync_with_stdio(false); cout.tie(NULL); cout << i << '\n';
  - printf("%d\n",i);
  - cout << i << '\n';
  https://www.acmicpc.net/blog/view/57

출력 속도 비교

• 변수 초기화 문제
  한 문제에서 여러개의 테스트케이스가 있을 때에, 즉 한 번의 실행으로 여러개의 테스트케이스를 검증 받을 때 자주 발생하는 문제이다. 항상 전역변수가 잘 초기화되었는지 확인하자.