Competitive Programming 개인 노트

 

저의 CP를 위해 작성한 매뉴얼입니다. 미흡하거나 잘못된 부분이 있을 수 있습니다. 또한 제 실력을 기준으로 하여 작성했으므로 일반적인 사람에게 맞지 않을 수 있습니다.

---

대회 운영

지문 읽기

• 초반에는 쉬운 문제만 읽거나 쉬운 문제를 찾는 것을 목표한다.
• 중반부터는 다이아 3 이하의 해결 가능성이 있는 어려운 문제도 같이 읽는다.
• '지문 잘못 읽음'의 위험성을 간과하지 않는다.

문제 선택

• 초반에는 쉬운 문제만 선택해야 한다.
• 중반에도 우선 쉬운 문제를 선택한다.
• 중반에 쉬운 문제에서 다시 되돌아왔다면 다이아 3 이하의 다른 문제를 선택하는 걸 고려한다.

그 외 관리

• 간식을 먹거나 화장실을 다녀오는 방법으로 멘탈을 관리한다.
• 너무 주눅들지 말자. 나는 어디서도 충분히 1인분 하는 사람이라고 생각하자.
• (팀 대회) 팀원 두 명이 10분 이상 매몰된 문제는 다음 단계를 따른다.
  • 문제를 읽고 30초 정도 고민한다.
  • 팀원에게 지금까지의 관찰을 듣는다.
  • 둘 중 한 명을 이 문제를 그만 보게 한다.
  • 문제를 길게 고민한다.

---

문제 해결

일반론

• 해결할 수 있다는 희망만으로 해결 확률이 올라간다.
• 막히는 것 같다면 의식적으로 이전 단계로 돌아가라.
• 명심하라. 내 두뇌는 아주 좋으며 내 두뇌가 오래동안 찾지 못했다면 애초에 그 방법을 사용해서는 답이 없을 가능성이 높다.

DP

• 제일 먼저 고민해볼만한 방법이다.
• 최대한 다양한 방법의 상태 정의를 시도해보자. (2419번 사수아탕을 떠올려라)
• N 제한이 작다면 다차원 상태 정의도 고려하자.

그리디

• 그리디 문제가 아니더라도 그리디적 사고가 중요하다.
• 항상 이득이 되기보단, 항상 손해를 보지 않는 선택지를 생각하자.

---

코드 작성

전역 변수

• 문제에서 주어지는 중요한 문자는 대문자 전역 변수로 선언한다.
• 대문자로 관리가 안 될 것 같다면 제발 그냥 길게 늘려서 써라.
• 여러 개의 테스트 케이스가 주어지는 문제는 전역 변수 관리를 신경써야 한다.

지역 변수, 구조체 변수

• 변수 작명은 snake_case를 따른다.
• n, m, x, y 등 의미를 알기 쉬운 문자는 한 글자로 선언하고, 의미를 바로 알기 어려운 문자는 길게 선언한다.

함수

• 함수 작명은 snake_case를 따른다.
• 성능 차이가 없다면 함수를 순수 함수로 작성한다.
• 알고리즘의 이름을 제외하고 함수 이름을 축약어로 사용하지 않는다.

템플릿

#include <iostream>
using ll = long long;

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
}

 

---

코드 디버깅

해결법의 문제

• 해결법을 증명했는가?
• 증명에 논리적 비약이 있었는가?

경계 조건의 문제

• 배열 크기를 너무 작게 잡은 건 아닌가?
• 0-index와 1-index를 헷갈린 건 아닌가?
• <와 <=를 헷갈린 건 아닌가?

오타의 문제

• 타입을 잘못 적은 건 아닌가?
• 변수를 잘못 적은 건 아닌가? 이를테면 반복문에서 i가 쓰여야 하는데 다른 전역 변수가 쓰였다거나 하는 경우