[자료구조] 알고리즘 개념

1. 알고리즘이란?

• 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법, 문제를 해결하는 방법
• 한 문제를 해결하는 방법은 한 가지만 있는 게 아니라 무수히 많을 수 있다.
• 자주 쓰이는 문제 해결 방법(알고리즘)은 패턴화하기. (BFS, DFS, DP, 다익스트라 등등)
• 각 상황에 적합한 알고리즘을 선택할 수 있어야 한다

 

2. 알고리즘 평가기준

1. 시간 복잡도: 적은 시간을 잡아먹는 알고리즘

 

2. 공간 복잡도(메모리): 최대한 적은 용량의 메모리를 사용

 

3. 구현 복잡도: 간단하게 구현 

코테에서는 공간보다는 시간을 더 중요하게 생각한다.

 

코딩테스트 준비하기

 

1.시간 복잡도

알고리즘 선택의 기준이 되는 시간 복잡도

시간 복잡도를 정의하는 3가지 유형

• 빅-오메가: 최선일 때 연산 횟수
• 빅-세타: 보통일 때 연산 횟수
• 빅-오 O(n): 최악일 때 연산 횟수

 

코딩 테스트에서는 O(n)을 기준으로 수행 시간 계산 즉, 최악일 때를 염두에 둬야 한다.

시간 복잡도가 최악 -> 데이터의 크기가 제일 큰 걸로 따지기

연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출

 

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외 (N == 3N 3배 차이지만 같은 시간 복잡도)
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다. (N과 N^2은 차이가 크다.)

 

 

2. 디버깅

코드의 오류 - 문법 오류, 논리 오류 -> 문법 오류는 컴파일러가 잡아주니 logic에 집중

가장 뛰어난 논리 오류 탐색 방법은 디버깅 !!

 

디버깅의 중요성 

코테에서 실수를 줄여줄 수 있다.

 

디버깅하는 법

중단점 설정하고, IDE의 디버깅 기능을 실행해 진행

 

디버깅 활용 사례

• 변수 초기화 오류
• 인덱스 오류
• 변수 사용 오류
• 파이썬 자동 형변환 오류