'Coding Test/Codility' 카테고리의 글 목록 (2 Page)

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

3. 시간 복잡도 (Time Complexity) Codility Lesson 한국어 정리본 (JavaScript ver.) 시간 복잡도란?시간 복잡도(Time Complexity)를 사용하면 프로그램의 실행 시간을 대략적으로 추정할 수 있다. 정확한 실행 시간을 계산하는 것은 컴파일러, 컴퓨터의 종류, 프로세서 속도 등 여러 요인에 의해 영향을 받기 때문에 매우 복잡하다. 따라서, 우리는 실행 시간의 대략적인 크기(order of magnitude) 를 측정하는 것이 목표이다.복잡도는 프로그램이 실행할 수 있는 기본 연산(primitive operation) 의 최대 개수로 볼 수 있다. 여기서 기본 연산이란 덧셈, 곱셈, 대입 연산 등을 의미한다. 하지만 모든 연산을 다 고려하는 대신, 프로그램에서 가장 많이 실행되는 지배적인 연산(dominant operation) 에 초점을 맞춘다.프로그램의 시간 복잡도는 입력 데이터에..

2. 배열 (Arrays) Codility Lesson 한국어 정리본 (JavaScript ver.) 배열 (Arrays)배열(Array)은 여러 개의 항목을 한 곳에 저장할 수 있는 데이터 구조이다. 예를 들어, 쇼핑 목록을 생각해보자. 각각의 제품을 개별적인 페이지에 기록하지 않고, 한 페이지에 나열하는 것이 더 효율적이다. 배열은 이러한 개념과 유사하다. 마찬가지로, 1년 동안의 일일 기온을 기록하려 한다면, 365개의 변수를 만들기보다는 하나의 배열에 저장하는 것이 더 적절하다.1. 배열 생성 (Creating an Array)우리는 세 개의 제품을 포함하는 쇼핑 목록을 만들고자 한다. 이러한 배열은 다음과 같이 생성할 수 있다.JavaScript 코드:let shopping = ['bread', 'butter', 'cheese'];배열의 각 항목을 요소(element) 라고 한다. 배열은 메모리..

1. 반복 (Iterations) Codility Lesson 한국어 정리본 (JavaScript ver.) Codility 에서 제공하는 lesson의 open material 을 모두 한국어로 정리하는 동시에, 나는 JS 로 코딩테스트를 봐야하기 때문에 튜토리얼 속 파이썬 코드를 JS 코드로 바꿔 정리하게 되었다.100% 완벽한 번역본이 아닌 필자의 입맛대로 (벼락치기용 )ㅎ 정리한 내용이다.lesson 17까지 다 공부하고 문제 풀고 블로그에 포스팅까지 하는게 목표!반복문 (Iterations)프로그래밍에서 반복(iterating) 이란 프로그램의 일부를 여러 번 실행하는 것을 의미한다. 이 장에서는 반복을 수행할 수 있는 기본적인 프로그래밍 구조인 for문과 while문을 다룬다.1.1. For 루프 (For Loops)어떤 연산을 일정 횟수만큼 반복하거나, 특정 컬렉션의 각 요소에 대해 반복하려면 fo..

이전 1 2 다음

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

티스토리툴바