이것이 취업을 위한 코딩 테스트다 - 1
❗참고 : 이것이 취업을 위한 코딩 테스트다
코딩 테스트 준비를 돕는 다양한 서비스
- codeup
- 백준 온라인 저지
- 백준 온라인 저지의 문제 순서는 난이도와 무관
- 크롬에 solved.ac 확장 프로그램을 설치하여 난이도 정보를 확인 가능
- programmers
- for kakao
- SW Expert Academy
- with Samsung
- 가장 난이도가 낮은 A형에 응시하여 실력 테스트 (A형을 통과 후 B형 응시 자격이 주어짐)
- 삼성의 경우, 주로 DFS / BFS 를 활용하는 탐색과 시뮬레이션 문제 유형을 주로 출제함
코테에 유리한 언어?
- python
- 배우기 쉽고, 읽고 쓰기 쉬워 초보자가 접근하기 좋음
- 라이브러리가 풍부함
- AI 나 데이터 분석 분야에 널리 사용됨
- C++
- 다른 언어에 비해 빠름 (with C)
- 삼성의 경우, B 형부터는 파이썬을 제외하고 선택 가능함
- 삼성 C형은 C/C++의 필수 라이브러리를 제외한 대부분의 표준 라이브러리를 사용 불가 (기본 자료구조부터 작성)
코테 종류에 따라 선택하여 작성할 수 있도록 알면 좋을 듯… -> k의 경우, 본인이 할 수 있는 언어로 전부 풀어보라는 형태도 나왔던거 같다. (같은 문제를 C로 풀고, C++로 풀고, Python으로 풀고, java로 풀고…)
실습 환경 구축
- 온라인 웹 IDE
- 리플릿
- 파이썬 튜터
- 온라인 GDB
- 오프라인 개발 환경
- VS Code
- Jupyter Notebook
- Pycharm
이 책의 메인이 python이라서 그런듯..
- Cloud IDE
- 요새 이쪽으로 몬가 많아져서 적당한 IDE 골라서 사용하면 될 듯
- 대부분의 cloud ide에서는 c / c++ / python / java 정도는 기본으로 제공하고 있음
복잡도 (Complexity)
-
알고리즘의 성능을 나타내는 척도
- 시간 복잡도
- 얼마나 오래 걸리는가?
- 알고리즘을 위해 필요한 연산의 횟수
- 공간 복잡도
- 얼마나 많은 메모리를 사용하는가?
- 알고리즘을 위해 필요한 메모리의 양
시간 복잡도
- 코딩 테스트를 풀다 보면 시간 복잡도에 의해 “시간 초과 + 오답 처리”를 볼 수 있음
- 시간 복잡도를 표현할 때는 Big-O 표기법을 사용함
- 가장 빠르게 증가하는 항만을 고려하여 표기함
- O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) ~~~
공간 복잡도
- 공간 복잡도도 Big-O 표기법을 이용
- 시간 복잡도의 경우, 1초가 절대적인 제한이였다면 공간 복잡도는 MB 기준으로 표기됨
- 코딩 테스트에서는 보통 메모리 사용량을 128MB ~ 512MB 로 제한한다.
int a[1000] >> 4KB
int a[1000000] >> 4MB
int a[2000][2000] >> 16MB
시간과 메모리 측정
- 파이썬의 예제….
import time
start_time =
time.time() # 측정 시작
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time :", end_time - start_time) # 수행 시간 출력
- c++ 샘플
#include <iostream>
#include <ctime>
int main(void) {
clock_t start_time = clock(); // 측정 시작
// 프로그램 소스 코드
clock_t end_time = clock(); // 측정 종료
clock_t diff_msec = end_time - start_time; // millisec
double diff_sec = (double)(diff_msec / CLOCKS_PER_SEC); // sec
std::cout << "time : " << diff_sec << "\n";
return 0;
}