1. 알고리즘이란?
- 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법, 문제를 해결하는 방법
- 한 문제를 해결하는 방법은 한 가지만 있는 게 아니라 무수히 많을 수 있다.
- 자주 쓰이는 문제 해결 방법(알고리즘)은 패턴화하기. (BFS, DFS, DP, 다익스트라 등등)
- 각 상황에 적합한 알고리즘을 선택할 수 있어야 한다
2. 알고리즘 평가기준
1. 시간 복잡도: 적은 시간을 잡아먹는 알고리즘
2. 공간 복잡도(메모리): 최대한 적은 용량의 메모리를 사용
3. 구현 복잡도: 간단하게 구현
코테에서는 공간보다는 시간을 더 중요하게 생각한다.
코딩테스트 준비하기
1.시간 복잡도
알고리즘 선택의 기준이 되는 시간 복잡도
시간 복잡도를 정의하는 3가지 유형
- 빅-오메가: 최선일 때 연산 횟수
- 빅-세타: 보통일 때 연산 횟수
- 빅-오 O(n): 최악일 때 연산 횟수
코딩 테스트에서는 O(n)을 기준으로 수행 시간 계산 즉, 최악일 때를 염두에 둬야 한다.
시간 복잡도가 최악 -> 데이터의 크기가 제일 큰 걸로 따지기
연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출
시간 복잡도 도출 기준
- 상수는 시간 복잡도 계산에서 제외 (N == 3N 3배 차이지만 같은 시간 복잡도)
- 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다. (N과 N^2은 차이가 크다.)
2. 디버깅
코드의 오류 - 문법 오류, 논리 오류 -> 문법 오류는 컴파일러가 잡아주니 logic에 집중
가장 뛰어난 논리 오류 탐색 방법은 디버깅 !!
디버깅의 중요성
코테에서 실수를 줄여줄 수 있다.
디버깅하는 법
중단점 설정하고, IDE의 디버깅 기능을 실행해 진행
디버깅 활용 사례
- 변수 초기화 오류
- 인덱스 오류
- 변수 사용 오류
- 파이썬 자동 형변환 오류
'Algorithm > Data Structures' 카테고리의 다른 글
| [자료구조] 스택(Stack) (0) | 2023.09.06 |
|---|---|
| [자료구조] 연결 리스트(Linked list) (0) | 2023.08.28 |
| [자료구조] 배열(Array) (0) | 2023.08.28 |
| [자료구조] 시간복잡도(Time Complexity) (0) | 2023.08.24 |
| [자료구조] 큐(Queue) (0) | 2023.01.17 |