1. 그림은 모든 케이스를 포함하고있지 않으므로, 이해하기 쉽다고 그림을 보고 알고리즘을 짜면 거의 무조건 반례에 걸린다. 문제에서 제시하는 '정의'를 보고 코드로 옮겨야한다. 그림에 현혹되지 말자!
2. 항상 index가 boundary를 벗어나는지( 0보다 작은지, N보다 큰지)를 검사해야한다.
3. 복사 붙여넣기는 가능하면 하지 말자. 붙여넣고 변경할 부분(i, j 가 대표적)을 제대로 변경하지 않으면 디버깅 시에 애를 먹는다. (인간의 심리상 그쪽을 먼저 의심하지 않음)가능하면 직접 타이핑하는 것이 좋다.
4. 격자 순환시에 값이 바뀌는 경우가 있으면 항상 주의해야한다. 해당 좌표 이후 계속 순환이 이어지면 예측할 수 없는 결과가 나타난다. 문자열 순회하면서 수정할 때도 마찬가지.
5. DFS나 BFS 시에 매 stage마다 격자를 새로 만들어야하는지, 아니면 해당 stage가 return 된 후 복구하여 계속사용할 수 있는지를 미리 결정해야한다. boj_19236번 같은 경우, 격자 값이 변경되고 전체 격자가 fishesMove라는 함수에 의해 완전히 뒤섞여버리기 때문에 이를 rollback할 방법이 없으면 무조건 stage마다 새로운 격자를 짜야한다. reference를 받아서 memcopy같은 함수로 복사를 하던가 call by value로 던저주던가
6. 5번과 비슷한 이유로, 격자문제에서 원래 판의 값을 수정하는 경우는 항상 collateral effect를 생각해야한다. 즉, 원래 판에다 수정할지 수정한 것을 기록하는 다른 판을 만들 지 결정해야한다. 특정 처리의 값을 모아놓고 한 번에 판에 적용해야하는 경우에, 각 값을 계산하는 과정에서 판에 미리 적용해버리면 순회 다음 순번 (i, j )에서 영향을 받는다.(BOJ 16235 문제 나무 죽을 때)
7. 맵 순회를 할 때, 굳이 for문으로 전체를 다 볼 필요가 없다. 봐야하는 곳을 vector같은 자료구조에 넣은 다음에 vector를 순회하면서 맵에서 필요한 부분만 확인하는 게 시간 복잡도를 훨씬 줄여준다. (BOJ 17136번)
8. 특정 알고리즘이 opitmal한 해법을 내놓는다는 '확신'이 없으면 완전탐색을 우선 적용하는 게 낫다. 확신이 없을 때에는 optimal함을 증명하기보다 일단 '반례'를 먼저 찾아보자. 그게 훨씬 빠르다.
9. 후속 처리가 필요한 반복 로직에서 continue 사용시 후속 처리 누락되는 것 주의( 특정 격자점 확인해보고 true이면 새로운 logic 적용하고, false인 경우에도 어떤 처리를 해준 후 다음 것 탐색하는 경우)
10. 선입견 버리고 문제 풀기
- BOJ 17281번 야구 게임. 당연히 9이닝인줄 알고 배열 크기 9로 잡아서 런타임 에러)
- BOJ 14500: '회전', '대칭' 모두 다 따져보고 해야함. 지레 짐작으로 회전만 구현하면 틀림. '회전'만으로 대칭 커버 못함
11. 격자 상에서 움직이는 것이 여러 개일 때 코드상으론 순차적으로 이동이지만 실제론 모두 동시에 움직이는 경우를 잘 생각해야한다. 이럴 경우 수정을 원래 판에 미리하면 안되고 새 판에다가 먼저 쓰고 한 번에 적용해야한다
12. row, column 순서 거꾸로 쓰지 않았는지 확인!
13. 격자 순환 시 for문 안에서 i 값을 바꾼다면 항상 조심해야한다. 루프가 끝나고 +1 되는 것을 감안하고, 가능하면 건너뛰기 보다는 모든 격자를 순서대로 순회하면서 자연스럽게 처리되도록 하는 것이 좋다. (에러 확률 줄이고 debug하기 쉬움)
14. 최단 거리가 BFS일 때는, 벽 같은 게 있어서 더듬어 가야할 경우. 그냥 단순 최단거리는 좌표간 단순 계산임.
15. 시간 초과 시에는 Input 제한 크기를 확인해봐야 한다.
16. 직선 이동 시에는 매 칸의 상태를 확인해야 하거나 거리 계산해서 바로 이동하는 것이 좋다.
17. 맵 전체를 확인한 후 true/false를 결정하는 로직은 시간이 생각보다 매우 많이 소요된다. 순회 횟수를 줄이기 위해 이 로직을 매 순회마다 넣는 것은 효율성을 떨어뜨릴 수 있다. (BOJ 17142번)
18. row, column이 1 부터 시작인지 0 부터 시작인지 항상 재확인! (BOJ 19238번)
19. 같은 거리에 있는 것들 끼리 행, 열 번호 우선순위 있을 때, 모아놨다가 sort 쓰거나 우선순위 큐!
20. 문제에 힌트, 주의할 점이 다 있다. 문제를 끝까지 정독해라! (BOJ 19235번)
21. 최대 찾기 초기값은 INT_MIN으로 하자! 0으로 초기화 하면 음수 나오는 경우에 틀림!
22. 퍼지는 것도 꼭 bfs가 답은 아니다!(BOJ 16234번)