알고리즘 공부를 하다보면 재귀함수를 사용하는 경우도 있고, 반복문을 사용하는 경우도 있다. 사용하는 것에는 문제가 없지만 그 둘의 차이가 무엇일까? 재귀함수 vs 반복문 재귀함수는 자기 자신을 호출해는 함수이고, 반복문은 특정 수만큼 반복한다. 일반적으로 반복문이 실행 속도는 더 빠르다. 그 이유는 재귀함수의 경우 매개변수, 리턴값, 리턴 시 돌아가야 하는 위치 등의 정보가 스택에 저장되지만 반복문의 경우 그러한 오버헤드가 없다. 그렇다면 굳이 재귀함수를 사용하는 이유가 무엇일까? 재귀함수는 반복문에 비해서 속도가 느리다는 단점이 있으니, 전부 반복문을 사용해서 해결해도 된다. 하지만 그래도 재귀함수를 사용하는 사람이 있다. 그 이유는 뭘까? 그 이유는 알고리즘을 해결할 때 재귀 함수로 표현하면 더 자연..

문제 설명 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다. 이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들..

순열? 모든 경우의 수를 계산하는 알고리즘이다. ( 순서 고려 O ) [ 1, 3, 5 ] 가 주어졌다면 1 3 5 1 5 3 3 1 5 3 5 1 5 1 3 5 3 1 처럼 모든 경우의 수를 구하는 방법이다. function permutations(arr, n) { if (n === 1) return arr.map((v) => [v]); let result = []; arr.forEach((fixed, idx, arr) => { const rest = arr.filter((_, index) => index !== idx); const perms = permutations(rest, n - 1); const combine = perms.map((v) => [fixed, ...v]); result.push..

재귀 함수를 이용하는 트리 순회는 전위 순회, 중위 순회, 후위 순회가 있다. 전위 순회 루트 노드를 방문하고, 왼쪽 서브 트리를 전위 순회한 뒤 오른쪽 서브 트리를 전위 순회하는 방식이다. 1 / \ / \ 2 3 / \ / \ 4 5 6 7 트리가 있다면 1. 루트 노드 [ 1 ] 을 방문한다. 2. [ 2 ]를 방문한다. 3. [ 2 ]의 왼쪽 서브 트리로 이동한다. 4. [ 4 ]를 방문한다. 5. [ 4 ]의 왼쪽, 오른쪽 서브 트리가 없으므로 올라간다. 6. [ 2 ]의 오른쪽 서브 트리로 이동한다. ... 방식으로 [ 1, 2, 4, 5, 3, 6, 7 ] 순서대로 순회한다. preorder(tree) { 방문(tree.root); preorder(tree.left); preorder(tre..

재귀함수? 자기 자신을 호출하는 함수이다. 이때 호출은 Call Stack에 쌓여서 스택 자료구조와 유사하게 동작한다. 함수형 프로그래밍에선 루프 구현을 재귀로 하는 경우가 많다. 자바스크립트에서의 재귀함수 콜 스택에 제한이 있다. 자바스크립트 엔진마다 다르지만 크롬의 경우 약 1만개이다. 성능이 그렇게 좋지는 않다. 재귀함수를 사용하는 경우 피보나치 수열 앞 두 항의 합이 뒤 항의 값이 되는 수열 function fibonacci(x) { if(x

0. 들어가며 프로그래머스 순위 탐색 문제를 풀다가 배열을 참조해서 순차적으로 배열을 변경하는 경우가 의외로 많이 있는 것 같아서 정리하였다. 1. 사용 방식 예를 들어 [a, b, c, b, e]라는 배열이 있는데, 이것을 [-, b, c, d, e], [-, -, c, d, e], ... [a, b, c, d, -] 순으로 모든 경우의 수를 다 만들어야 하는 상황이 있을 것이다. 그럴 경우에 반복문을 통해서 만들어도 되지만 그렇게 만들려면 배열의 길이는 고정되야하고 배열의 속성 개수에 따라 반복문 개수도 변경되기 때문에 일반적으로 재귀함수를 사용한다. 2. 코드 구현 const info = [ "java backend junior pizza 150", "python frontend senior chi..

문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 100..