알고리즘 기초

알고리즘 문제를 풀면서 어떤 방법으로 접근 해야하는지 답답하여 알고리즘 공부법을 찾아 보다가 알고리즘에도 종류가 있고 기법 같은게 있다는 것을 알았다. 무턱대고 푼 과거의 나 자신을 칭찬한다...

복잡도(complexity)

복잡도는 알고리즘의 성능을 보여주는 기준이다.

복잡도에는 시간 복잡도(수행시간 분석) 공간복잡도(메모리 사용량 분석)가 있다.

복잡도가 낮을수록 좋은 알고리즘이다!

알고리즘 성능 평가에서 빅오 표기법(Big-O Notation)을 이용 할 수 있다.

자신이 짠 소스코드의 시간복잡도 정도는 빅오 표기법으로 유추할 수 있어야 한다.

빅오 표기법 : 함수의 가장 큰 항만을 고려한다!

aN^3 + bN^2 + c

이와 같은 알고리즘이 있을 경우 여기서 가장 큰 항인 N의 3승 만을 고려한다. 상수 부분을 생각하지 않아도 된다!

O(1) 상수 시간

O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간
O(n!)	팩토리얼 시간

위에서 아래로 갈수록 성능이 떨어지고 안 좋은 알고리즘이다!

array =  [1, 2, 3, 4, 5] #5개의 데이터
summary = 0 #합계를 저장 할 변수 

for x in array: #모든 데이터를 하나씩 호출 후 합계 계산
	summary += x

print(summary) # 합을 출력

위와 같이 코드를 작성하면 수행시간이 데이터 개수와 비례하는 것을 알 수 있다.

시간 복잡도: O(N)

알고리즘 문제 해결 과정

1. 지문을 읽고 요청내용을 컴퓨터적 사고로 전환
2. 요구사항(복잡도) 분석
3. 문제해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩

알고리즘 문제 유형

1. 그리디, 구현
2. DFS, BFS
3. 정렬 알고리즘
4. 이진탐색
5. 다이내믹 프로그래밍
6. 최단 경로 알고리즘
7. 기타

결론:

알고리즘 문제에 대한 해결 아이디어를 떠올릴 수 있는 연습이 많이 필요하다!