알고리즘 (4) 썸네일형 리스트형 [Algorithm] 완전 탐색(Exhaustive search)과 브루트 포스(Brute Force) 완전탐색(Exhaustive search)과 브루트포스(Brute Force) 알고리즘은 모든 가능한 경우의 수를 탐색하여 문제를 해결하는 방법입니다1. 완전탐색 (Exhaustive search)완전탐색은 모든 경우의 수를 다 만들어 보는 방법입니다.이 방법은 컴퓨터의 빠른 계산 능력을 이용하여 가능한 모든 경우를 일일이 나열하면서 답을 찾습니다 2. 완전 탐색의 종류완전 탐색은 문제의 구조에 따라 다양한 방법으로 구현될 수 있습니다.브루트 포스 (Brute Force): 반복문과 조건문을 사용하여 가능한 모든 경우를 단순하게 탐색합니다.비트 마스크 (Bit Mask): 이진수를 사용하여 문제에서 나올 수 있는 모든 경우의 수를 표현하고 탐색합니다.백트래킹 (Backtracking): 답을 찾는 과정에.. [Algorithm] 5. 이진 탐색(Binary Search) 알고리즘 흔히 for 문을 이용해 배열의 처음부터 끝까지 탐색하는 선형탐색은 O(n) 이라는 시간복잡도로 효율성이 떨어집니다.이를 보완하는 탐색 알고리즘으로 대체되는 이분탐색 (Binary Search, 이진 탐색이라고도 합니다 )은 O(log N) 의시간 복잡도를 가지고 있습니다. 주어진 범위의 절반씩 삭제하며 윈도우를 조절하며 찾아가는 기법으로주어진 배열은 순서대로 정렬이 되있어야 사용할 수 있는 알고리즘입니다. 32를 찾는 순서는 아래와 같이 절반의 범위를 줄여가며 진행됩니다 /** * 정렬된 배열에서 특정 요소의 인덱스를 찾는 이진 탐색 함수 * @param {Array} arr - 검색할 정렬된 배열 * @param {*} elem - 찾고자 하는 요소 * @returns {number} - 요소.. [Algorithm] 알고리즘 기본 패턴 2 - Multiple Pointers (다중 포인터) 1. 개념 배열이나 문자열에서 한 쌍의 값이나 조건을 찾을 때 사용인덱스 또는 위치에 해당하는 포인터 또는 값을 생성하고 특정 조건에 따라 시작, 끝 또는 중간으로 이동합니다.공간의 복잡성을 최소화하면서 문제를 해결하는 데 매우 효율적입니다.정렬된 배열에서 사용합니다 2. 특징시간 복잡도: 대부분 O(n) 공간 복잡도: O(1) (추가 공간이 거의 필요 없음) 주로 정렬된 배열에서 사용됨 두 개의 값을 비교하거나 특정 조건을 찾을 때 효과적3. 사용하는 경우중복 값 찾기 특정 합을 가진 쌍 찾기 팰린드롬 확인 배열에서 고유한 값 개수 세기 4. 예제 1) 정렬된 배열에서 합이 0인 쌍 찾기/** * 배열에서 합이 0이 되는 두 숫자를 찾는 함수 * @param {number[]} arr - 정렬된 숫자.. 두 수의 최대 공약수, 최소 공배수 구하기 (유클리드 호제법, 자바스크립트) 코테 준비를 하다보면 두 수의 최대 공약수를 구해야 하는 경우가 보인다. a = 100, b = 30 두수가 있을 때, a = b * x + y 에서 기존 b 에 a 를 넣고 b 자리에는 y를 넣어 반복 하고y가 0일 때의 b값이 최대 공약수가 된다 100 = 30 * 3 + 10 => a 에 30 b 에 나머지 10치환30 = 10 * 3 + 0 => 나머지 0 이므로 10이 최대공약수 가 된다. 코드화하면const GCD = (a, b) => { if (b === 0) return a; return GCD(b, a % b); };위 처럼 재귀함수화 하여 파라미터의 a 자리에 b를 대입하고, b 자리에는 나머지를 넣어주면 된다. 그럼 최소공배수를 구하는 법은? 두 수 a와 b의 .. 이전 1 다음
