17. 동적 프로그래밍 (Dynamic Programming) Codility Lesson 한국어 정리본 (JavaScript ver.) 동적 프로그래밍(Dynamic Programming)이란?동적 프로그래밍(DP)은 작은 문제들의 해를 활용하여 더 큰 문제의 해를 구하는 알고리즘 기법 이다. 일반적으로 문제를 여러 작은 부분 문제로 나누고, 중복 계산을 줄이기 위해 결과를 저장(memoization) 하는 방식으로 사용된다.동적 프로그래밍이 효과적인 경우:최적 부분 구조(Optimal Substructure): 큰 문제의 최적해가 작은 부분 문제의 최적해로 구성될 수 있음중복 부분 문제(Overlapping Subproblems): 동일한 작은 문제를 여러 번 해결해야 하는 경우대표적인 DP 문제:최단 경로 문제 (Floyd-Warshall, Bellman-Ford)배낭 문제 (Knapsack Problem)동전 거스름돈 문제 (Coi..
16. 탐욕적 알고리즘 (Greedy Algorithms) Codility Lesson 한국어 정리본 (JavaScript ver.) 탐욕적 알고리즘(Greedy Algorithm)이란?탐욕적 알고리즘은 각 단계에서 가장 최선의 선택을 하는 방식으로 최적해를 찾는 방법 이다. 전체 최적해를 고려하지 않고, 매 순간 최적의 선택을 하기 때문에 구현이 간단하지만, 항상 최적해를 보장하는 것은 아니다.탐욕적 알고리즘이 적용될 수 있는 대표적인 문제들:동전 거스름돈 문제 (Coin Change Problem)회의실 배정 문제 (Activity Selection Problem)배낭 문제 (Knapsack Problem)작업 스케줄링 문제 (Activity Selection)최소 신장 트리 (MST, Minimum Spanning Tree)허프만 코딩 (Huffman Coding)탐욕 알고리즘의 특징빠른 실행 시간: O(n log n) 또는 O(..
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..

티스토리툴바