[c++] 실수 & 코너케이스(수정 24.03.26.)

맞왜틀인경우 일단 문제를 다시 읽어보자

코너 케이스가 될 수 있는 경우

• 입력 데이터의 최대, 최소
  ex) https://cses.fi/problemset/task/1194/ n, m 이 모두 1
  ex) 0 이 들어갈 때
  ex) 그래프에서 루트만 주어지는 경우
• 뭔가가 없어도 되는 경우
  ex) https://cses.fi/problemset/task/1194/ 몬스터가 없는 경우
• trivial case(코드 돌릴필요 없이 바로 끝나는 경우)
  ex) https://cses.fi/problemset/task/1194/ A가 처음부터 가장자리에 있는 경우
  ex) https://cses.fi/problemset/task/1746/ 빈칸을 채우기 전에 조건에 위배되는 경우
• 이동이 주어진 격자점 밖에서 이루어질 수 있는 경우
  ex) https://www.acmicpc.net/board/view/69162 답이 12가 나오는 케이스(오답은 10)
• 특이한 모양의 트리
  일자 모양 트리에서 dp를 시행할 때, leaf 노드를 edge[node].size() == 1로 판단한다면 root에서 함수가 바로 끝나버린다
  (leaf i.f.f. non-root node with degree 1)

맞왜틀? 인 경우

• 문제 이해 잘못한 경우(조건 하나를 빠뜨린다든지)
  https://tinycaterpillar.tistory.com/244
• 스텍 또버플로우
  • unsigned int 가 음수가 되거나
  • int 곱셈이 있는데 그 수가 커서(10^6 라든지)
    long long을 써야하는 문제면 int 를 쓰지 말자
    경우의 수 문제는 결과값이 long long 일 수도 있다(https://www.acmicpc.net/problem/2143)
    분수 계산 문제의 경우 중간 과정에서 overflow가 일어나기 쉽다(https://www.acmicpc.net/problem/10253)
    파라메트릭 서치에서 mid 뿐만 아니라 검증하는 함수에서 오버플로우 가능(https://tinycaterpillar.tistory.com/252)
  • signed 형은 unsigned 형과 비교연산 시 unsigned로 형변환 됨.
    -1 > 0U → 4294967295U > 0U → true
    
  • STL 자료구조들의 .size() 함수들은 리턴 타입이 unsigned
    -> 음수와 비교했을 때, 올바르지 않게 동작
  • Shift 연산자 오버플로 ex) 1 << 34
    https://www.acmicpc.net/problem/9527
    
• 연산자 우선순위 
  • 비트연산은 우선순위 낮다! (x&1) == 1를 x&1 == 1로 쓴다든지
    비트연산자는 괄호로 감싸자
  • 삼항연산자 cout << (? : ) 괄호 안쓴경우
• 에러
  • -1 % 3  를 양수로 생각하고 푸는 경우
    ((음수 % MOD) + MOD)%MOD 사용하자
  • MOD 연산이 있는 문제에서(주로 dp) 뺄셈을 사용하는 경우
    ((19 % MOD - 5 % MOD) % MOD) 가 항상 양수라고 생각하시나요?? what if MOD = 3??
  • zero division error
  • empty stl에서 뭔가 꺼내거나 지울때
    항상 꺼내거나 지울때는 존재 여부부터 파악하도록 하자
  • 배열의 크기를 넘어서는 호출(UB)
    dp에서 메모이제이션이 먼저 됐는지 확인하고 base조건 따지는 경우 일어날 수 배열의 크기를 넘어서는 호출이 일어날 수 있다
    (https://tinycaterpillar.tistory.com/237)
  • 부동소수점 sqare root 를 사용한 경우(https://www.acmicpc.net/board/view/84475)
  • log2 함수는 컴파일러에 따라 다르게 구동한다(https://codeforces.com/blog/entry/98173)
• 알고리즘(논리) 상 오류
  • 1차원 dp 갱신시 갱신 순서의 문제
    ex) https://tinycaterpillar.tistory.com/230
  • 문제의 그래프가 simple(self loog, parallel edges가 없는 그래프)이 맞는지?(보통 문제에서는 graph가 simple인 경우로 주어지는 경우가 많아서, 당연히 그렇겠거니 하면 안됨)
  • INF, NINF(negative infinite) 를 잘못 설정한 경우(답으로 나올 수 있는 값보다 작게 설정한 경우)
  • dfs 완탐에서 노드 방문을 해제하지 않고 결과(특히 true)를 return 해버리는 경우(https://tinycaterpillar.tistory.com/253)
  • (leaf 노드) == (degree가 1) 으로 생각 할 경우
    (leaf 노드) == (degree가 1 && 노드가 root가 아님)
  • binary search에서 구간 [lo, hi]에 답이 존재하지 않는 경우도 있는데 예외처리 하지 않은 경우
    (https://tinycaterpillar.tistory.com/304)
  • double linked list에서 head의 왼쪽에 tail이 위치할 때
•  문법상 오류
  • 1 <= s[i] <= 1
    파이썬에서는 동작하는데 c++ 에서는 버그임
  • 5//3
    파이썬에서는 정수나눗셈이 // 이다
• 초기화 문제
  • 테스트 케이스가 여러 개 주어지는 문제에서 다른 테스트케이스에서 사용한 배열을 초기화하지 않은 경우
    테케 문제에서는 배열과 변수는 항상 초기화를 먼저 하고 사용하도록 하자(배열은 assign 이용, 전역변수 초기화 까먹지 말것)
• 오타
  • 스펠링이 같은 대문자 변수와 소문자 변수를 동시에 사용하다가 혼동했을 때
    ex) int dp(n, k) { N을 사용 ~ } 

Time limit

• 함수에 container를 전달할 때 레퍼런스& 로 전달하지 않은 경우(이 경우는 주로 Time limit)
• '\n'을 안쓰고 std::endl 쓴 경우(이 경우는 주로 Time limit, interactive문제는 endl을 안쓰면 틀림)
• 빠른 입출력 안했을 때
  ios::sync_with_stdio(false); cin.tie(0);
• DP의 값이 나올 수 있는 값(=DP에 저장될 수 있는 값)이라서 메모이제이션이 의미 없어지는 경우
  DP는 절대 나오지 않는 값으로 초기화 한다
  ex) https://www.acmicpc.net/board/view/119776
• 테스트케이스가 있는 문제에서 각 테케마다 최대 크기의 배열을 선언하는 경우
  쓸 만큼만 배열을 선언하거나, 쓴 만큼만 초기화 할 것