1. 온라인 코딩테스트 vs 오프라인 코딩테스트 : 인터넷 검색 허용 / 허용 불가의 경우가 많음. 온라인 합격 다음에 오프라인 식으로 진행하기도 함.
2. 온라인 저지 : 프로그래밍 대회나 코딩 테스트에서 나올 법한 문제를 시험해보는 온라인 시스템
- 백준 온라인 저지, 코드업, 프로그래머스
3. 코테 언어 : 주로 C++, 파이썬을 코테 응시에 사용함. 프로그램 개발 방식 코테에서 가장 유리한 프로그래밍 언어는 파이썬, 자바.
4. 팀노트 만들어서 비슷한 유형의 코딩 테스트에 대비하기.
<코딩테스트 출제 경향>
1) 그리디
2) 구현
3) BFS/DFS
<알고리즘 성능평가>
1) 복잡도 : 시간 복잡도(수행 시간 분석), 공간 복잡도(메모리 사용량 분석) 낮을 수록 더 좋은 알고리즘.
- 빅오 표기법 : 가장 빠르게 증가하는 항만 고려하는 표기법. 함수의 상한만을 나타내게 됨. 3N^3 + 5N^2 의 빅오 표기법은 O(N^3).
2) 알고리즘 설계시 유의사항
- CPU 기반 컴퓨터의 연산 횟수가 5억 이상인 경우: C언어는 1~3초, Python은 5~15초 걸릴 수 있음.
- 코딩테스트 문제에서 시간제한은 통상 1~5초 가량이라는 점에 유의할 것.
+ N의 범위에 따른 시간 복잡도 제한. (시간제한 1초)
- N의 범위가 500인 경우 : O(N^3)
- N의 범위가 2000인 경우 : O(N^2)
- N의 범위가 100,000인 경우 : O(NlogN)
- N의 범위가 10,000,000인 경우 : O(N)
3) 문제 해결 과정
(1) 지문 읽기 및 컴퓨터적 사고
(2) 요구사항(복잡도) 분석
(3) 문제 해결을 위한 아이디어 찾기
(4) 소스코드 설계 및 코딩
4) 수행 시간 측정 소스코드
import tiome
start_time = time.time()
end_time = time.time()
print("time:", end_time - start_time)
<자료형>
- 정수형 : int
- 실수형 : float : 실수형을 저장하기 위해 고정된 크기의 메모리를 할당해 실수 표현시 정확도에는 한계가 있음. = round 함수를 이용해서 자리를 고정해야함.
+ 지수 표현 방식 : 유효숫자 e 지수 = 유효숫자 * 10^지수
+ 수 자료형의 연산 : 나누기 연산자는 나눠진 결과를 실수형으로 반환함. 그래서 나머지 연산자와 몫 연산자를 사용함.
- 리스트 자료형 : 일반적인 배열과 유사한 기능. 배열 혹은 테이블이라고 부른다.
+ 리스트 컴프리헨션 : 조건문과 반복문 등을 이용해서 리스트 초기화
Ls=[i for i in range(10)]
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Ls=[i for i in range(10) if i % 2 == 1]
# [1, 3, 5, 7, 9]
- 문자열 변수 " ", ' ' : \ 백슬레시를 활용해서 특수기호를 포함시킬 수 있음.
+ 문자열 연산 : 덧셈과 곱셈 가능. 문자열은 특정 인덱스 값을 변경할 수 없음.
- 튜플 자료형 : 한번 선언된 값을 변경할 수 없음.
+ 튜플 사용시 좋은 경우
1) 서로 다른 성질의 데이터를 묶어서 관리해야 할 때
2) 데이터의 나열을 해싱의 키 값으로 사용해야 할 때
3) 리스트보다 메모리를 효율적으로 사용해야 할 때
- 딕셔너리 : 키와 값을 쌍으로 가지는 자료형. 해시 테이블을 이용하므로 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다.
- 집합 : 중복을 허용하지 않고, 순서가 없음. {}
+ 합집합 |, 교집합 &, 차집합 - 으로 수행할 수 있음.
+ add()로 추가, update([1,2])로 여러개 원소 추가, remove()로 특정값 원소 삭제
<기본 입출력>
1) 입력
a=input()
#한 줄의 문자열 입력
b=map()
#리스트 형식으로 입력된 값들 각각 자료형 변환
Ls=map(int, input().split())
- 입력을 최대한 빠르게 받아야 하는 경우 (속도 제한)
import sys
sys.stdin.readline().rstrip()
# 입력 후 엔터가 줄 바꿈 기호로 변환되기 때문에 .rstrip() 사용
2) 출력
- print 함수. 출력 이후에 줄바꿈을 원하지 않는다면 end=' '로 끝을 설정해줄 수 있음.
+) f-strint : print(f"{name}")
<조건문>
- if문
+ 한줄 쓰기 : true실행문 if 조건 else false실행문
<반복문>
- while문 : 특정 조건을 만족할 때 반복 실행. 무한루프 발생 가능하므로 탈출할 수 있는지 확인해야함.
- for문 : for i in range(시작값, 끝값+1) : 시작값부터 끝값까지 순차적 수행
+ 반복문 탈출하기 위해서 break 쓸 수 있음.
+ 특정 조건은 넘어가기 위해 continue 함수를 쓸 수 있음.
- 중첨 반복문 : 바깥 반복문 실행시 안 반복문도 매번 실행됨.
<함수>
- 내장함수와 사용자 정의 함수
def 함수명(매개변수):
실행할 소스코드
return 반환값 #반환값을 여러개 값을 가질 수 있음
+ global 키워드로 함수 바깥에 선언된 변수를 활용할 수 있음.
a = 1
def func():
global a
a += 1
print(a)
func()
- 람다 표현식 (이름 없는 함수)
lambda a,b : a+b
print(sorted(array, key=lambda x: x[1]) : 정렬 기준을 [1]에 위치한 것을 기준으로 정렬하라
<실전에서 유용한 표준 라이브러리>
- 내장 함수
+ sum(), min(), max(), sorted(,reverse=True 내림차순)
- itertools 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들 제공. 순열과 조합 라이브러리 자주 사용됨.
+ 내부 원소가 몇번 등장했는지 알려주는 함수 Counter
+ 순열과 조합
#순열
from itertools import permutations
data = ['A', 'B', 'C']
result = list(permutation(data, 3))
print(result)
#조합
from itertools import combinations
data = ['A', 'B', 'C']
result = list(combinations(data, 2))
print(result)
- 중복순열과 중복조합
#중복순열
from itertools import product
data = ['A', 'B', 'C']
result = list(product(data, repeat=2)) #2개 뽑는 순열 구하기(중복허용)
print(result)
#중복조합
from itertools import combinations_with_replacement
data = ['A', 'B', 'C']
result = list(combination_with_replacement(data, 2)) #2개 뽑는 조합 구하기(중복허용)
print(result)
- heapq : 힙 자료구조를 제공. 우선순위 큐 기능을 구현하기 위해 사용됨.
- bisect : 이진 탐색 기능을 제공.
- collections : 덱, 카운터 등의 유용한 자료구조를 포함.
- math : 필수적인 수학적 기능을 제공. (팩토리얼, 제곱근 등)
+ 최대 공약수 : math.gcd(5, 10)
+ 최소 공배수 : 5 * 10 // math.gcd(5, 10)
'코딩 어쩌구 > 코딩테스트' 카테고리의 다른 글
[코드업] 3004번 데이터 재정렬 (0) | 2021.11.10 |
---|---|
[코드업] 1805번 입체기동장치 생산공장 (0) | 2021.11.09 |
[코드업] 6098번 성실한 개미 (0) | 2021.11.08 |
[코드업] 6097번 설탕과자 뽑기 (0) | 2021.11.08 |
[코드업] 6096번 바둑알 십자 뒤집기 (0) | 2021.11.08 |