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..
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..
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) 시간..