알고리즘과 관련된 코딩을 하다보면, 시간 복잡도 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) 이고 이 말은 즉 시간복잡도가 같다는 것이다.
시간 복잡도에서의 손해는 없었지만 머리속에서 헷갈리는 부분은 적어졌으니 스스로 더 명확해진 것이다!
인덱스 값에 제한을 줄 때는 나를 의심하며 마지막 인덱스까지 포함된건가..? 고민하는 시간이 있었지만,
이 책임을 조건문으로 넘겨 동일 시간 복잡도에 보다 확실한 조건문을 활용하는 것은 정말 큰 장점인 것 같다!! 정말로!!!
끘!
'CS' 카테고리의 다른 글
equal의 동작 방식과 최적화 (2) | 2024.04.01 |
---|