들어가기 앞서서…
본 글은 코딩 테스트 겸 알고리즘을 제대로 공부하기 위하여 기존에 공부를 했던 내용을 다시 요약 복습하는 글입니다 :)
따라서 내용이 많이 생략 되어 있으며, 원문을 보시고 싶으시면 저의 블로그 원본 글을 참조해 주세요.
또한 본 내용은 이것이 취업을 위한 코딩테스트다 라는 교재의 내용 + 유튜브 인강을 기반으로 되어 있으니, 직접 학습하시는 것도 좋다고 생각됩니다.
복잡도
복잡도의 개념
•
복잡도는 알고리즘의 성능을 나타내는 척도입니다.
◦
시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘 수행 시간을 분석합니다.
◦
공간 복잡도 : 특정 크기의 입력에 대해 알고리즘 메모리 사용량을 분석합니다.
•
동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이라고 보시면 됩니다.
•
여기서 낮은 경우는 시간, 공간 모두 속하지만, 오히려 시간과 공간은 반비례 하는 경향이 있습니다.
빅오 표기법(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초 가량 시간이 소요 됩니다.
◦
◦
문제에 제한 시간이 명시되지 않은 경우 약 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
복사
