'이것이 코딩 테스트다' 강의를 듣는 이유 🤔
이전에 학습했던 알고리즘 힙, 큐, 스택, 해시 등의 알고리즘을 뒤로하고,,
혼자 공부하기 까다롭다고 생각했던 그래프기반 알고리즘(BFS/DP/그리디)을 학습하기 위해 강의를 듣기로 결정했다 ~ 유튜브에서 무료제공중이므로 3일 동안 열심히 강의를 듣고 정리해보도록 하겠다! ㅎㅎ
3일의 코테 전사 ... 시작합니다 😵💫
(1) 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기
코딩테스트 개요 및 출제 경향
- 리플릿: 온라인 파이썬 활용 사이트
- 파이썬 튜터: 온라인 파이썬 활용사이트, 어떤 변수에 어떤 값이 들어가는지 확인 가능
- 파이참: 디버깅 확인 가능
알고리즘 코테를 준비하는 과정에서 자신만의 소스코드를 관리하는 습관 들이기 !
자신이 자주 사용하는 알고리즘 코드를 라이브러리화 하기(팀 노트)
- 문제 유형에 따라 본인이 주로 쓰는 코드가 있기 때문.
가장 출제 빈도가 높은 유형: 그리디(쉬운 난이도), 구현, DFS/BFS 활용한 탐색
알고리즘 성능 평가
- 시간 복잡도: 알고리즘 수행 시간 분석
- 빅오 표기법: 가장 빠르게 증가하는 항만을 고려하는 표기법
- 빅오 표기법: 가장 빠르게 증가하는 항만을 고려하는 표기법
- 공간 복잡도: 알고리즘 메모리 사용량 분석
동일한 기능 수행할 경우 복잡도가 낮을수록 좋은 알고리즘임.
➡️ 코딩테스트에서는 시간 복잡도만 고려하면 됨
for문 한 번마다 n제곱씩
➡️이중 for문의 경우 O(n^2) (이때 내부적으로 수행되는 함수도 고려해야함)
파이썬 제출 시 1초 = 연산 횟수 1억(=100,000,000)으로 생각할 것
문제에 시간제한이 없을 경우 통상 5초정도라고 생각하면 됨
문제에서 시간제한(1초)을 확인했을 때 !
- N의 범위가 500인 경우, 시간 복잡도가 O(N^3)인 알고리즘 설계
- N의 범위가 2,000인 경우, 시간 복잡도가 O(N^2)인 알고리즘 설계
- 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)파이썬 문법, 자료형
-
파이썬 정수형:
int, 실수형 표현:float -
파이썬 지수표현방식: 임의의 큰 수를 표현하기 위해 자주 사용됨
- 최단 경로 알고리즘의 경우 도달 불가능한 노드에 대해 최단거리를 무한(INF: 1e9)로 설정함, 기본적으로 실수형 데이터
-
수 자료형 연산자:
/%//** -
리스트 자료형: 데이터를 연속적으로 담아 처리하기 위해 사용하는 자료형,인덱싱과 슬라이싱, 리스트 컴프리헨션이 가능
리스트 메서드 시간복잡도
- append(): O(1)
- sort(): O(NlogN)
- reverse(): O(N)
- insert(): O(N)
- count(): O(N)
- remove(): O(N)
-
문자형 자료형:
""'', 이스케이프 문자:\, 덧셈 곱셈 연산이 가능 -
튜플 자료형: 리스트와 유사하지만, 한 번 선언된 값을 변경할 수 없음, 소괄호 선언, 리스트에 비해 공간효율적
- 서로 다른 성질의 데이터를 묶어 관리할 경우
- 데이터의 나열을 해싱(hashing)의 키 값으로 활용할 경우
- 메모리 효율성이 필요할 경우
-
사전 자료형: 키(Key)와 값(Value)의 쌍을 데이터로 가지는 자료형, 값의 순서X, 해시 테이블 이용으로 데이터의 조회 및 수정에 효율적: O(1)
-
집합 자료형: 중복되는 값은 허용X, 순서X, 합집합, 교집합, 차집합 연산이 가능
파이썬 기본 입출력
-
input(): 한줄의 문자열을 입력 받는 함수 -
map(): 리스트의 모든 원소에 각각 특정한 함수를 적용하는 함수- 공백을 기준으로 구분된 데이터를 입력받을 때
➡️data = list(map(input().split()))
- 공백을 기준으로 구분된 데이터를 입력받을 때
-
sys.stdin.readline(): 사용자로부터 입력을 최대한 빠르게 받아야 하는 경우, sys 라이브러리에 정의된 readline 메서드를 사용함- 단, 입력 후 enter가 줄바꿈 기호로 입력되므로
rstrip()메서드를 함께 사용
➡️data = sys.stdin.readline().rstrip()
- 단, 입력 후 enter가 줄바꿈 기호로 입력되므로
-
print(): 파이썬 기본 출력 함수, 기본적으로 출력 이후에 줄바꿈 수행, 줄바꿈 발생 X시: end 인자를 활용 -
파이썬 3.6 이후 버전부터는 문자열 출력시 f-string 활용이 가능함.
조건문과 반복문
-
파이썬에서는 코드의 블록을 들여쓰기로 지정함. tab이나 space 4개 활용
-
if ~ elif ~ else -
비교 연산자
==!=>=<=>< -
논리 연산자
andornot -
기타 연산자: 리스트, 튜플, 문자열, 딕셔너리 형태
innot in -
pass키워드: 프로그램 작성 도중 조건문의 형태만 만들어놓을 때 활용 -
C,JAVA 달리 파이썬은
0<x<20와 같은 부등식 형태 활용이 가능함. 다만 다른 언어와 헷갈리지 않기 위해 and, or의 연산자를 활용 -
whilefor -
무한루프(끊임없는 반복문)을 주의할 것
-
continue키워드: 반복문에서 남은 코드의 실행을 건너뛰고, 다음 반복을 진행하고자 할때 활용 -
break키워드: 반복문을 즉시 탈출
함수
자주 사용하는 작업을 하나의 단위로 묶어놓은 것
-
내장함수: 파이썬이 기본적으로 제공하는 함수
-
사용자 정의 함수: 개발자가 직접 정의하여 사용하는 함수(
def) -
global키워드: 함수 바깥에 선언된 변수(=전역 변수)를 참조할 때 활용
유용한 표준 라이브러리
-
itertools: 파이썬에서 반복되는 형태의 데이터 처리에 유용- 순열과 조합 라이브러리(
product,combinations)
- 순열과 조합 라이브러리(
-
heapq: 힙 자료구조 제공- 우선순위 큐 기능 구현
-
bisect: 이진탐색 기능 제공 -
collections: 덱(deque), 카운터(Counter)등의 유용한 자료구조 포함 -
math: 수학적 기능 제공- 팩토리얼, 제곱근, 최대공약수, 삼각함수 관련 함수, 파이 상수
