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