Algorithm 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이란 무엇인가를 설명하고자 한다. 우선, 다이나믹 프로그래밍에 대해서 집고 넘어갈 필요가 있다. 다이나믹 프로그래밍이란?.. 더보기 Codility Lesson9 - MaxProfit 🔍 문제 주어진 배열 A의 원소가 한 주식의 가격이라고 생각하고, 배열 A의 index는 날짜라고 생각한다. 따라서 주식의 가격(배열 값)은 날짜(index)에 따라 가격이 변화하는데, 이 중 주식을 사고 팔았을 때 가장 큰 이익을 계산해서 return 하면 되는 문제이다. 만약 이익을 낼 수 있는 경우가 전혀 없고 손해만 난다면 return 0을 해주면 된다. MaxProfit coding task - Learn to Code - Codility Given a log of stock prices compute the maximum possible earning. app.codility.com ✏️ 풀이 - JS 이 문제를 brutal force로 푸는 방법 밖에 생각나지 않아, 검색해보다가 Kadane.. 더보기 Codility Lesson8 - Dominator 🔍 문제 주어진 배열 A에서 과반수 이상으로 같은 값을 가진 인덱스들을 찾아서 아무 인덱스나 return 해주면 되는 문제이다. Dominator coding task - Learn to Code - Codility Find an index of an array such that its value occurs at more than half of indices in the array. app.codility.com ✏️ 풀이 - JS 처음에 문제를 잘못 읽고 과반수 이상으로 같은 값을 가진 인덱스들을 모두 배열로 반환하는 건 줄 알았다가 오류떠서 다시 읽어보니 index중 아무 값이나 반환하면 되는 문제였다. Map을 이용해서 풀었으며, 시간 복잡도는 O(N*log(N)) or O(N)가 나왔다. fun.. 더보기 Codility Lesson7 - Nesting 🔍 문제 이전에 풀었던 Lesson7의 Brackets와 매우 비슷한 문제인데 더 쉬운 문제이다. (, ) 로 이루어진 문자열 S의 괄호 짝이 맞는지 확인해서 맞으면 return 1 틀리면 return 0을 하면 된다. Nesting coding task - Learn to Code - Codility Determine whether a given string of parentheses (single type) is properly nested. app.codility.com ✏️ 풀이 - JS 이 문제도 역시 stack을 이용해서 풀었다. 여는 괄호가 나오면 open이라는 배열에 넣어주고, 닫는 괄호가 나오면 open.pop()을 해서 여는 괄호가 있는지 확인해주면 된다. 처음에는 주어진 문자열 S를 .. 더보기 Codility Lesson7 - Fish 🔍 문제 Fish coding task - Learn to Code - Codility N voracious fish are moving along a river. Calculate how many fish are alive. app.codility.com 강 한 줄기가 있다고 했을 때, 물고기들의 사이즈가 담긴 A 배열과 물고기들이 향하는 방향을 알려주는 배열 B가 주어진다. 만약, 위로 향하는 물고기와 아래로 향하는 물고기가 만나게 되면, 사이즈가 더 작은 물고기는 더 큰 물고기에게 잡아먹히게 된다. 이렇게 해서 최종 살아남게 되는 물고기 수를 구하면 된다. ✏️ 풀이 - JS 물고기가 만나게 되는 경우는 오직 아래로 향하는 물고기 + 위로 향하는 물고기의 조합 밖에 없다. 따라서 B배열의 값이 (1.. 더보기 이전 1 2 3 4 5 6 다음