Algorithm/문제풀이 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.. 더보기 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 다음