재귀는 강력한 도구지만, 구현 방식에 따라 복잡도와 유지 보수성이 크게 달라질 수 있다.특히 헬퍼 메소드 재귀(helper method recursion) 와 순수 재귀(pure recursion) 는 매우 자주 비교되는 두 가지 재귀 구현 방식이다. 헬퍼 메소드 재귀 (Helper Method Recursion)외부 함수 안에 정의된 내부 헬퍼 함수가 재귀적으로 호출되는 구조외부 함수는 한 번만 호출됨내부의 헬퍼 함수가 재귀 호출을 담당주로 결과값을 누적할 변수(result)를 외부에 선언해서 공유로직이 분리되어 구조가 명확하고 직관적function outer() { let result = []; function helper(input) { // 재귀 호출 } helper(someInput..
1. 재귀란 무엇인가?재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법이다. 이는 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 방식으로, 수학의 귀납법과 유사한 개념이다.재귀를 이해하기 위해 한 가지 이야기를 들어본다. 드래곤은 아래와 같은 숫자를 가지고 있다.[2, 4, 6, 8, 9, 10]우리의 주인공 마틴이, 드래곤에게 말한다."이 숫자 목록에 홀수가 있는지 확인해줘."하지만 드래곤은 마법에 걸려서 오직 첫 번째 숫자만 확인할 수 있다. 그래서 마틴은 다음과 같이 생각한다.첫 번째 숫자가 홀수인지 확인한다. 아니라면 제거한다.남은 목록은 [4, 6, 8, 9, 10]이며, 다시 같은 방식으로 확인한다.4도 홀수가 아니므로 [6, 8, 9, 10]로 넘어간다.6도 홀수가 아니므로 [8, 9..
슬라이딩 윈도우란?슬라이딩 윈도우(Sliding Window)는 배열이나 문자열과 같은 연속적인 데이터에서 특정 크기의 부분 집합을 효율적으로 처리하는 알고리즘 패턴이다. 마치 창문(윈도우)을 한 칸씩 밀어가며 데이터를 살펴보는 것과 같다고 해서 이런 이름이 붙었다.언제 사용할까?연속된 부분 배열의 최대/최소 합 구하기고유 문자로 이루어진 가장 긴 부분 문자열 찾기특정 조건을 만족하는 부분 배열 찾기문제 예시: 연속된 부분 배열의 최대 합정수 배열과 숫자 n이 주어졌을 때, 연속된 n개 요소의 최대 합을 구하는 문제// 예시: [2, 6, 9, 2, 1, 8, 5, 6, 3], n = 3// 결과: 19 (8 + 5 + 6)비효율적인 접근법 (Brute Force)먼저 직관적이지만 비효율적인 방법을 살펴..
다중 포인터(Multiple Pointers) 패턴이란?다중 포인터(Multiple Pointers) 패턴은 인덱스나 위치에 해당하는 포인터(or 값)를 만든 다음, 특정 조건에 따라 중간 지점에서부터 시작 지점-끝 지점 또는 양쪽 지점을 향해 이동시키는 패턴이다.한 쌍의 값이나 조건을 충족시키는 해답을 찾을 때 주로 사용된다. 🔍 예시 문제차례대로 정렬된 숫자 배열이 존재할 때, 두 수끼리 더했을 때 0이 나오는 쌍의 개수를 구하라. sumZero([-4,-3,-2,-1,0,1,2,5]) // 2 (-2,2 / -1,1)다중 포인터 패턴을 적용하지 않았을 때 O(n²)function sumZero(arr){ for(let i = 0; i 시간 복잡도 : O(N^2) 모든 가능한 쌍을 확인한다. ..
[알고리즘] 빈도수 세기 패턴 (Frequency Counter Pattern)
빈도수 세기(Frequency Counter) 패턴이란?빈도수 세기(Frequency Counter) 패턴은 중첩 반복문 없이, 배열이나 문자열 등의 값의 발생 빈도를 객체에 저장해두고 그 정보를 기반으로 문제를 해결하는 방식이다.이 패턴은 시간 복잡도를 O(n²)에서 O(n)으로 줄일 수 있기 때문에 유용하다.🔍 예시 문제배열 arr1과 arr2가 있을 때, arr2가 arr1의 각 원소를 제곱한 값들을 같은 빈도로 포함하고 있는지 확인하는 함수를 만들어보자.same([1, 2, 3, 2], [9, 1, 4, 4]) → truesame([1, 2, 3], [1, 9]) → false빈도수 세기 패턴을 적용하지 않았을 때 O(n²)function same(arr1, arr2) { if (arr1.le..
알고리즘이란?특정 작업을 수행하기 위한 프로세스 또는 일련의 단계. 즉, 우리가 알고리즘 문제를 푼다는 것은 특정 작업을 위한 프로세스를 수립하는 일이 된다. 예를 들자면, 두 수를 덧셈하라는 문제(작업) 를 받았다고 가정해보자. 그렇다면 두 자리를 덧셈하는 함수를 만들고, 결과값을 반환하는 과정이 프로세스일 것이다. 알고리즘 문제를 해결하기 위해서는 어떻게 해야할까? 1. 문제 해결을 위한 계획을 수립문제에 접근하는 방법, 문제를 세분화하기 위한 전략2. 일반적인 문제 해결 패턴을 파악많은 알고리즘들, 특히 면접에서의 많은 문제들을 여러 범주로 나눌 수 있는데, 일부 범주를 식별할 수 있는 경우에는, 도움이 될 몇 가지 조합법을 확보하여 문제 해결을 용이하게 할 수 있다.이 글에서는 우선 문제 해결 계..