'분류 전체보기' 카테고리의 글 목록 (2 Page)

15. 캐터필러 방법 (Caterpillar Method) Codility Lesson 한국어 정리본 (JavaScript ver.) 1. 캐터필러 방법이란?캐터필러 방법은 연속된 부분 배열(슬라이스)에서 특정 조건을 만족하는 경우를 찾는 효율적인 방법 이다. 보통 O(n) 시간 복잡도로 최적화할 수 있다.2. O(n) 시간 복잡도의 캐터필러 방법JavaScript 코드:function caterpillarMethod(A, s) { let n = A.length, front = 0, sum = 0; for (let back = 0; back 이 방법을 사용하면 O(n) 시간 복잡도로 특정 조건을 만족하는 부분 배열을 찾을 수 있다.3. 캐터필러 방법의 활용이 알고리즘은 다음과 같은 문제에 적용할 수 있다:연속 부분 배열의 합 찾기 (예: 연속된 숫자의 합이 특정 값 s가 되는 경우 찾기)연속된 원소들의 곱 찾기 (예: 최대 ..

14. 이진 탐색 (Binary Search) Codility Lesson 한국어 정리본 (JavaScript ver.) 1. 이진 탐색(Binary Search)이란?이진 탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘 으로, O(log n) 시간 복잡도를 가진다. 이 알고리즘은 반복적으로 검색 범위를 절반으로 줄이면서 원하는 값을 찾는다.예를 들어, 1부터 16까지의 숫자 중에서 목표 숫자를 찾는다고 가정해 보자. 단순 선형 탐색(linear search)으로는 최악의 경우 16번의 비교가 필요하지만, 이진 탐색을 사용하면 최대 4번의 비교만으로 찾을 수 있다.2. O(log n) 시간 복잡도의 이진 탐색 구현JavaScript 코드:function binarySearch(A, x) { let left = 0, right = A.length - 1; while (left 시간 복잡도: O(log n)..

13. 피보나치 수열 (Fibonacci Numbers) Codility Lesson 한국어 정리본 (JavaScript ver.) 피보나치 수열(Fibonacci Numbers)이란?피보나치 수열은 다음과 같이 정의된다.F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2) (n ≥ 2)예제:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...1. O(2ⁿ) 시간 복잡도의 재귀 방식 (비효율적)JavaScript 코드:function fibonacci(n) { if (n 이 방식은 너무 느려서 n이 커질수록 사용할 수 없다.2. O(n) 시간 복잡도의 동적 프로그래밍 방식JavaScript 코드:function fibonacciDP(n) { let fib = new Array(n + 1).fill(0); fib[1] = 1; for (let i = 2; i 이 방식..

12. 최대공약수 (Greatest Common Divisor, GCD) Codility Lesson 한국어 정리본 (JavaScript ver.) 최대공약수(GCD)란?두 개의 정수 a, b의 최대공약수(GCD)는 두 수를 동시에 나눌 수 있는 가장 큰 정수 를 의미한다.1. O(n) 시간 복잡도의 유클리드 알고리즘 (뺄셈 방식)JavaScript 코드:function gcdSubtraction(a, b) { if (a === b) return a; return a > b ? gcdSubtraction(a - b, b) : gcdSubtraction(a, b - a);}2. O(log n) 시간 복잡도의 유클리드 알고리즘 (나머지 방식)JavaScript 코드:function gcd(a, b) { return a % b === 0 ? b : gcd(b, a % b);}이 방법은 빠르고, 대부분의 프로그래밍 언어에서 기본적으로 제공된..

11. 에라토스테네스의 체 (Sieve of Eratosthenes) Codility Lesson 한국어 정리본 (JavaScript ver.) 에라토스테네스의 체란?에라토스테네스의 체(Sieve of Eratosthenes) 는 주어진 범위 내에서 모든 소수를 빠르게 찾는 알고리즘이다. 이 방법은 소수를 걸러내는 방식으로 동작하며, O(n log log n) 의 시간 복잡도를 가진다.1. O(n log log n) 시간 복잡도의 소수 판별JavaScript 코드:function sieve(n) { let sieve = new Array(n + 1).fill(true); sieve[0] = sieve[1] = false; for (let i = 2; i * i 이 방법을 통해 n 이하의 모든 소수를 찾을 수 있다.2. 소인수 분해 (Factorization)소인수 분해는 정수를 소수의 곱으로 표현하는 과정 이다.JavaSc..

10. 소수와 합성수 (Prime and Composite Numbers) Codility Lesson 한국어 정리본 (JavaScript ver.) 소수(Prime Number)와 합성수(Composite Number)소수(Prime Number) 는 1보다 크고, 자기 자신과 1을 제외한 약수가 없는 수 를 의미한다.합성수(Composite Number) 는 1과 자기 자신 이외에도 다른 약수를 가지는 수 를 의미한다.예를 들어, 2, 3, 5, 7, 11, 13 등은 소수이며, 4, 6, 8, 9, 10 등은 합성수이다.1. O(√n) 시간 복잡도의 약수 개수 구하기n의 약수를 찾는 기본적인 방법은 1부터 n까지 모든 수를 확인하는 것 이다. 하지만 n의 약수는 대칭성을 가지므로, √n 까지만 탐색해도 전체 약수를 구할 수 있다.JavaScript 코드:function countDivisors(n) { let count = 0; let..

9. 최대 슬라이스 문제 (Maximum Slice Problem) Codility Lesson 한국어 정리본 (JavaScript ver.) 최대 슬라이스 문제란?주어진 정수 배열 A = [a₀, a₁, ..., aₙ₋₁] 에서 연속된 부분 배열(슬라이스, Slice) 중 합이 최대가 되는 구간을 찾는 문제 이다. 즉, 두 인덱스 p, q (p ≤ q)를 선택하여 A[p] + A[p+1] + ... + A[q] 값이 최대가 되는 경우 를 찾는다.예를 들어, 다음과 같은 배열이 있을 때:A = [5, -7, 3, 5, -2, 4, -1];위 배열에서 최대 합을 갖는 부분 배열은 [3, 5, -2, 4]이며, 합은 10이다.1. O(n³) 시간 복잡도의 비효율적인 방법모든 가능한 슬라이스를 탐색하여 최댓값을 찾는 방법이다.JavaScript 코드:function slowMaxSlice(A) { let n = A.length; let r..

8. 리더 (Leader) Codility Lesson 한국어 정리본 (JavaScript ver.) 리더(Leader)란?주어진 수열 A = [a₀, a₁, ..., aₙ₋₁] 에서 리더(Leader) 는 수열의 원소 중 절반을 초과하여 등장하는 원소 를 의미한다.예를 들어, 다음과 같은 수열이 있을 때:A = [6, 8, 4, 6, 8, 6, 6];위 수열에서 6은 4번 등장하여 n/2 = 3.5 보다 많이 등장하므로 리더가 된다. 리더는 최대 하나만 존재 한다.1. O(n²) 시간 복잡도의 단순한 방법각 원소의 등장 횟수를 세어 리더를 찾는 방법이다.JavaScript 코드:function slowLeader(A) { let n = A.length; let leader = -1; for (let k = 0; k Math.floor(n / 2)) { lea..

7. 스택과 큐 (Stacks and Queues) Codility Lesson 한국어 정리본 (JavaScript ver.) 스택(Stack)과 큐(Queue)란?스택과 큐는 데이터를 저장하고 관리하는 대표적인 자료구조이다. 이들은 push(삽입) 및 pop(삭제) 연산을 제공하지만, 데이터의 입출력 방식이 다르다.1. 스택(Stack)스택은 LIFO(Last In, First Out) 구조를 가지며, 가장 최근에 추가된 요소가 가장 먼저 제거된다. 마치 접시를 쌓아올리고 위에서부터 하나씩 제거하는 방식과 유사하다.JavaScript 코드:class Stack { constructor() { this.stack = []; } push(x) { this.stack.push(x); } pop() { if (this.isEmpty()) throw new ..

이전 1 2 3 4 5 ··· 10 다음

라이브러리 브랜드 그룹 | 🐤 개발하는 참새 🌞

티스토리툴바