Introduction

본 포스트는 알고리즘 학습에 대한 정리를 재대로 하기 위하여 남기는 것입니다. 더불어 기본 내용은 나동빈 저의 〖이것이 취업을 위한 코딩 테스트다〗라는 교재 및 유튜브 강의의 내용에서 발췌했고, 그 외 추가적인 궁금 사항들을 검색 및 정리해둔 것입니다.

복잡도

복잡도의 개념

  • 복잡도는 알고리즘의 성능을 나타내는 척도입니다. 우리는 쉽게 눈에 보이는 코드의 복잡도로 코드를 판가름 할 수 있지만, 사실 컴퓨터 시스템에서의 복잡도라는 것은 사람과는 다르게 작동하고, 자원을 효율적으로 사용해야하는 필연적인 상황 상 컴퓨터의 복잡도를 알고 접근하냐 모르냐는 매우 중요한 부분이라 할 수 있습니다.
    • 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘 수행 시간을 분석합니다.
    • 공간 복잡도 : 특정 크기의 입력에 대해 알고리즘 메모리 사용량을 분석합니다.
  • 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이라고 보시면 됩니다.

빅오 표기법(Big-O Notation)

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

시간 복잡도 계산 예제

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

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

print(summary)
array = [3, 5, 1, 2, 4]

for i in array: # n 번 수행함
	for j in array: # 각 경우당 다시 n 번 진행함.
		temp = i * j
		print(temp)

알고리즘 설계의 팁

팁

  • 이 파트는 알고리즘 문제들을 해결하기 위해 알아두면 좋은 토막상식들입니다.
  • 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터는 연산 횟수가 5억을 넘어가는 경우 :
    • C언어 기준으로 통상 1~3초 가량 시간의 소요됩니다.
    • 파이썬 기준 5~15초 가량 시간이 소요 됩니다.
      • PyPy 의 경우 때때로 C 보다 빠르게 동작할수도 있습니다.
  • 코딩테스트 문제에서 시간제한은 통상 1~5초 가량이라는 점을 유의 해야 합니다.
    • 문제에 제한 시간이 명시되지 않은 경우 약 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) # 수행시간 출력

🧑🏻‍💻 알고리즘 박살내기 시리즈🧑🏻‍💻