시간 복잡도를 믿고, 나를 의심하기

 

알고리즘과 관련된 코딩을 하다보면, 시간 복잡도 O(n), O(n^2) 이런 것들을 고려해 접근하게 된다.

 

 

예시로 함께 해보자.

 

5x5의 격자에서 랜덤한 위치에 광물이 1개씩 놓여 있다 가정해보자.

이때 한번에 1x3의 크기만을 탐색할 수 있다면, 어떤 부분에서 최대의 광물 수를 확인할 수 있을까?

 

나는 뒤도 돌아보지 않고 2중 for문을 이용해 가능한 모든 직사각형을 탐색할 것이다.

물론 가로로 긴 직사각형만을 가정하자!

 

코드로 확인해본다면,

for i in range(0, 5):
	for j in range(0, 3):
    		//체크

 

세로는 위와 같이 j 인덱스는 5 끝까지 체크하지 않을 것이고,

가로로는 직사각형 가로의 길이

즉 길이 3이 벗어나지 않는 시작점인 2까지만 체크를 해볼 것이다.

 

이렇게 하는 이유는 나름의 최적화 때문이다.

굳이 직사각형의 범위가 넘어가는 부분까지 고려할 필요가 없기 때문이다.

 

시간복잡도는 이중 for문으로, O(n^2)이다.

 

 

그러나 오늘 정말 좋은 코드를 보았다.

 

for i in range(0, 5):
	for j in range(0, 5):
	    	if j+3 > 5: continue
	        //체크

 

 

위와 같은 코드이다.

 

별 차이가 없어 보이지만,

코드를 작성하는 입장에선 확실하게 어떤 조건에서 코드의 흐름이 바뀌는지 알 수 있는 큰 장점이 있다.

 

사실 내가 처음에 작성한 코드는 되게 미묘하게 헷갈리는 부분이 있다.

바로 j 인덱스에 관련된 것인데, "for문의 범위가 정확하게 뭐지?" 라고 헷갈리는 부분이다.

 

'j가 어느 값까지 나올 수 있는거지?' 라는 고민을 하게 되기 때문에,

코딩을 하며 가상의 크기를 머리속에 만들며 시뮬레이션을 해보는 과정을 겪게 된다.

또 이 과정은 정확하지 않을 가능성이 높아 잦은 실수의 원인이 되기도 한다.

(마지막 인덱스를 놓치거나, 넘어서까지 체크하거나!)

 

 

그런데 이 j 범위의 책임을 if 조건문으로 넘기게 된다면, 그런 고민은 확실히 덜 수 있다.

 

"j + 어떤 값" 의 크기가 내가 원하는 조건이 아니라면, 넘겨버린다! 라는 

j 값 범위에 대한 문제에서 보다 다루기 쉬운 조건의 문제로 관점을 변경할 수 있기 때문이다.

 

특이하게 조건문을 활용한 풀이 역시 O(n^2) 이고 이 말은 즉 시간복잡도가 같다는 것이다.

시간 복잡도에서의 손해는 없었지만 머리속에서 헷갈리는 부분은 적어졌으니 스스로 더 명확해진 것이다!

 

 

 

인덱스 값에 제한을 줄 때는 나를 의심하며 마지막 인덱스까지 포함된건가..? 고민하는 시간이 있었지만,

 

이 책임을 조건문으로 넘겨 동일 시간 복잡도에 보다 확실한 조건문을 활용하는 것은 정말 큰 장점인 것 같다!! 정말로!!!

 

 

끘!