코딩 테스트 출제 경향 분석 및 파이썬 문법 정리
📌 알고리즘 설계 Tip
언어별 연산 속도 기준
| 언어 | 1초당 연산 횟수 |
|---|---|
| C언어 | 약 1억 번 |
| Python | 약 2천만 번 |
| PyPy | 때때로 C언어보다 빠름 |
연산 횟수가 5억을 넘어가는 경우, C언어 기준 1~3초, Python 기준 5~15초 소요
코딩 테스트의 시간제한은 보통 1~5초. 명시되지 않은 경우 5초로 가정하자.
n의 범위에 따른 시간 복잡도 기준 (시간제한 1초)
| n의 범위 | 적합한 시간 복잡도 |
|---|---|
| 500 | O(n³) |
| 2,000 | O(n²) |
| 100,000 | O(n log n) |
| 10,000,000 | O(n) |
알고리즘 문제 해결 과정
- 지문 읽기 및 컴퓨터적 사고
- 요구사항(복잡도) 분석
- 문제 해결을 위한 아이디어 찾기
- 소스코드 설계 및 코딩
💡 핵심 아이디어를 캐치하면 코드는 간결해진다. 문제에서 가장 먼저 시간제한을 확인하자!
수행 시간 측정 코드
import time
start_time = time.time() # 측정 시작
# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력📦 파이썬 자료형
1. 실수형 (Float)
실수형은 부동소수점 오차가 있으므로 비교 시 round() 를 사용하자.
a = 0.3 + 0.6
print(round(a, 4)) # 0.9
if round(a, 4) == 0.9:
print(True)
else:
print(False)2. 리스트 (List)
인덱싱 & 슬라이싱
끝 인덱스는 실제보다 1 크게 설정한다.
a = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(a[1:4]) # [2, 3, 4]리스트 컴프리헨션
# 0부터 9까지
array = [i for i in range(10)]
# 0~19 중 홀수만
array = [i for i in range(20) if i % 2 == 1]
# 1~9의 제곱값
array = [i * i for i in range(1, 10)]2차원 리스트 초기화
# ✅ 올바른 방법
array = [[0] * m for _ in range(n)]
# ❌ 잘못된 방법 (모든 행이 같은 객체를 참조함)
array = [[0] * m] * n리스트 주요 메서드
| 함수명 | 사용법 | 설명 | 시간 복잡도 |
|---|---|---|---|
append() | 변수명.append(값) | 원소 하나 삽입 | O(1) |
sort() | 변수명.sort() / 변수명.sort(reverse=True) | 오름차순 / 내림차순 정렬 | O(N log N) |
reverse() | 변수명.reverse() | 원소 순서 뒤집기 | O(N) |
insert() | insert(인덱스, 값) | 특정 위치에 삽입 | O(N) |
count() | 변수명.count(값) | 특정 값의 개수 반환 | O(N) |
remove() | 변수명.remove(값) | 특정 값 하나 제거 | O(N) |
a = [1, 4, 3]
a.append(2) # [1, 4, 3, 2]
a.sort() # [1, 2, 3, 4]
a.sort(reverse=True) # [4, 3, 2, 1]
a.reverse() # [1, 2, 3, 4]
a.insert(2, 3) # [1, 2, 3, 3, 4]
a.count(3) # 2
a.remove(1) # [2, 3, 3, 4]특정 값 원소 모두 제거하기
a = [1, 2, 3, 4, 5, 5, 5]
remove_set = {3, 5}
result = [i for i in a if i not in remove_set]
print(result) # [1, 2, 4]3. 문자열 (String)
+: 문자열 연결*: 문자열 반복- 인덱싱/슬라이싱 가능, 단 Immutable (특정 인덱스 값 변경 불가)
a = "Hello"
b = "World"
print(a + " " + b) # Hello World
a = "String"
print(a * 3) # StringStringString
a = "ABCDEF"
print(a[2:4]) # CD4. 튜플 (Tuple)
리스트와 유사하지만 변경 불가(Immutable), 소괄호 () 사용
a = (1, 2, 3, 4, 5, 6, 7, 8, 9)
print(a[3]) # 4
print(a[1:4]) # (2, 3, 4)
# a[2] = 7 ← 오류 발생!튜플을 사용하면 좋은 경우
- 서로 다른 성질의 데이터를 묶을 때 → ex.
(비용, 노드번호)형태로 최단경로 알고리즘에서 활용 - 해싱의 키(key) 로 사용해야 할 때 (리스트는 키로 사용 불가)
- 메모리를 더 효율적으로 사용해야 할 때
5. 사전 자료형 (Dictionary)
- 키(key) - 값(value) 쌍으로 데이터 저장
- 해시 테이블 기반 → 조회 및 수정 O(1)
- 키는 Immutable 자료형만 사용 가능
data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
data['코코넛'] = 'Coconut'
print(data) # {'사과': 'Apple', '바나나': 'Banana', '코코넛': 'Coconut'}
if '사과' in data:
print("'사과'를 키로 가지는 데이터가 존재합니다.")# 키/값 리스트 추출
key_list = data.keys()
value_list = data.values()
for key in key_list:
print(data[key])# 딕셔너리 선언 방법
b = {
'홍길동': 97,
'이순신': 98
}
print(b['이순신']) # 98
print(list(b.keys())) # ['홍길동', '이순신']6. 집합 자료형 (Set)
- 중복 허용 X, 순서 없음
- 조회 및 수정 O(1)
a = set([1, 2, 3, 4, 5])
b = set([3, 4, 5, 6, 7])
print(a | b) # 합집합: {1, 2, 3, 4, 5, 6, 7}
print(a & b) # 교집합: {3, 4, 5}
print(a - b) # 차집합: {1, 2}data = set([1, 2, 3])
data.add(4) # 원소 하나 추가
data.update([5, 6]) # 원소 여러 개 추가
data.remove(3) # 특정 원소 삭제🔑 자료형 핵심 정리
| 자료형 | 순서 | 인덱싱 | 중복 | 조회 시간 |
|---|---|---|---|---|
| 리스트 | ✅ | ✅ | ✅ | O(N) |
| 튜플 | ✅ | ✅ | ✅ | O(N) |
| 사전 | ❌ | ❌ | 키 중복 X | O(1) |
| 집합 | ❌ | ❌ | ❌ | O(1) |
사전과 집합은 순서가 없어 인덱싱 불가. 대신 O(1) 의 빠른 조회 속도가 장점!
