꼬리 퇴뀌오늘 공부한 내용 🌦️
BFS와 DFS, 그리디 알고리즘을 배우고 실습 문제를 풀었다.
리마인드된 내용 🔨
splice
실습 문제를 풀다가 splice 관련해서 실수가 있는 바람에 고난을 겪었다.
심지어 코스 초반에 slice와 splice의 차이 및 원본 배열 변경 여부에 조심해서 사용하라는 글도 보고 문제를 풀 때조차 이를 고려해야겠다는 생각을 하면서 풀었는데도 실수를 했다.
내가 했던 실수는 대략 다음과 같은 코드이다.
routes.push({
route: [...route, dest],
curTickets: [...curTickets].splice(idx, 1),
});routes라는 리스트에 넣어줄 때 curTickets의 요소 중 하나만 제거해서 객체를 넣으려는 코드이다.
내가 착각한 것은 원본 배열의 복사본 [...curTicket] 에 splice 를 했으니 한 요소가 삭제된 복사본이 전달 될 것이라고 생각했다는 점이다.
실제로는 복사된 배열이 아닌 splice 의 리턴값인 제거된 요소가 반환되어 전달된다.
함수형 프로그래밍에 익숙하지 않아서 그랬던 것 같다.
DFS 스택
그동안 알고리즘 문제를 풀 때 파이썬을 주로 사용하였는데 그 땐 DFS를 구현할 때 재귀함수로 구현하는 게 편하다고 느껴져서 재귀함수만 사용했다.
문제는 그거만 하다보니 다른 구현 방법의 가능성을 아예 까먹고 있었다.
DFS는 스택으로도 구현이 가능하다.
인접 요소들을 스택에 push하고 pop하면서 순회를 하는 방식으로 구현된다.
너무 편한 것도 문제다.
삼천포 ⚓
자바스크립트의 재귀함수
DFS와도 연관이 있는 내용인데 자바스크립트에서는 재귀함수의 성능이 특히 좋지 않기 때문에 되도록 사용하지 말라는 내용을 지나가듯 보았던 것 같다.
때문에 문제를 풀 때도 재귀가 필요한 부분은 반복문으로 대체해서 사용하고 있었다.
하지만 왜 성능이 좋지 않은 지에 대해선 찾아보지 않아서 알아보고자 한다.
결론은 그런거 없다.
분명 어디선가 봤었는데 대체 뭐지..
물론 그렇다 하더라도 재귀함수 자체가 스택 메모리에서 손해를 보고 가독성을 얻는 방법이라는 것은 바뀌지 않으니 굳이 쓸 필요는 없을 것 같다.
변화된 생각 🥏
강의에서 자바스크립트의 재귀 성능에 대한 내용이 나오길래 다시 검색해보았다.
요즘 프로그래밍 언어들의 최적화된 컴파일러 환경에서는 재귀함수를 사용하여도 유의미한 손해를 보는 정도는 아니기 때문에 가독성이나 효율성 측면에서 이점을 얻을 수 있다면 고려할 수 있다고 한다.
자바스크립트의 경우 재귀하는 부분만이 구현된 고차함수인 reduce를 주로 사용하기 때문에 실제로 재귀함수를 구현하는 경우는 적다고 한다.
꼬리 재귀
위 내용에 대해 검색해보다 찾았다.
재귀함수의 특별한 형태인데 모든 코드나 연산이 끝나고 마지막 return 문에 함수 호출 하나만 하도록 구성한 재귀방식을 꼬리 재귀라고 한다.
대체로 parameter에 accumulator 역할을 하는 변수를 전달시켜 구현하는 것 같다.
이것도 이론적으로는 재귀함수처럼 콜 스택에 함수 관련 데이터가 쌓이게 되지만 실제 컴파일러 환경에서 선형적으로 최적화가 이루어진다.
모든 연산이 끝나면 함수 데이터를 유지할 필요가 없어지므로 새 함수 데이터로 덮어씌워져 스택에 부담이 훨씬 덜하다.
다만, 해당 플랫폼의 컴파일러가 최적화 기능을 지원해야 가능한 방식이다.
느낀점 🎬
들은 것도 제대로 못 써먹는데 이상한 걸 듣고 써먹는 상태가 되버렸다.
글을 쓰면서 하나하나 검증해보는 게 이런 오류를 줄이는데 도움이 되겠거니 하면서 꾸준히 써봐야겠다.
참고
