Search
Duplicate

알고리즘 박살내기 - 02. 알고리즘의 성능 평가

간단소개
본 글은 알고리즘 공부를 체계적으로 진행하기 위해 멋데로 복습 겸 정리하는 글입니다.
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
Algorithm
태그
코딩테스트
파이썬
c++
Scrap
8 more properties

들어가기 앞서서…

본 글은 코딩 테스트 겸 알고리즘을 제대로 공부하기 위하여 기존에 공부를 했던 내용을 다시 요약 복습하는 글입니다 :)
따라서 내용이 많이 생략 되어 있으며, 원문을 보시고 싶으시면 저의 블로그 원본 글을 참조해 주세요.
또한 본 내용은 이것이 취업을 위한 코딩테스트다 라는 교재의 내용 + 유튜브 인강을 기반으로 되어 있으니, 직접 학습하시는 것도 좋다고 생각됩니다.

복잡도

복잡도의 개념

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

빅오 표기법(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 개 만큼의 연산작업이 소요되므로 시간복잡도는 𝑂(𝑁)
Python
array = [3, 5, 1, 2, 4] for i in array: # n 번 수행함 for j in array: # 각 경우당 다시 n 번 진행함. temp = i * j print(temp) # 최종적으로 각 N개의 항에 대해 항 당 N개를 수행하므로 시간복잡도는 𝑂(𝑁²)
Python

알고리즘 설계의 팁

일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터는 연산 횟수가 5억을 넘어가는 경우 :
C언어 기준으로 통상 1~3초 가량 시간의 소요됩니다.
파이썬 기준 5~15초 가량 시간이 소요 됩니다.
PyPy 의 경우 때때로 C 보다 빠르게 동작할수도 있습니다. 코딩테스트 문제에서 시간제한은 통상 1~5초 가량이라는 점을 유의 해야 합니다.(pypy?)
문제에 제한 시간이 명시되지 않은 경우 약 5초라고 생각하고 문제를 푸는 것이 합리적인 기준치라고 생각하시면 될 것입니다.

요구사항에 따라 적절한 알고리즘 설계하기

위의 기초적인 기준 아래에 우리는 보통 이런 평균 기준을 갖고 코딩을 하게 됩니다.
문제에서 가장 먼저 확인할 내용은 시간제한(수행시간 요구사항) 입니다.
시간제한이 1초 문제를 만났을 때, 일반적인 기준
N의 범위 500 :O(𝐍³)
N의 범위 2,000 : O(𝐍²)
N의 범위 100,000 : O(𝐍㏒𝐍)
N의 범위 10,000,000 : O(𝐍)

알고리즘 문제 해결 과정

일반적인 알고리즘 문제 해결 과정은 다음과 같이 접근하시면 됩니다. 1. 지문 읽기 및 컴퓨터적 사고 2. 요구사항(복잡도) 분석 3. 문제 해결을 위한 아이디어 찾기 4. 소스코드 설계 및 코딩
일반적으로 대부분의 문제는 출제자들은 핵심 아이디어를 캐치한다면 간결하게 코드를 작성할 수 있는 형태로 문제를 출제됩니다.

수행시간 측정 코드 예제

import time start_time = time.time() # 측정 시작 # 프로그램 소스 코드 end_time = time.time() # 측정 종료 print("time:", end_time - start_time) # 수행시간 출력
Python