분류 전체보기 Sieve of Eratosthenes(에라토스테네스의 채) 들어가기에 앞서, 중1 때 배웠던 소수와 합성수에 대해서 잠깐 알아보면 더 이해가 잘 될 것이다. 소수와 합성수 1보다 큰 모든 정수는 소수이거나 합성수이다. 소수는 1과 자기 자신으로 밖에 나누어 떨어지지 않는 수이다. (두 개의 약수만 가지고 있다.) 합성수는 1과 자기 자신이 아닌 다른 자연수의 곱으로 나타낼 수 있는 자연수를 의미한다. (두개 이상의 약수를 가지고 있다.) 따라서 1은 소수도 합성수도 아니다. Sieve of Eratosthenes(에라토스테네스의 채) 간단하게 말하면, 1부터 어떤 수 N까지의 범위에서 소수들을 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였으며, 구하는 방법이 마치 채에 거르는 것과 같아 '에라토스테네스의 채'라고 불린다. 알고리즘은 아래의 이미지를.. 더보기 Codility Lesson11 - CountNonDivisible 🔍 문제 어떤 주어진 배열 A의 원소인 A[i]의 약수가 아닌 원소가 해당 배열에 몇개인지 구하는 문제이다. CountNonDivisible coding task - Learn to Code - Codility Calculate the number of elements of an array that are not divisors of each element. app.codility.com ✏️ 풀이 - JS 원소 A[i]의 약수가 아닌 수는 전체 원소의 개수에서 약수인 수를 빼서 구했다. 맨 처음에는 배열안에서 각각의 수가 몇개인지 구해준다. 원소의 개수를 담는 배열의 범위는 idx값이 1부터 N*2까지 담을 수 있도록 만들었다. 왜냐하면 문제의 조건 중에 A[I]의 원소가 될 수 있는 범위는 1부터 N.. 더보기 Codility Lesson11 - CountSemiprimes 🔍 문제 주어진 범위내에서 두 소수의 곱의 값인 semiprime의 개수를 구하는 문제이다. CountSemiprimes coding task - Learn to Code - Codility Count the semiprime numbers in the given range [a..b] app.codility.com ✏️ 풀이 - JS Lesson의 소제목이 Sieve of Eratosthenes(에라토스테네스의 채)이길래 이 이론에 대해서도 정리해보았다. 링크로 가기 👉 Sieve of Eratosthenes(에라토스테네스의 채)에 대해서 알아보자. 로직은 아래와 같으며, 시간 복잡도는 O(N * log(log(N)) + M) 가 나왔다. 1~N 까지의 인덱스를 가진 배열을 만들어준 후, 인덱스를 기준.. 더보기 Codility Lesson10 - Flags 🔍 문제 이전 풀었던 peaks 문제와 비슷한데, 조금 더 꼬아서 낸 것 같다. 먼저 주어진 배열 A에서 peak을 구한다. 각 peak에는 깃발을 꽂을 수 있는데, peak에 깃발을 꽂을 수 있는 조건은 다음과 같다. 1. peak P와 Q사이의 거리(배열 A에서 index)가 챙겨간 깃발의 갯수보다 크거나 같아야 깃발을 꽂을 수 있다. 2. 이 때, 배열 A의 peak에 꽂을 수 있는 가장 큰 깃발의 수를 구하면 된다. Flags coding task - Learn to Code - Codility Find the maximum number of flags that can be set on mountain peaks. app.codility.com ✏️ 풀이 - JS 정확도는 다 맞았는데 perfor.. 더보기 Codility Lesson10 - Peaks 🔍문제 Peaks coding task - Learn to Code - Codility Divide an array into the maximum number of same-sized blocks, each of which should contain an index P such that A[P - 1] A[P + 1]. app.codility.com 어떤 배열을 블럭으로 나눴을 때, 모든 블럭이 peak인 숫자를 가지고 있어야한다. 이 때, 가능한 최대 블럭의 개수를 구하면 된다. ✏️ 풀이 - JS 아래처럼 풀면 보나마나 performance에서 timeout error가 뜰 것 같았지만 한 번 submit해보았다. 정확도 test는 다 맞았지만 시간복잡도 O(N**2)로 역시나 tim.. 더보기 Codility Lesson10 - MinPerimeterRectangle 🔍 문제 어떤 직사각형의 넓이 N이 주어지면, 가능한 둘레 중 가장 작은 둘레를 반환 하는 문제이다. MinPerimeterRectangle coding task - Learn to Code - Codility Find the minimal perimeter of any rectangle whose area equals N. app.codility.com ✏️ 풀이 - JS 직사각형의 넓이 N은 두 변의 곱이다. 따라서 가능한 두 변의 길이는 넓이 N의 약수라고 할 수 있다. 둘레의 공식은 (A + B)*2 이므로 A+B의 값이 제일 작은 약수의 조합을 찾으면 된다. 이전에 풀었던 CounterFactors 문제와 비슷한 방식으로 풀어보았는데, N의 제곱근을 기준으로 N의 제곱근 보다 작은 약수들 중 가.. 더보기 Codility Lesson10 - CountFactors 🔍 문제 CountFactors coding task - Learn to Code - Codility Count factors of given number n. app.codility.com ✏️ 풀이 - JS 첫 번째 풀이는 어렸을 때 수학 시간에 배운 어떤 수의 약수 개수 구하기가 생각나서 그 방식으로 풀어 보았다. N을 소인수 분해한 후, 각 소인수의 지수+1을 해준 후 곱한 수를 반환하였다. 정확도는 100%가 나왔지만 문제는 performance에서 timeout error가 발생하였다. 만약 매우 큰 소수가 N(ex. 780291637)으로 들어올 경우 while문에서 i++를 해가면서 i가 N이 될 때까지 매우 오랜 시간이 걸렸다. 또, 정수 타입 중 가장 큰 값이 N으로 들어오면 시간 초과.. 더보기 Codility Lesson9 - MaxDoubleSliceSum 🔍 문제 MaxDoubleSliceSum coding task - Learn to Code - Codility Find the maximal sum of any double slice. app.codility.com ✏️ 풀이 부분합 구하기 문제를 꼬아서 낸 문제이다. 부분합 구하기 문제는 아래 링크로 가면된다. 👉 Codility Lesson9 - MaxSliceSum 주어진 배열 A를 예를 들면 0번 인덱스와 7번 인덱스는 어떠한 경우에도 포함되지 않는다. 따라서 인덱스 1번과 6번 사이에서 가능한 최대 부분합을 구하면되는데, (X,Y,Z)에서 Y 인덱스 값은 부분합에 포함되지 않아야 한다. 따라서 Y를 기준으로 앞쪽으로 부분합 배열을 하나 만들고, 뒷쪽으로 부분합 배열을 하나 만들어서 두 배열을 합.. 더보기 Codility Lesson9 - MaxSliceSum 🔍 문제 주어진 배열안에서 최대 부분합 구하기 문제이다. MaxSliceSum coding task - Learn to Code - Codility Find a maximum sum of a compact subsequence of array elements. app.codility.com ✏️ 풀이 - JS MaxProfit 문제를 풀 때 카데인 알고리즘을 공부했었기 때문에 바로 풀 수 있었다. 시간복잡도는 O(N)이다. 카데인 알고리즘에 대한 포스트 👉 Dynamic Programming - Kadane’s Algorithm (카데인 알고리즘) function solution(A) { if(A.length === 1) return A[0]; let localMaxSum = A[0]; let globa.. 더보기 Dynamic Programming - Kadane’s Algorithm (카데인 알고리즘) 오늘도 어김없이 Codility의 문제를 풀다가, brutal force로 풀기는 정말 싫은데 도저히 다른 방법이 떠오르지 않아서 검색하다가 발견한 알고리즘에 대해 글을 써보려 한다. 검색을 해보니 Kadane's Algorithm에 대한 설명을 정말 잘 해준 포스트가 있었다. 포스트로 가기 👉 Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work? 유튜브 비디오 보기 👉 https://www.youtube.com/watch?v=86CQq3pKSUw 위의 포스트와 비디오를 기반으로, Kadane's Algorithm이란 무엇인가를 설명하고자 한다. 우선, 다이나믹 프로그래밍에 대해서 집고 넘어갈 필요가 있다. 다이나믹 프로그래밍이란?.. 더보기 이전 1 ··· 8 9 10 11 12 13 다음