이것이 코딩테스트다 with 파이썬 기반 정리 내용입니당
🖥 코딩테스트란?
최근 IT 기업의 채용과정에서 대부분이 코딩테스트를 친다!
뉴스만 검색해봐도, 코딩테스트가 중요하고 개발자라면 항상 코딩테스트를 걱정할 것이다.
전체적으로 IT 개발직군의 경우에는 프로젝트 경험, 코딩테스트 준비, CS지식이 제일 중요하다는 생각이 든다..🧐
늦었지만 더 늦어지기전에 코딩테스트 준비를 제대로 해야겠다는 생각이 들어 슬슬 시작해보려 한다.
일단 목표는 책 다 훑고 코딩테스트 문제 100개 풀기다! 화이팅!
문제는 백준과 프로그래머스 중에서 선정하여 풀 생각이고,
스터디를 진행하며, 깃허브 잔디심기도 열심히 하려고 한다.ㅎㅎ
복잡도
💡 코딩테스트에서 예를 들어 3문제가 나왔을 때, 3문제 다 풀었다고 만점일까?
절대 아니다.
시간복잡도,공간복잡도에 따라 더 효율적인 알고리즘을 사용한 사람이 더 높은 점수를 획득할 것이다.
따라서 시간 복잡도,공간 복잡도를 계산하는 방법에 대해서 알아보자
예전에 다 알았던 상식인데 안하다보니 까먹은 지식들이 많다😂
시간복잡도? :알고리즘을 위해 필요한 연산의 횟수
공간복잡도? :알고리즘을 위해 필요한 메모리의 양
👋 궁금한 점
예를 들어, 코딩테스트에서 한문제를 시간복잡도와 공간복잡도를 낮도록 제대로 푸는 것 vs 두문제를 복잡도를 고려하지 않고 푸는 것
어느 것이 더 높은 점수를 획득할까?
시간 복잡도
빅오(Big-O) 표기법을 사용한다
빅오 표기법을 간단히 정의하자면, 가장 빠르게 증가하는 항만을 고려하는 표기법
다시 말해 함수의 상한 만을 나타낸다.
실제 케이스를 보면서 이해하는게 좋을 것 같당
어쩌구
for x in array:
summary +=x
print(summary)👉다음과 같은 경우는 print()도 있고 for문도 있지만, for문의 영향력이 가장 크기 때문에, for문으로 시간 복잡도를 판단한다.
예를 들어 5개의 데이터를 받아 차례로 5회 더해주는 경우. 이때 연산 횟수는 N에 비례한다 -> 즉 O(N)
2중 반복문이 사용된 경우 O(N^2)으로 생각할 수 있다.
💡알고리즘 문제 풀이를 할 때 문제의 조건부터 확인하여 얼마나 효율적인 알고리즘을 작성해야하는지 파악해야한다!
- 일반적인 CPU 기반의 컴퓨터는 연산 횟수가 10억을 넘어가면 C 언어를 기준으로 통상 1초 이상의 시간이 소요된다. 파이썬은 더욱 오래 걸린다.
- 일반적으로 코딩테스트 문제에서의 시간제한은 1~5초
- 이를 계산해서 대충 어떤 시간 복잡도를 갖는 알고리즘을 작성해야하는지 확인가능!
문제를 풀다보면 대충 감각이 생길 듯 하다
공간 복잡도
시간 복잡도가 끝이 아니다,,,, 공간복잡도도 계산을 해야한다. 즉 메모리 사용량도 계산을 해야 된다!
- 대부분 리스트(배열)를 사용해서 풀어야 함
- 보통 코딩테스트에선 128~512MB로 제한
- int 자료형의 경우 약 리스트 길이가 100만개일 때, 4MB
파이썬에서는, 웬만하면 넘어갈 일 없을듯
시간과 메모리 측정
- 알고리즘을 공부하는 과정에서 시간을 측정하는 작업을 굉장히 많이 사용
- 실질적으로 알고리즘의 소요 시간을 확인해야 자신이 제대로 작성하고 있는지 체크할 수 있기 때문
import time
start_time=time.time() # 측정 시작
소스코드 블라블라
end_time = time.time()
print("time:",end_time - start_time) # 수행시간 출력
💎출제 경향
- 출제 빈도는 그리디 > 구현 > DFS/BFS를 활용한 탐색 문제
- 카카오의 경우 '그리디 혹은 구현 유형의 문제'를 다수 확인할 수 있음
- 삼성 전자의 경우 '문제를 바르게 읽고 예외 상황을 적절히 처리하는 방식으로 소스코드를 작성하는 유형', 완전 탐색, DFS/BFS, 구현 유형의 문제를 가장 선호
