알고리즘 기초

시간 복잡도와 언어별 유의점

알고리즘 효율성

시간

메모리

숏코딩 → 의미없다. 그냥 잘 알아보게 쓰는게 중요한 거

크기를 나타내는 N, 문제의 가지수, 갯수를 의미함.

문제의 크기를 먼저 보고 방법을 생각해야한다.

구현하기 전에 시간이 얼마나 걸릴지 예측해봐야한다. → 시간 복잡도

코드를 보고 하던가, 방법을 이용해서 미리 계산해보고 구현하던가

다양한 표기법이 있지만 Big-O만 사용한다.

N이 1억일 때 O(N)은 1초즈음 걸린다. 물론 1초보다 약간 더 빠르다.

문제에는 시간 제한이 있다. 안되는 알고리즘 방법을 걸러낼 때 사용.

보통 가장 많은 공간을 사용하는 것은 보통 배열

배열이 사용한 공간: 배열의 크기 * 자료형의 크기 바이트

크기가 배열인 배열 → 4MB 즈음 된다.

근데 보통 엄청 크기 때문에 큰 상관X

메모리초과를 갖는 경우 → 중복되는 값을 계속 저장하거나, 불필요한 공간을 계속 사용하거나

C++ : cin, cout보다 느리다.

몇 백만개 정도면 많은 편인데 그러면 몇 가지 옵션을 주면 된다.

ios_base::sync_with_stdio(false);

cin.tie(nullptr);

입출력도 유형이 나뉜다.

그냥 입출력만 해도 되고

테스트 케이스 문제 → 테스트 케이스 개수를 주어주고, 그 만큼 반복해야한다.

입력 받으면서 출력해주면 된다.

입력이 EOF일 때까지 받으면 된다. 

while(cin >> a >> b)

for(int i=0; i<strlen(s); i++){
	
}

s의 길이를 N이라고 하면 O(N^2)이다.
이럴거면 strlen을 저장해놓고 반복문 돌린다.
C++은 문자열 길이를 재는 시간이 O(n)
JavaScript
복사

c++

s += "A" -> O(n)
s = s + "A" -> O(n^2)이다. 길이가 점점 길어질 수록, n번 n이 걸리는 작업을 하니까 O(n^2)
JavaScript
복사

java → 무조건 새로운 문자열을 만든다. 따라서 + 연산자가 무조건 O(n^2). 이러기 싫으면 string builder를 쓰자.