코딩 테스트 [취미]

분류

풀이 순서

문제를 처음부터 끝까지 순서대로 천천히 읽는다. (문제 조건 놓치면 디버깅으로도 찾을 수 없다.)
- 어디가 중요한지 알 수 없기에 띄엄띄엄 읽지 않는다.
- n번째, i번째 이렇게 적혀서 이해가 되지 않으면 직접 몇 개 넣어본다.
종이노트에 기능 구분 + 제일 최적화 된 자료구조 적기 → 50% 이상의 시간 투자
- 실버문제는 기능 1~2개, 골드문제는 기능 3~4개 정도가 조합되어서 문제의 요구사항이 구현된다.
  - 한 번에 하나씩…!
- 중첩 Dictionary는 절대 지양. Dictionary의 Value가 List나 HashSet은 괜찮다.
  - :links: 링크
복잡도 검사
1. 대강의 Big-O를 파악한다.
2. 상수까지 포함해서 제대로 복잡도를 계산한다.
  - Big-O는 상수를 무시하지만 실전 복잡도에서는 포함하는 게 더 확실하다.
  - Example
    - 이차원 배열 (N * N)이 나오고 N이 50이라고 가정한다.
    - Vertex 탐색은 50 * 50이고, Edge 탐색은 4방향이니까 50 * 50 * 4다.
    - 그러므로 50 * 50 * (1+4) 니까 12,500이 나오고, 이건 2,500(Big-O)와 큰 차이다.
  - 재귀는 특히 조심한다.
    - 재귀의 경우 100회 순회를 재귀로 4번만 타도 10^8이다.
3. 문제는 보통 10^9에서 터지도록 설계된다. 너무 보수적으로 시도를 주저하지는 말자.
4. 이 값이 10^8 이하고, for문 내부에 O(N) 급(ex : LINQ)연산이 없다면 진행한다.
구현
- 두 가지 주석은 적으면서 구현한다.
  - 실수할 여지가 있는 부분에는 //todo
  - 디버깅 시에 도움 줄 내용
- 데이터의 상태와 의미가 헷갈리는 문제라면 필드와 컨테이너의 네이밍을 제대로 짓는다.
  - 디버깅 할 때 대충지으면 다시 풀어야 한다.
- 기능이 복잡하면 무조건 Local Function으로 만든다. Nested Local Function도 허용한다.
  - Local Function으로 만드는 조건
    - 일단 구현할 때 복잡하고 실수 할 것 같으면 만든다. (실수는 쉬운 기능에서 한다.)
      - 어려운 기능이 여러 개일 때는 자연스럽게 기능을 나누어 구현한다.
      - 쉬운 기능은 한 번에 처리하려는 경향이 생기고, 이 과정에서 필연적으로 실수한다.
    - 매개변수에 다양한 인자의 값을 넣어 호출해야 하는 경우는 반드시 메서드로 만든다.
    - 쪼개서 보는 게 가독성 및 디버깅에 유리하면 만든다. (ex : Print Method)
  - Local Function 대신 if-else 사용하는 조건
    - 기능이 2~3줄 정도로 간단하다면 if-else를 사용한다. 현업이면 리팩토링 할 수도 있는.
  - Local Function을 위해 지역변수를 static Main의 가장 큰 scope에 한번에 선언한다.
  - 예시 문제
    - BOJ_17281
      - 복잡하면 local_function
      - 야구 게임 시뮬은 쉽지만 거슬려서 local function으로 뺀다.
    - BOJ_21922
      - 간단하면 if-else