1. 개요나이브 문자열 검색(Naive String Search)은 가장 기본적인 문자열 탐색 기법이다. 이 알고리즘은 긴 문자열 내에서 특정한 짧은 문자열(패턴)이 몇 번 등장하는지를 확인하는 데 사용된다. 2. 알고리즘 개념나이브 문자열 검색은 다음과 같은 방식으로 동작한다.긴 문자열의 각 문자부터 시작하여,짧은 문자열의 길이만큼 잘라서 비교하며,모든 문자가 일치하면 해당 위치를 일치로 간주하고 카운트를 증가시킨다.3. 동작 절차 count를 0으로 초기화한다.긴 문자열의 0번째 문자부터 (긴 문자열 길이 - 짧은 문자열 길이) 위치까지 반복한다.매 반복마다:짧은 문자열의 문자를 하나씩 반복하며,긴 문자열의 i + j 번째 문자와 짧은 문자열의 j 번째 문자를 비교한다.둘 중 하나라도 다르면 비교를 ..
1. 검색이란?특정 데이터(값)를 자료구조 내에서 찾는 과정이다. 배열에서 특정 이름이 있는지 확인로그인 시 입력한 이메일이 DB에 존재하는지 검사2. 선형 검색 (Linear Search)배열의 처음부터 끝까지 순서대로 확인하며 값을 찾는다.정렬 여부와 무관하게 사용 가능하다.[0] → [1] → [2] → ... → [n] ↓ ↓ ↓ ↓val? val? val? val?→ 순차적으로 값을 비교 의사코드 (Pseudocode)배열의 첫 번째 원소부터 시작한다.각 원소를 찾는 값과 비교한다.값이 같으면 해당 인덱스를 반환한다.끝까지 비교했는데 값이 없으면 -1을 반환한다. 예시 코드 (JS)function linearSearch(arr, val) { for ..
재귀는 강력한 도구지만, 구현 방식에 따라 복잡도와 유지 보수성이 크게 달라질 수 있다.특히 헬퍼 메소드 재귀(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) 모든 가능한 쌍을 확인한다. ..