1주차 개념 #8. 공간복잡도(space complexity)

1주차 개념 #8. 공간복잡도(space complexity)

공간 복잡도에 대해서 얘기를 해보도록 할게요.

공간 복잡도는 입력 크기에 대해서 어떠한 알고리즘이 실행되는데 필요한 메모리 공간의 양이에요.

그러니까 예를 들어서 저희가 어떤 변수를 선언을 한다던가, 어떠한 요소들을 배열이든, map이든, set이든 담을 공간이 필요하다면, 사실은 이런 것들이 다 컴퓨터 메모리에 올라가게 되거든요.

그런 양을 뜻하는 게 바로 공간 복잡도다 라는 겁니다.

이는 정적변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할경우도 포함하며, 배열이든 맵이든 셋이든 요소들을 담을 공간이면 다 적용됩니다.

이거 보시면은 a[10000000]가 지역변수고 b[1004]가 전역 변수잖아요. 이거 두 개 다 포함해서 공간 복잡도를 설명을 합니다.

그리고 이게 좀 있는데, 예를 들어서 재귀함수를 작동하게 되잖아요?

예를 들어서 기저사례가 이러한 재귀함수가 있다라고 쳐요.

그러면 공간 복잡도를 표현할 때 이 함수가 작동될 때의 메모리도 포함하곤 해요.

근데 이제 재귀함수를 사용한다고 했을 때 그러한 함수가 매번 호출되게 되면서 메모리를 잡아먹곤 하는데 공간 복잡도를 따질 때는 그것까지 계산하는 데는 좀 무리가 있어요.

그래서 보통은 이런 식으로 배열이나 map, set 이러한 공간에 대해서만 하는 겁니다.

물론 재귀함수 자체도 사실은 메모리를 잡아먹어요. 근데 이런 거를 계산하기가 너무 힘드니까 보통은 배열이나 맵, 셋 그런 공간적인 자료구조들만 계산을 한다는 거예요.

자 예를 들어 입력이 N이 들어왔고 거기에 따라 N개 짜리 int형 요소를 담아야 할 공간이 필요하다면 4N바이트의 공간이 필요하겠죠.

지금 배열의 크기가 N 정도가 필요한데, int가 4바이트 잖아요. 그러니까 4N의 공간 복잡도가 필요한 거죠.

자 이거를 빅오 표기법으로 나타내면 상수인자는 제거되니까 O(n)이 되죠.

자 그런데 사실은 이런 공간 복잡도라는 개념은 문제를 푸는데 잘 사용이 안 돼요.

저희가 앞서서 배웠던 시간 복잡도는 문제를 풀 때 많이 사용되거든요. 근데 공간 복잡도는 그렇지가 않아요.

그래서 보통 문제를 풀 때는 공간, 배열의 범위를 잡을 때는 두 가지 방법을 기반으로 잡습니다.

자 팁 두 가지 들어갑니다.

첫 번째는 최대 범위예요. 그러니까 대부분의 문제는 최소 범위가 있거든요. 그걸 기반으로 배열을 만들곤 해요. 이 문제에서 n의 최대 범위는 얼마죠? 100만이에요. 그러니까 100만을 int a[1000000]; 이렇게 미리 선언하는 거죠.

그러니까 문제의 최대 범위를 보고 그걸 기반으로 선언을 한다라는거에요.

자 두번째는 메모리 제한을 참조를 합니다.

자 다음과 같은 문제에서 메모리 제한은 512MB에요. 즉, 5억 1200만 바이트에요. 그러면 배열의 크기를 1억 2천 8백만 바이트를 선언할 수 있겠죠? 왜냐면 int형이 4바이트니까 나누기 4를 한 거예요.

자 그러면 실제로 이걸 할 수가 있는지 테스팅을 해 볼게요.

실제로 이 문제 같은 경우는 2차원 배열이 필요해서 이렇게 쪼개서 테스팅을 해본 거예요.

여러분 연구소는 지금 풀 필요는 없어요. 지금 레벨에서는 못 풉니다.

