[이것이 코딩 테스트다] 코딩테스트 개요

1. 사이트 : 백준 & 코드포스

국내

• 백준
• 코드업
• 프로그래머스
• SW export academy

국외

• 코드포스 → 민트 이상 목표
• 탑코더
• 립코더
• 코드셰프

2. 조건

• 제출 횟수 제한
• 온라인 IDE 공개 여부 확인
  • 리플릿
  • PythonTest
  • 파이썬 튜터
• 접근 방식 설명

3. 복잡도

⇒ 코딩 테스트에서는 최악의 시간 복잡도가 중요하여, 가장 우선으로 고려!

• 시간 복잡도 : 연산 횟수
• 공간 복잡도 : 메모리 양 - 128~512MB
  • 1024(2^10)개 단위로 뜀
  • Byte (바이트)< KB(킬로바이트) < MB(메가바이트) < GB(기가바이트) < TB(테라바이트)

1초 예시( 숫자가 크면 log(N) 빠름 < log(N logN)

• N = 500, O(N^3)
• N = 2000, O(N^2)
• N = 100,000 십만, O(N logN)
• N = 1,000,000 백만, O(N)

4. 최신 출제 경향

• 정렬
• 그리디
• 구현
• DFS/BFS
• (다이나믹 프로그래밍, 그래프 이론)

5. 질의응답

1. 알고리즘 풀이
   • 어떤 상황에서 어떤 알고리즘이 사용되는지 & 비교해서 왜
   • 정렬 알고리즘의 시간 복잡도
     • 선택, 삽입은 최악의 O(N^2)의 시간 소요, 그러나 병합 정렬 같이 최악 경우에도 O(N logN) 보장추가로, 계수 정렬 같은 O(N+K)를 보장하는 정렬 알고리즘 사용 가능
     • 대부분 라이브러리에서도 O(N logN) 형태로 정렬 기능 제공
2. 포트폴리오 징의응답
   • 개발 프로젝트에 필요한 지식 요구(신입 교육 불가 : 잠재력 < 경험)
   • 토이 프로젝트 정리
   • 웹 개발자 → spring
   • 클라우드 이용 경험
3. 공학 지식 질의응답
   • 서버 개발 : 멀티 스레딩, 메모리 관리
   • 웹 개발 : GET, POST 차이 / tcp, udp, http, https 개념과 원리
   • 데이터베이스 : 정규화, 인텍스, NoSQL