🐤 개발하는 참새 🌞

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

6. 정렬 (Sorting) Codility Lesson 한국어 정리본 (JavaScript ver.) 정렬(Sorting)이란?정렬이란 데이터를 특정한 순서대로 배치하는 과정이다. 일반적으로 숫자 또는 문자열을 값에 따라 정렬한다. 예를 들어, 학생을 키 순서대로 정렬하거나, 도시를 인구수 기준으로 정렬할 수 있다.다음과 같은 배열이 있다고 가정하자.A = [5, 2, 8, 14, 1, 16];이를 숫자 크기 순서로 정렬하면 다음과 같다.A = [1, 2, 5, 8, 14, 16];정렬 알고리즘은 시간 복잡도와 메모리 사용량에 따라 차이가 있다. 여기서는 대표적인 정렬 알고리즘을 살펴본다.1. 선택 정렬 (Selection Sort)아이디어: 배열에서 가장 작은 원소를 찾아 첫 번째 위치와 교환하는 작업을 반복한다.JavaScript 코드:function selectionSort(A) { let n..

5. 누적 합 (Prefix Sums) Codility Lesson 한국어 정리본 (JavaScript ver.) 누적 합(Prefix Sums)이란?배열의 특정 구간(슬라이스)의 합을 빠르게 계산하는 강력한 기법이 누적 합(Prefix Sums) 이다. 이는 배열의 처음부터 특정 위치까지의 합을 미리 계산해 저장하는 방법이다.예를 들어, 배열 A가 다음과 같다고 하자.A = [a₀, a₁, a₂, ..., aₙ₋₁]그러면 누적 합 배열 P는 다음과 같이 정의된다.P[0] = 0P[1] = a₀P[2] = a₀ + a₁P[3] = a₀ + a₁ + a₂...P[n] = a₀ + a₁ + ... + aₙ₋₁이전 값 P[k-1]에 현재 값 A[k-1]을 더하는 방식으로 누적 합을 계산할 수 있으며, 전체 연산은 O(n) 의 시간 복잡도를 가진다.1. O(n) 시간 복잡도의 누적 합 계산JavaScript 코드:funct..

4. 원소 개수 세기 (Counting Elements) Codility Lesson 한국어 정리본 (JavaScript ver.) 원소 개수 세기란?배열을 활용하여 숫자 시퀀스를 저장하는 방법에는 여러 가지가 있다. 일반적으로 연속된 숫자 a₀, a₁, ..., aₙ₋₁를 배열의 인덱스에 맞춰 저장한다.예를 들어:let A = [4, 2, 4, 5];// A[0] = 4, A[1] = 2, A[2] = 4, A[3] = 5그러나 원소를 직접 저장하는 대신, 각 숫자의 등장 횟수를 세는 배열 을 만들 수도 있다.이 경우, 배열 count[] 는 해당 값이 등장한 횟수를 저장한다.count[2] = 1; // 숫자 2는 한 번 등장count[4] = 2; // 숫자 4는 두 번 등장count[5] = 1; // 숫자 5는 한 번 등장이 방법을 사용하면 특정 숫자가 등장한 횟수를 O(1) 시간에 확인할 수 있다.1. O(n + m) 시간..

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

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

티스토리툴바