자 이렇게 해서 집어 넣어 볼게요.

메모리를 많이 쓰긴 했지만, 2번 방법인 메모리 제한을 보고 이렇게 설정하는 거는 사실은 하지 않는 게 좋아요.

왜냐하면 메모리 제한을 미리 보고 그걸 기반으로 해서 나누기 4를 해가지고 1억 2천 8백만 이런 식으로 계산하는 것 자체가 사실은 코딩 테스트나 알고리즘 문제를 풀 때 생각하기 힘들어요.

그래서 여러분 이건 팁인데, 그냥 1000만까지는 어느정도 된다 라고 보시면 돼요.

제가 두가지를 설명을 드렸죠. 공간 복잡도가 어떻게 설정되는지 설명을 드렸지만 공간 복잡도는 O(N)처럼은 사용이 잘 안되고요.

문제를 풀 때는 첫번째 최대 범위, 그리고 두번째는 메모리 제한을 봐라 라고 제가 설명을 드렸는데, 이 메모리 제한 같은 경우는 사실은 실전에서는 하기가 힘들어요. 그래서 이거 같은 경우에는 어떻게 하냐? '그냥 1000만까지는 해보자!'

그러니까 문제의 최대 범위를 미리 설정하는 경우에는 문제의 입력을 받을 때 보통 활용이 돼요. 그리고 나서 이 입력 말고 문제에서 필요한 로직이 있을 거에요. 그 로직에 필요한 어떤 공간, 뭐 배열이나 맵이나 셋이 됐든, 배열을 예로 들게요. 배열에서 1000만짜리가 필요하다 라고 했을 때 '내 로직이 잘못됐나'라고 한 번 생각을 해봐야 된다는 거에요.

그러니까 1000만이 상한값이 된다는 거에요. 물론 문제마다 달라요. 아까 보여드린 연구소 문제는 1억짜리 배열이 잘 먹힌 거예요.

이런 것도 있지만 대부분의 문제는 보통은 1000만짜리 배열은 잘 안 먹혀요.

이거를 알고 들어가시면 조금 더 문제를 빠르게 풀 수 있다라는 거예요. 완전 꿀팁입니다.

그리고 또 있는데 지금은 안 풀지만 나중에는 그 펜윅 트리라는 것도 배우고요. 이분 탐색이라는 것도 배워요.

이게 좀 다른 알고리즘이긴 한데 얘네 둘, 이 두 개의 다른 알고리즘이 공통 분모가 있어요.

뭐냐면 어떠한 유동적인 배열, 다이나믹한 Array에서 어떤 요소를 logN만에 찾을 수가 있어요. 근데 펜윅 트리는 무조건 새로이 배열을 만들어야 돼요. 이분탐색은 새로 안 만들어도 돼요.

그러니까 만약에 내가 펜윅 트리를 쓰는데, 이런 식으로 logN만에 찾는 로직이 필요하고, 근데 배열을 새로 만들려고 하다 보니까 1000만짜리가 필요한다고 그러면, 펜윅 트리보다는 이분탐색을 선택해야 된다라는 거예요.

 

그러니까 1000만이라는 기준이 '아 내가 다른 알고리즘을 사용해 볼까?', '펜윅 트리 말고 이분탐색을 사용해볼까?' 라는 기준이 된다라는 거예요. 이건 팁이라서 100% 맞는 건 아니에요. 일단 문제를 풀 때 이런식으로 대강 감을 잡고 가야 된다라는 거예요.

 

이렇게 해서 공간 복잡도를 배워봤습니다. 일단 공간 복잡도라는 개념은 입력 크기에 대해서 어떠한 알고리즘이 실행되는데 필요한 메모리 공간 양이구요.

문제를 풀 때는 최대 범위나 메모리 제한을 쓰는데, 메모리 제한 같은 경우는 잘 사용이 안 되고 보통은 1000만 잡고 들어가시는 게 좋다고 말씀을 드렸습니다.