시간복잡도

저번 글에 이어서 시간 복잡도와 관련된 빅 오 표기법(big-O notation), 주먹구구 법칙, NP 문제 등을 다뤄보겠습니다. 시간 복잡도지난 글을 돌이켜보면 알고리즘을 평가할 때 중요한 지표 중 하나는 바로 '시간 복잡도'였습니다. 이 시간 복잡도는 알고리즘이 얼마나 효율적으로 실행되는지를 나타내는 척도로, 알고리즘이 수행하는 기본 연산의 총 횟수를 입력 크기에 따라 나타낸 것입니다. 기본 연산은 더 이상 쪼갤 수 없는 최소 단위의 연산으로, 예를 들어 정수의 사칙연산, 변수 간의 대입, 논리 연산 등이 이에 해당합니다. 이와 달리 배열 정렬, 문자열 비교, 소인수 분해 같은 연산들은 여러 기본 연산을 포함하므로 기본 연산으로 분류되지 않습니다. 시간 복잡도의 핵심은 알고리즘 내부의 '가장 깊이..

알고리즘 공부를 시작하면서 읽었던 ⟪ 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 ⟫ 시리즈에 대한 내용을 정리해보려고 합니다! 책에는 C++ 코드를 위주로 설명하고 있지만, 제가 현재 코딩 테스트나 대회에서 사용하는 파이썬 코드로 따로 정리하고 싶었습니다.먼저 시간 복잡도 분석에 대한 부분입니다. 개요알고리즘의 속도를 효과적으로 측정하는 것은 더 빠른 알고리즘을 개발하는 데 필수적입니다.가장 간단한 방법은 두 알고리즘을 구현하여 동일한 입력에 대한 실행 시간을 비교하는 것이지만, 알고리즘의 효율성을 평가하는 일반적인 기준으로는 부족할 수 있습니다.실행 시간은 다양한 외부 요인에 영향을 받기도 하고, 같은 알고리즘이라도 입력의 크기나 특성에 따라 수행 시간이 달라질 수 있습니다. 알고리즘의 수행 ..