문제해결패턴
-
알고리즘, 문제해결패턴, RecursionData Structure & Algorithm 2024. 6. 13. 20:09
재귀(Recursion)는 함수가 자기 자신을 호출하여 문제를 해결하는 기법입니다. 재귀는 문제를 작은 부분 문제로 나누어 해결할 때 특히 유용하며, Divide and Conquer와 같은 알고리즘 기법과 자주 결합됩니다. 재귀를 사용하려면 기본 조건(base case)과 재귀 조건(recursive case)을 정의해야 합니다.기본 개념기본 조건 (Base Case): 재귀 호출을 멈추는 조건입니다. 더 이상 문제를 쪼갤 수 없을 때 기본 조건을 사용하여 결과를 반환합니다.재귀 조건 (Recursive Case): 함수가 자기 자신을 호출하는 부분입니다. 문제를 더 작은 부분으로 쪼개고, 그 부분을 해결하기 위해 다시 함수를 호출합니다.예제예제 1: 팩토리얼 계산팩토리얼은 1부터 n까지의 정수를 모두..
-
알고리즘, 문제해결패턴, Divide and ConquerData Structure & Algorithm 2024. 6. 12. 22:02
Divide and ConquerDivide and Conquer의 기본 개념은 다음과 같습니다:분할(Divide): 해결해야 할 문제를 동일한 유형의 더 작은 부분 문제로 나눕니다.정복(Conquer): 각 부분 문제를 재귀적으로 해결합니다. 부분 문제가 충분히 작으면 직접 해결합니다.결합(Combine): 부분 문제의 해를 합쳐서 원래 문제의 해를 얻습니다.예제예제 1: 병합 정렬 (Merge Sort)병합 정렬은 Divide and Conquer를 사용하는 대표적인 정렬 알고리즘입니다. 배열을 반으로 나눈 후 각각을 정렬하고, 정렬된 부분 배열을 합칩니다.function merge(arr1, arr2) { let idx1 = 0; let idx2 = 0; let result = []; whi..
-
알고리즘, 문제 해결 패턴, Sliding WindowData Structure & Algorithm 2024. 6. 12. 21:37
Sliding WindowSliding Window는 프로그래밍에서 배열이나 문자열과 같은 연속된 데이터 구조 내에서 부분 집합의 합, 평균, 최대값 또는 최소값 등을 효율적으로 계산하기 위해 사용하는 알고리즘 기법입니다. 이 기법은 고정된 크기나 가변 크기의 윈도우를 사용하여 문제를 해결합니다.기본 개념Sliding Window의 기본 개념은 다음과 같습니다:윈도우 설정: 초기 윈도우 크기나 시작점을 설정합니다.윈도우 이동: 데이터를 한 번에 하나씩 이동하면서 윈도우 내 값을 갱신합니다.결과 갱신: 윈도우 내 값을 기준으로 필요한 결과를 갱신합니다.예제예제 1: 고정된 크기의 윈도우를 사용한 최대 합 찾기다음은 고정된 크기의 윈도우를 사용하여 배열 내 연속된 요소들의 최대 합을 찾는 예제입니다.func..
-
알고리즘, 문제해결 패턴, Mulitple PointersData Structure & Algorithm 2024. 6. 12. 21:35
Mulitple PointersMultiple Pointers의 기본 개념은 다음과 같습니다:포인터 설정: 배열이나 문자열의 시작과 끝, 또는 특정 조건에 따라 포인터를 설정합니다.포인터 이동: 특정 조건을 만족할 때까지 포인터를 이동합니다.조건 만족 확인: 포인터가 특정 조건을 만족하는지 확인하여 문제를 해결합니다.시간 복잡도Multiple Pointers를 사용하는 알고리즘의 시간 복잡도는 일반적으로 O(n)입니다. 이는 배열이나 문자열을 한 번만 순회하면서 문제를 해결하기 때문입니다.활용 예시Multiple Pointers 기법은 다음과 같은 다양한 문제에서 유용하게 사용됩니다:두 개의 포인터를 사용하여 배열 내 특정 조건을 만족하는 요소 찾기중복 요소 제거문자열 내 특정 패턴 찾기정렬된 배열에서 ..