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..