250117 TIL - 알고리즘 풀이 회고

소소한 기록

 며칠 전에 꼬리 재귀 이야기를 했는데, 알고보니 자바스크립트가 ES6부터 지원하는 게 맞긴 한데, 정작 브라우저들이 지원을 하지 않는 경우가 있다고.... 그 문제 때문인지는 몰라도, 오늘 풀이했던 문제에서 재귀를 사용하는 버전과 반복을 사용하는 버전의 차이가 심했다!! 미리 정리하자면 반복의 복잡도를 걱정해서 재귀를 쓰는 짓은, 구더기 잡으려고 초가삼간 다 태우는 일이다!!!

재귀 버전

function solution(n, m, section, answer = 0) {
  if (section.length <= 0) return answer;
  
  const paintOnce = section[0] + m - 1;
  const leftWalls = section.filter((wall) => wall > paintOnce);

  return solution(n, m, leftWalls, answer + 1);
}

 먼저 생각해냈던 로직!! 간만에 간결한 풀이가 나와서 싱글 벙글 했고, 나름 꼬리 재귀도 활용했다고 생각하며 즐겁게 제출을 했는디, 이게 웬걸... 30개의 예제중 두 문제가 오버플로우 문제가 발생하더라... 심지어 연산 시간도 몇몇 개는 한참 걸렸는데, 찾아보니 아무리 그래도 재귀는 재귀라더라... 또는 그 알고리즘 풀이하는 브라우저에서 돌리는 연산이 꼬리 재귀가 발동하지 않는 거였을까? 무튼 꽤나 실망스러웠다... 기대했는디

반복 버전

function solution(n, m, section) {
  let answer = 0;
  let idx = 0;

  while (idx < section.length) {
    const paintOnce = section[idx] + m - 1;
    while (idx < section.length && section[idx] <= paintOnce) {
      idx++;
    }
    answer++;
  }

  return answer;
}

 이상하게 반복문을 쓰기 꺼려졌는데 오늘부로 생각이 좀 바뀌었다!!! 재귀 버전에서는 크게는 막 3000ms도 걸리던 연산이었는데, 여기선 길어봐야 400ms 정도 나오더라!! 오버플로우 문제는 당연히 없고!! 예전에 첫 개인 과제 당시 재귀의 오버플로우에 대한 지적을 받고 블로그에 정리한 적이 있었는데, 이렇게 직접 겪어보니 확실히 더 와닿는 거 같다!! 다만 반복문의 종류가 워낙 많고, 아직 완벽히 숙달이 되진 않은 거 같아 연습이 좀 필요할 듯... 특히 while문에 대해 좀 더 공부해보자!!