코딩테스트 기본지식

📚 코딩 테스트 잘할려면

• 알고리즘 문제 푸는 과정에서 요구되는 요소들
  1. 📖 독해력 : 문제를 빠르고 정확하게 파악
  2. 🔧 배경지식 : 필수 자료구조, 알고리즘 지식들
  3. 💡 문제해결력 : 솔루션, 아이디어
  4. 📝 구현력 : 코드 작성 능력
  5. ✅ 검증, 디버깅 : 틀렸을 경우, 틀린곳, 반례 찾기
• Step by step
  • 필수 자료구조, 알고리즘 훑어보기
  • 문제해결력 키우기
  • 구현력 키우기

📚 코딩 테스트 채점 기준

• 문제마다 존재하는 제한 조건
  • 시간제한 : 시간복잡도
  • 메모리 제한 : 공간복잡도

시간복잡도 (Time Complexity)

• 알고리즘의 성능을 나타내는 척도

• Big-O notation으로 나타낸다

• 주먹구구 계산법
  • C++ 1초에 총 연산 1억번이 넘어가면 위험하다 ‘1초 = 1억’을 기억하자!
  • 보통 k중 for문 = $O(N^k)$
  • (정확한 셈법은 아니다.)

공간복잡도 (Space Complexity)

• N에 비례해서 메모리 얼마나 쓰는지 나타냄
• 일반적으로 성립하는 trade-off 관계 : 💾 메모리(공간) <-> ⏱️ 시간
• 주로 시간을 먼저 생각

예시

• 문제 : 시간제한 2초, 메모리제한 64MB
• 입력 : $0 \leq N \leq 100,000,000$

• 이 문제에서 가능한 시간/공간 복잡도는 어떤 것들이 있을지?

  📚 코딩테스트 기본지식

• 변수, 함수, 배열, 반복문, 조건문, 문자열 등을 주로 사용
• 상속, 포인터등은 거의 쓰지 않음
• 입출력 함수
• 빠른 입출력 함수 Link: [백준 15552. 빠른 A+B][빠른입출력]

---

출처¹

1 알고리즘 코딩테스트 입문부터 합격까지 강의 참고
빠른입출력