코딩테스트란?
•기업/기관에서 직원이나 연수생을 선발하기 위한 목적으로 시행되는 일종의 문제 풀이 시험
•2005년 무렵 국내 개발자 코딩 테스트가 도입
•다음커뮤티케이션이 마이크로소프트, 야후 등의 코딩테스트를 기반으로 알고리즘을 이용한 문제 해결 능력을 측정하는 코딩 테스트 시작
•공개채용을 하는 기업에서는 코딩 테스트를 주로 이용
•문제 해결 역량을 평가
•채점 시스템을 통해 응시자의 수를 효과적으로 줄일 수 있음
"즉, 정말 기본적인 코딩실력의 평가지표"
수업 때 배우는 것만으로는 좋은 성적 X
백준과 프로그래머스를 통해 향상 가능
그리디 - 탐욕법이라고 부르고 어떤것이 중요한지 알아야함
구현 - 기초적인 부분을 활용한 문제 *무조건 나옴
DFS/BFS를 활용한 탐색 - 웬만한 난이도에서 가장 많이 나오는 알고리즘
다이나믹 프로그래밍 - 매우 어려운 문제를 낼 때 많이 나오는 알고리즘
복습
복잡도
1. 시간복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
2. 공간복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
빅오표기법
•가장 빠르게 증가하는 항만을 고려하는 표기법입니다.
•함수의 상한만을 나타내게 됩니다.
•예를 들어 연산 횟수가 〖3N〗^3 + 5N^2 + 1,000,000인 알고리즘이 있다고 합시다.
•빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N^3 )으로 표현됩니다.
차수가 높아질 수록 엄청난 계산시간 소요
웬만해서는 이차까지 삼차는 정말 거의 없음
2^n은 거의 인생에서 없다고 봐도 무방
시간 복잡도 계산 예제
#N개의 데이터의 합을 계산하는 프로그램 예제
array = [3, 5, 1, 2, 4] # 5개의 데이터(N = 5)
summary = 0 # 합계를 저장할 변수
# 모든 데이터를 하나씩 확인하며 합계를 계산
for x in array:
summary += x
# 결과를 출력
print(summary)•수행 시간은 데이터의 개수 N에 비례할 것임을 예측할 수 있습니다.
•시간 복잡도: O(N)
#2중 반복문을 이용하는 프로그램 예제
array = [3, 5, 1, 2, 4] # 5개의 데이터(N = 5)
for i in array:
for j in array:
temp = i * j
print(temp)•시간 복잡도: O(N^2)
•참고로 모든 2중 반복문의 시간 복잡도가 O(N^2)인 것은 아닙니다.
•소스코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려해야 합니다.
알고리즘 설계팁
•일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우:
•C언어를 기준으로 통상 1 ~ 3초 가량의 시간이 소요됩니다.
•Python을 기준으로 통상 5 ~ 15초 가량의 시간이 소요됩니다.
•PyPy의 경우 때때로 C언어보다도 빠르게 동작하기도 합니다.
•O(N^3)의 알고리즘을 설계한 경우, N의 값이 5,000이 넘는다면 얼마나 걸릴까요?
•(5000 ^3)/500000000*5 = 1250 초
•코딩 테스트 문제에서 시간제한은 통상 1 ~ 5초가량이라는 점에 유의하세요.
•혹여 문제에 명시되어 있지 않은 경우 대략 5초 정도라고 생각하고 문제를 푸는 것이 합리적입니다.
요구사항에 따라 적절한 알고리즘 설계하기
•문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)입니다.
•시간제한이 1초인 문제를 만났을 때, 일반적인 기준은 다음과 같습니다.
•N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계하면 문제를 풀 수 있습니다.
•N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계하면 문제를 풀 수 있습니다.
•N의 범위가 100,000(10만)인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있습니다. (특별한 알고리즘사용)
•N의 범위가 10,000,000(1000만)인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있습니다. 매우 고난도
알고리즘 문제 해결 과정
•일반적인 알고리즘 문제 해결 과정은 다음과 같습니다.
1.지문 읽기 및 컴퓨터적 사고
2.요구사항(복잡도) 분석
3.문제 해결을 위한 아이디어 찾기
4.소스코드 설계 및 코딩
•일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면, 간결하게 소스코드를 작성할 수 있는 형태로 문제를 출제합니다.
"어떻게든 푼다? X 알맞게 푼다 O"
실전에서 유용한 표준 라이브러리
•내장 함수: 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공합니다.
•파이썬 프로그램을 작성할 때 없어서는 안 되는 필수적인 기능을 포함하고 있습니다.
•itertools: 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공합니다.
•특히 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용됩니다.
•heapq: 힙(Heap) 자료구조를 제공합니다. #반드시 이걸 써야하는 문제있음
•일반적으로 우선순위 큐 기능을 구현하기 위해 사용됩니다.
•bisect: 이진 탐색(Binary Search) 기능을 제공합니다. 이거도 꼭 알아야함
•collections: 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함합니다. #덱도 무조건 알아야함
•math: 필수적인 수학적 기능을 제공합니다.
•팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수부터 파이(pi)와 같은 상수를 포함합니다.