All Categories

앞선 포스트에서 시간복잡도와 공간복잡도에 대한 개념에 대해 알아보았다. 복잡도란 언급했듯이 특정한 알고리즘이 계산적으로 얼마나 복잡한지를 나타내는 것이다. 파이썬에서는 실제로 프로그램 수행 시간과 메모리 사용량을 측정할 수 있다. 시간복잡도의 개념에서 프로그램의 수행 시간을 측정하는 것은 해당 알고리즘이 복잡도 측면에서 얼마나 효율적인 지를 측정하는 것과 같다고 할 수 있다. 파이썬에서 수행 시간을 측정하는 소스코드는 아래와 같다. import time start_time = time.time() # 시간 측정 시작 #프로그램 소스코드 end_time = time.time() # 시간 측정 완료 print("time : ", end_time - start_time) # 수행시간 (시작 시간 - 완료 시간..

공간복잡도란 쉽게 말해 소스코드에서 메모리를 사용하는 양이라고 할 수 있다. 공간복잡도 또한 시간복잡도와 마찬가지로 빅오 표기법을 사용하여 표기한다. 즉 O(N), O(log N)등과 같이 표기하는 것이다. 코딩 테스트에서 아래와 같은 문제 조건을 볼 수 있는데 이는 시간복잡도와 공간복잡도에 제한을 두기 위해서이다. '시간 제한 1초, 메모리 제한 128MB' C언어에서 기본자료형의 메모리 크기는 아래와 같다. 자료형 키워드 메모리 크기 문자형 char 1 Bytes 정수형 short 2 Bytes int 4 Bytes long 4 Bytes 부호없는 문자형 unsigned char 1 Bytes 부호없는 정수형 unsigned short 2 Bytes unsigned int 4 Bytes unsigne..

복잡도란 알고리즘의 성능을 나타내는 척도이며 시간복잡도(Time complexity)는 특정한 크기의 입력에 대해 알고리즘이 시간을 얼마나 소요하는지를 나타낸다. 시간복잡도를 표현할 때는 일반적으로 빅오표기법을 사용한다. 알고리즘 문제를 풀 때 단순히 '복잡도'라고 한다면 시간복잡도를 의미한다. 코딩 테스트에서의 시간제한은 시간내에 문제를 풀어야 한다는 제한보다는 작성한 프로그램이 모든 입력을 받아서 이를 실행하고 결과를 출력하는 데 까지 소요되는 시간의 제한을 의미한다. 시간복잡도를 계산할 때 N개의 데이터에 대한 연산의 횟수에 의존하는 경우가 많다. 아래의 예시들을 통해서 시간복잡도를 이해해본다. 더보기 예시1) 위의 예시는 N=5의 데이터의 총합을 계산하는 코드이다. 이 때 연산횟수는 데이터의 개수..

복잡도란 알고리즘의 성능을 나타내는 척도이다. 복잡도에는 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)가 있다. 시간복잡도는 특정한 크기의 입력에 대해 알고리즘이 시간을 얼마나 소요하는지를 나타내고 공간복잡도는 특정한 크기의 입력에 대해 알고리즘이 메모리를 얼마나 차지하는지를 나타낸다. 일반적으로 적은 시간을 소요하고, 적은 메모리를 차지하는 것이 좋은 알고리즘이라는 것은 자명한 사실이다. 복잡도를 표기하는 방법에는 여러가지 방법이 있다. 빅오(Big-O)표기법 빅오메가(Ω)표기법 빅세타(Θ)표기법 빅오(Big-O)표기법 먼저 빅오(Big-O)표기법이란 쉽게 말해 함수의 상한(upper-bound)만을 고려하는 표기법이다. 즉, 가장 빠르게 증가하는 항만을 고려하는..