[동빈나]이코테 2021 강의 몰아보기 (1)(2020.12.30)

본 내용은 해당 강의 토대로 작성

코딩 테스트 출제 경향 분석

1. 코딩 테스트 개요 및 출제 경향

코딩 테스트 개요

• 기업 / 기관에서 직원,연수생 선발 목적으로 시행되는 문제 풀이 시험
• 공개채용 하는 기업에서 주로 이용
  • 문제 해결 역량 평가
  • 응시자 수 효과적으로 줄일 수 있음

코딩 테스트의 유형

• 온라인 코딩 테스트
  • 인터넷을 활용해 역량 평가
  • 인터넷 검색 선까지 허용
  • 표준 라이브러리 사용 방법 등 검색 가능
• 오프라인 코딩 테스트
  • 시험장에 방문 응시
  • 인터넷 검색 금지, 시험장 컴퓨터 환경 이용

일반적으로 1차 온라인, 2차 오프라인 or 면접 방식으로 진행

온라인 저지

문제를 시험해보는 온라인 시스템, 국내의 사이트는 아래와 같다.

• 백준 : 많은 대기업 기출, 유형별, 많은 국내 사용자
• 코드업 : 초보자
• 프로그래머스 : 대기업 기출
• SW Expert Academy

코딩 테스트 프로그래밍 언어

1. C++ : 메모리 관리 측면에서 자유도 높음, 실행속도 빠르다.

2. Python : 나날이 비중 커짐, 짧고 간결함, 표준 라이브러리 다양, 사용 편의성, 코딩 테스트에 적합, 과제형 테스트 유리

3. Java : 실행속도 느림, 코드 길다.

새롭게 공부하는 경우 Python 추천

온라인 개발 환경(Python)

리플릿 사용

자신만의 소스코드 관리하기

• 알고리즘 코딩 테스트를 준비하는 과정에서 자신만의 소스코드 관리
• 팀노트 : 자신이 자주 사용하는 알고리즘 코드를 라이브러리화

IT 기업 코딩 테스트 최신 출제 경향

• 2~5시간
  • 그리디(쉬운 난이도)
  • 구현
  • DFS/BFS를 활용한 탐색

카카오의 경우 기술 블로그에서 출제된 문제에 대한 자세한 설명 나와 있음

주로 문자열(구현) 다루는 문제 출제

2. 알고리즘 성능 평가

복잡도(Complexity)

• 복잡도는 알고리즘을 성능을 나타내는 척도
  • 시간 복잡도: 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석
  • 공간 복잡도: 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석
• 동일한 기능일 때, 복잡도가 낮을수록 좋은 알고리즘
• 복잡도란, 특정한 함수의 성능적인 측면에서 말하는 것

빅오 표기법(Big-O Notation)

• 가장 빠르게 증가하는 항만을 고려하는 표기법
  • 함수의 상한만을 나타냄
• 연산 횟수가 3N³ + 5N² + 1,000,000인 알고리즘이 있을 때, 차수가 가장 큰 항만 남기므로 O(N³)
• 계수는 무시
• 극한의 개념으로 접근, N이 큰 수라고 가정하기
• 상수 시간( 몇번의 연산을 거치면 수행 완료 ), 로그시간

시간 복잡도 계산해보기 1)

array = [3,5,1,2,4]
summary = 0

for x in array: #모든 데이터 하나씩 계산
  summary += x

print(summary)

수행시간은 데이터 개수 N에 비례하므로 시간 복잡도는 O(N)

시간 복잡도 계산해보기 2)

array = [3,5,1,2,4]
for i in array: #이중 for문
  for j in array:
    temp = i * j
    print(temp)

시간 복잡도: O(N²)

모든 2중 반복문이 O(N²)인 것은 아니다. 내부적으로 다른 함수를 호출한다면, 그것의 시간 복잡도도 고려해야 함

알고리즘 설계 Tip

• 연산 횟수가 5억을 넘는 경우
  • C언어 : 1~3초 소요
  • Python : 5~13초 소요
  • pypy의 경우 때때로 C보다 빠르기도 함
• 코딩 테스트에서 시간제한은 통상 1~5초
• Python으로 제출했을 때, 시간 초과 판정일 경우, pypy로 다시 해보기
• pypy로 시간,메모리 초과할 경우, Python으로 해보기
• 채점용 서버에서, Python이 1초에 2000만번 연산을 처리할 수 있다고 가정할 것

요구사항에 따라 적절한 알고리즘 설계하기

• 문제에서 가장 먼저 시간제한(수행시간 요구사항) 확인하기
• 시간 제한이 1초인 문제를 만났을 때, 기준은 다음과 같다.
  • N의 범위가 500인 경우 : 시간 복잡도가 O(N³) 인 알고리즘 설계
  • N의 범위가 2,000인 경우 : 시간 복잡도가O(N²)인 알고리즘 설계
  • N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘 설계
  • N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘 설계

알고리즘 문제 해결 과정

1. 지문 읽기 및 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제 해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩

핵심 아이디어를 캐치한다면, 간결하게 소스코드 작성할 수 있음

수행 시간 측정 소스코드 예제

import time
start_time = time.time() #측정 시작
# 프로그램 소스코드
end_time = time.time() #측정 종료
print("time:", end_time-start_time) #수행 시간 출력