32. Tips for exhaustive searching(Brute-force)

완전 탐색 algorithm을 무식하게 만들지 않는, 조금이라도 더 빠르게 돌릴 수 있게 하는 몇 가지 팁.

 

• 불가능한 탐색 공간의 빠른 가지치기
• 대칭성 활용
• 사전 작업, 사전 계산 ~ 공간을 써서 시간을 줄이기
• 문제를 거꾸로 접근(탐색 주체의 선정)
• 소스코드의 최적화
  
  • 빠른 언어: C> C++ > JAVA
  • cin, cout보다는 printf,scanf
  • 힙정렬 보다는 퀵정렬, 힙정렬은 index가 너무 멀리 떨어져있어서 cache의 활용도가 낮다.
  • 2차원 배열에서는 행우선으로 접근
  • 기본 정수 자료형에 대한 비트 연산이 Boolean배열에 대한 bit연산보다 훨씬 빠르다.
  • 가능하면 저차원의 자료구조를 이용하자
  • 거의 모든 자료를 전역으로 두어 한 번만 선언되게 하자
  • 반복/재귀의 갈림길에서는 반복이 낫다. 재귀해는 함수호출의 overhead가 크다.
  • 다중 loop에서 배열에 계속 접근하는 것은 느리다. 임시 변수에 저장해놓고 쓰는 것이 좋을 수도 있다.
  • 매크로/인라인 함수를 적절히 사용하자.
  • C스타일의 문자열 스타일이 string보다 빠르다. (char*쓰자고)
• 적절한 자료구조의 활용