들어가기 앞서서…

본 글은 코딩 테스트 겸 알고리즘을 제대로 공부하기 위하여 기존에 공부를 했던 내용을 다시 요약 복습하는 글입니다 :)

따라서 내용이 많이 생략 되어 있으며, 원문을 보시고 싶으시면 저의 블로그 원본 글을 참조해 주세요.

또한 본 내용은 이것이 취업을 위한 코딩테스트다 라는 교재의 내용 + 유튜브 인강을 기반으로 되어 있으니, 직접 학습하시는 것도 좋다고 생각됩니다.

해당 게시물 원본 링크

복잡도

복잡도의 개념

• 복잡도는 알고리즘의 성능을 나타내는 척도입니다.
  • 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘 수행 시간을 분석합니다.
  • 공간 복잡도 : 특정 크기의 입력에 대해 알고리즘 메모리 사용량을 분석합니다.
• 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이라고 보시면 됩니다.
• 여기서 낮은 경우는 시간, 공간 모두 속하지만, 오히려 시간과 공간은 반비례 하는 경향이 있습니다.

빅오 표기법(Big-O Notation)

• 가장 빠르게 증가하는 항 만을 고려하는 표기
• 예를 들어 연산 회수가 3𝐍³ + 5𝐍² + 100000 인 알고리즘이 있다고 할 때.. ⇒ 빅오 표기시 가장 큰 차수의 항만 남깁니다.
• 왜냐하면 자료가 커지고 연산횟수가 증가한다고 하면, 최초 3𝐍³ 항만이 전체 값중 가장 큰 비중을 차지하고 컴퓨터 입장에선 당연히 엄청난 양의 데이터를 처리하는 만큼 ‘가장 큰 항’을 제외한 나머지는 비중적으로 크지 않기에 복잡도 분석을 위해 사용되는 개념이라고 보시면 되겠습니다.

시간 복잡도 계산 예제

array = [3, 5, 1, 2, 4] # 5개의 데이터
summary = 0

for x in array;
	summary += x # 모든 데이터를 하나씩 확인하며 합계를 계산
# 결국 전체 프로그램의 연산량을 좌우하는 것은 이 부분...

print(summary)
# 최종적으로 n 개 만큼의 연산작업이 소요되므로 시간복잡도는 𝑂(𝑁)

array = [3, 5, 1, 2, 4]

for i in array: # n 번 수행함
	for j in array: # 각 경우당 다시 n 번 진행함.
		temp = i * j
		print(temp)
# 최종적으로 각 N개의 항에 대해 항 당 N개를 수행하므로 시간복잡도는 𝑂(𝑁²)

알고리즘 설계의 팁

팁