이것이 취업을 위한 코딩 테스트다 2021 - 코딩 테스트 출제경향 분석

#1. 코딩테스트 경향

■ 팀 노트

- 알고리즘 코테 준비를 위해 자신만의 소스코드를 관리하는 것

- 자신이 자주 사용하는 알고리즘 코드를 라이브러리화

- 주로 깃허브로 관리

 

■ 코테 출제 경향

- 구현 / BFS, DFS / 그리디 / 정렬 / 동적 프로그래밍 / 이진 탐색 / 최단 경로

 

■ 코테 유형

- 카카오 코테는 카카오 기술 블로그 참조

---

 

#2. 알고리즘 기초

■ 복잡도 (특정한 크기의 입력에 대하여)

- 시간 복잡도: 알고리즘의 수행 시간 분석

- 공간 복잡도: 알고리즘의 메모리 사용량 분석

• 복잡도 낮을수록 좋은 알고리즘이라고 할 수 있음

- 빅오 표기법: 함수의 상한만을 나타냄

• O(1): 상수시간: 문제 해결에 오직 한 단계만 처리 (상수N)
• O(logN): 로그시간: 문제 해결에 필요한 단계들이 연산마다 특정 요인에 의해 줄어듦
• O(N): 선형시간: 문제 해결 위한 단계의 수와 입력값 N이 1:1 관계를 가짐
• O(NlogN): 로그선형시간
• O(N^2): 이차시간
• O(N^3): 삼차시간
• O(2^n): 지수시간
• 물론 이 외에 더 많기도 함

- 시간 복잡도 계산

• 모든 2중 반복문이 시간 복잡도가 O(N^2)이 아님
• 내부에 별도 함수 호출 시 그 함수의 복잡도 고려

 

■ 알고리즘 설계Tip

- 일반적 CPU 기준, 연산 횟수 5억 이상일 경우

• C언어 기준으로 1~3초 시간 소요
• Python 기준으로 5~15초 시간 소요
  • PyPy의 경우 C보다 빠를 때도 있음 (Python과 PyPy 바꿔가며 제출해볼 것)

- 수행 시간을 예측해서 알고리즘을 설계하는 것이 중요

• 시간 제한이 1초인 문제일 때 시간 복잡도 예측
  • N 범위 500 : O(N^3)인 알고리즘 설계
  • N 범위 2000 : O(N^2)인 알고리즘 설계
  • N 범위 100,000 : O(NlogN)인 알고리즘 설계
  • N 범위 10,000,000 : O(N)인 알고리즘 설계
• 어느 정도 성능으로 동작해야할지 분석 필요
• 핵심 아이디어를 캐치한다면 간결하게 소스코드를 작성 할 수 있는 형태가 많다

---

뒷부분인 파이썬 기초 문법 파트는 파이썬 카테고리에 있다.

2023.06.11 - [프로그래밍언어 || 프레임워크/Python] - 이것이 취업을 위한 코딩테스트다 2021 - 파이썬 기초 문법

이것이 취업을 위한 코딩테스트다 2021 - 파이썬 기초 문법