총정리
배열 (Array)
| 개념 | 내용 |
|---|---|
| 정의 | 같은 자료형 데이터를 연속된 메모리에 저장 |
| 특징 | 인덱스로 O(1) 접근 가능, 중간 삽입/삭제 시 O(N) |
| 주요 연산 | 인덱싱, 삽입, 삭제, 탐색 |
| 시간 복잡도 | 접근 O(1), 탐색/삽입/삭제 O(N) |
| 직접 구현 | insert_at, delete_at, find_value 등 |
| 내장함수 | len(), append(), insert(), pop(), remove() 등 |
C언어에서는 배열 크기 고정, 직접 메모리 관리 필요
문자열 (String)
| 개념 | 내용 |
|---|---|
| 정의 | 문자(char)의 연속, 문자 배열처럼 동작 |
| 특징 | 파이썬에서는 불변(immutable), 슬라이싱 가능 |
| 주요 연산 | 인덱싱, 슬라이싱, 탐색, 연결, 변환 |
| 시간 복잡도 | 슬라이싱/연결은 O(N), 탐색은 O(N) |
| 직접 구현 | 문자열 뒤집기, 문자 탐색, 부분 문자열 찾기 등 |
| 주요 함수 | len(), split(), strip(), replace(), find() 등 |
C에서는 char[], 널 문자 \0로 끝 표시, 직접 구현 필요
반복문 & 재귀 함수
| 개념 | 내용 |
|---|---|
| 반복문 | for, while 사용하여 반복 수행 |
| 재귀 함수 | 함수가 자기 자신을 호출, base case 필요 |
| 비교 | 반복은 명확하고 빠름, 재귀는 구조적으로 깔끔함 |
| 시간 복잡도 | 반복: 반복 횟수 기준, 재귀: 호출 트리 기준 분석 |
| 예시 | 팩토리얼, 피보나치, 합 구하기 등 |
재귀는 호출 스택을 사용 → 메모리 사용량 주의
복잡도 (Big-O 표기법)
| 개념 | 내용 |
|---|---|
| 시간 복잡도 | 입력 크기에 따른 실행 횟수 |
| 공간 복잡도 | 추가로 필요한 메모리 양 |
| 주요 표기 | O(1), O(log N), O(N), O(N log N), O(N²), O(2ⁿ), O(N!) |
| 분석 팁 | 가장 높은 항만 남김 (Big-O), 입력 크기 기준 성능 판단 |
문제의 입력 제한(N)에 따라 사용할 수 있는 알고리즘 복잡도를 예측해야 함
정렬 (Sorting)
| 개념 | 내용 |
|---|---|
| 목표 | 데이터를 오름차순 / 내림차순으로 나열 |
| 주요 알고리즘 | 버블, 선택, 삽입, 퀵, 병합, Timsort |
| 시간 복잡도 | O(N²): 버블, 선택, 삽입 / O(N log N): 병합, 퀵 |
| 직접 구현 | 버블, 선택, 삽입 정렬 구현 |
| 내장 함수 | sorted(), list.sort() + key, reverse 옵션 |
C언어에서는 qsort(), 혹은 모든 정렬을 직접 구현해야 함
완전 탐색 (Brute Force)
| 개념 | 내용 |
|---|---|
| 정의 | 가능한 모든 경우의 수를 시도 |
| 주요 유형 | 순열, 조합, 부분집합, 다중 for문 |
| 시간 복잡도 | O(N!), O(2ⁿ) 등 → N 작을 때만 가능 |
| 구현 방식 | 백트래킹(DFS), 반복문 |
| 예시 | 조합 생성, 3개 숫자 합이 0인 조합 찾기 등 |
C언어에서도 백트래킹과 반복문으로 구현 가능 (재귀 필수)
정수론 (Number Theory)
| 개념 | 내용 |
|---|---|
| 약수/배수 | n % d == 0이면 d는 n의 약수 |
| GCD/LCM | 유클리드 호제법으로 구현 (O(log N)) |
| 소수 판별 | √N까지만 나눠보면 됨 (O(√N)) |
| 소수 전체 구하기 | 에라토스테네스의 체 (O(N log log N)) |
| 소인수분해 | 나누면서 분해 (O(√N)) |
| 모듈 연산 | (a * b) % c = ((a % c) * (b % c)) % c 등 |
C언어로 직접 구현 시 반복문, 나눗셈, 조건문 필수
알고리즘 학습
| 개념 | 이유 |
|---|---|
| 배열/문자열 | 모든 알고리즘의 기본 데이터 구조 |
| 반복/재귀 | 로직 구현의 핵심 도구 |
| 복잡도 | 알고리즘의 성능을 판단하는 기준 |
| 정렬 | 정답 조건을 만족시키기 위한 전처리 |
| 완전 탐색 | 정답 보장되는 기본 전략, 최적화의 기준 |
| 정수론 | 소수, 배수, 수학적 조건이 있는 문제에서 필수 |
보충 개념
1. 파이썬의 기본 자료형 정리
(내장함수, 메서드, 시간 복잡도 포함)
list,str,dict,set,tuple→ 각 자료형의 특성과 시간 복잡도- 예:
in연산자 → 리스트는 O(N), set/dict는 O(1)
2. 정렬 기준을 이용한 커스터마이징 정렬
data.sort(key=lambda x: (x[1], x[0])) # 조건 2개 이상 정렬→ 점수순, 이름순 등 실전 문제에서 자주 나옴
3. 입력 최적화
- 파이썬 기본 입력은 느림 →
sys.stdin.readline()사용
4. 재귀 깊이 제한 해제
import sys
sys.setrecursionlimit(10**6)→ DFS 재귀 문제에서 필수
5. 정렬된 배열에서 이진 탐색
- 완전 탐색보다 빠르게 찾고 싶을 때 사용하는 탐색 최적화 기법
Week1 체크리스트
| 항목 | 숙지 여부 |
|---|---|
| 배열과 문자열 직접 구현 가능 | |
| 반복문/재귀 개념과 차이 이해 | |
| 시간복잡도 계산 가능 | |
| 정렬 알고리즘 최소 2~3개 직접 구현 | |
| 완전 탐색 구현(순열/조합/부분집합) 가능 | |
| GCD/LCM, 소수 판별 구현 가능 | |
| 에라토스테네스 체 이해 |
안녕하세요.