본문 바로가기
반응형

Algorithm73

[알고리즘] 유클리드 호제법(Uclidean algorithm) by javascript - 최대공약수 / 최소공배수 구하기 알고리즘 최대 공약수를 구하는 알고리즘인 유클리드 호제법에 대해 알아보자. 그리고 추가적으로 최소공배수까지 구하는 방법 역시 알아보자. 1. 최대공약수 구하기 우선 최대공약수란 두 수의 공통인 약수(공약수) 중에서 가장 큰 수를 최대공약수라고 부른다. 유클리드 호제법의 원리를 다음과 같이 설명한다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a> b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 무슨 소리인지 모르겠지만 일단 원리를 따라가보면 두 수(a, b)가 주어지고 이 둘을 나눈 나머지를 구하라는 의미 같다. 예를 들어 1071 과 1029 주어 졌다면 다음과 같은 원리를 따른다. (1071은 1029로 나누어 떨어지지 않기 때문에 둘을 나눈 나머지를 .. 2022. 4. 20.
[Codility] MinPerimeterRectangle (Easy) by javascript - AVAILABLE LESSONS 10 ▷ 문제 : AVAILABLE LESSONS 10 - MinPerimeterRectangle (Easy) MinPerimeterRectangle coding task - Learn to Code - Codility Find the minimal perimeter of any rectangle whose area equals N. app.codility.com ▷ 해결 날짜 : 2022.04.20 ▷ 소요 시간 : 10분 ▷ 풀이 과정 : 면적이 매개변수로 주어지면 면적이 N인 직사각형의 최소 둘레를 찾는 문제이다. 예제를 보면 직사각형의 각 변은 약수의 집합으로 볼 수 있어서 이전 문제와 동일하되 수정만 조금 해주면 된다. ▷ 구현 function solution(N) { return getDivisor.. 2022. 4. 20.
[Codility] CountFactors (Easy) by javascript - AVAILABLE LESSONS 10 ▷ 문제 : AVAILABLE LESSONS 10 - CountFactors (Easy) CountFactors coding task - Learn to Code - Codility Count factors of given number n. app.codility.com ▷ 해결 날짜 : 2022.04.20 ▷ 소요 시간 : 10분 ▷ 풀이 과정 : 그냥 단순하게 주어진 값의 약수를 구하는 문제로 보였다. 게시글 카테고리 중에 약수 알고리즘 게시글이 있는데 그것만 알면 손쉽게 해결할 수 있는 문제이다. ▷ 구현 function solution(N) { return getDivisors(N); } const getDivisors = (num) => { let count = 0; for(let i = 1 ; i 2022. 4. 20.
[Codility] MaxSliceSum (Easy) by javascript - AVAILABLE LESSONS 9 ▷ 문제 : AVAILABLE LESSONS 9 - MaxSliceSum (Easy) MaxProfit coding task - Learn to Code - Codility Given a log of stock prices compute the maximum possible earning. app.codility.com ▷ 해결 날짜 : 2022.04.20 ▷ 소요 시간 : 20분 ▷ 풀이 과정 : 같은 카테고리에 묶여있어서 그런지 이전 문제와 동일하게 풀 수 있다. ▷ 구현 function solution(A) { let [sum, max] = [A[0], A[0]]; for(let i = 1 ; i < A.length; i++) { sum = Math.max(A[i], sum + A[i]); max .. 2022. 4. 20.
[Codility] MaxProfit (Easy) by javascript - AVAILABLE LESSONS 9 ▷ 문제 : AVAILABLE LESSONS 9 - MaxProfit (Easy) MaxProfit coding task - Learn to Code - Codility Given a log of stock prices compute the maximum possible earning. app.codility.com ▷ 해결 날짜 : 2022.04.20 ▷ 소요 시간 : 40분 ▷ 풀이 과정 : 처음에는 이중 반복문을 사용하려다가 무조건 효율성에서 걸릴 거 같아서 좀 더 고민을 해보았다. 그래서 내가 이전에 풀었던 문제 Lesson 8 EquiLeader 문제에서 leader와 max값을 구한 것처럼 특정 값을 저장해 놓고 계속 비교 후 교체해가면서 문제를 풀면 좋을 것 같아 그렇게 방향을 잡고 구현을 .. 2022. 4. 20.
[Codility] EquiLeader (Easy) by javascript - AVAILABLE LESSONS 8 ▷ 문제 : AVAILABLE LESSONS 8 - EquiLeader (Easy) EquiLeader coding task - Learn to Code - Codility Find the index S such that the leaders of the sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N - 1] are the same. app.codility.com ▷ 해결 날짜 : 2022.04.20 ▷ 소요 시간 : 1시간 30분 ▷ 풀이 과정 : 자꾸 효율성 부분에서 0점이 나와 시간이 걸렸다. 이 문제는 Lesson 8 Leader 문제답게 리더로 두 그룹을 나누고 그 리더가 같은지 확인하는 것이다. 우선 첫 번째로 리더를 먼저 .. 2022. 4. 20.
[Codility] Dominator (Easy) by javascript - AVAILABLE LESSONS 8 ▷ 문제 : AVAILABLE LESSONS 8 - Dominator (Easy) 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 ▷ 해결 날짜 : 2022.04.20 ▷ 소요 시간 : 15분 ▷ 풀이 과정 : 중복되는 숫자의 개수가 배열 길이의 절반보다 큰 경우를 해당 숫자의 인덱스 번호를 출력하는 문제다. map을 사용해 개수를 세주고 그다음에 조건에 맞는 인덱스를 바로 출력해주는 로직을 짜서 풀었다. ▷ 구현 function solution(A) { if(!A... 2022. 4. 20.
[Codility] Nesting (Easy) by javascript - AVAILABLE LESSONS 7 ▷ 문제 : AVAILABLE LESSONS 7 - Nesting (Easy) Nesting coding task - Learn to Code - Codility Determine whether a given string of parentheses (single type) is properly nested. app.codility.com ▷ 해결 날짜 : 2022.04.20 ▷ 소요 시간 : 15분 ▷ 풀이 과정 : 이 문제 역시 괄호의 짝을 맞추는건데,앞에서 풀었던 Brackets 문제와 비슷해서 좀 난이도가 쉬운 문제였다. ▷ 구현 function solution(S){ const opened = []; for(let nest of S){ if(nest == '(') opened.push(nest);.. 2022. 4. 20.
[Codility] Fish (Easy) by javascript - AVAILABLE LESSONS 7 ▷ 문제 : AVAILABLE LESSONS 7 - Fish (Easy) Fish coding task - Learn to Code - Codility N voracious fish are moving along a river. Calculate how many fish are alive. app.codility.com ▷ 해결 날짜 : 2022.04.20 ▷ 소요 시간 : 40분 ▷ 풀이 과정 : 내려오는 물고기와 올라가는 물고기를 싸움 붙여서 마지막에 살아남은 물고기의 개수를 출력하는 문제이다.덩치큰 물고기가 덩치가 작은 물고기를 잡아먹는 구조이며 속도가 같아 같은 방향의 물고기끼리는 만날수 없다. 처음에는 올라가는 물고기 내려가는 물고기 둘다 나눠서 배열에 담아주려다가굳이 올라가는 물고기는 필요없을.. 2022. 4. 20.
반응형
TOP

티스토리툴바