본문 바로가기

Algorithm

Codility Lesson13 - Ladder 🔍 문제 어떤 사다리가 있고, 발을 밟고 올라갈 수 있는 발판이 N개가 주어진다. 이때 발판을 한번에 이동할 수 있는 칸의 수는 1칸 아니면 2칸만 허용된다. 예를들어, 3개의 발판을 가진 사다리를 올라가서 꼭대기에 도달할 수 있는 방법은 [1, 1, 1] or [1, 2] or [2, 1] 로 세가지이며 4개의 발판을 가진 사다리를 올라가서 꼭대기에 도달할 수 있는 방법은 [1, 1, 1, 1] or [1, 1, 2] or [1, 2, 1] or [2, 1, 1] or [2, 2]로 5가지 방법이 존재한다. 따라서 주어진 사다리를 올라갈 수 있는 경우의 수를 return하면되는데, 발판의 수가 커질 수록 그 경우의 수는 기하급수적으로 커지기 때문에 배열 B에 주어진 수를 이용해서 2^B[i]를 한 값으.. 더보기
Codility Lesson12 - CommonPrimeDivisors 🔍 문제 두 배열 A와 B가 주어지고, 같은 index의 두 요소가 최대 공약수와 똑같은 인자를 가지고 있을 경우의 수를 구하는 문제이다. CommonPrimeDivisors coding task - Learn to Code - Codility Check whether two numbers have the same prime divisors. app.codility.com ✏️ 풀이 - JS Lesson의 소제목이 유클리드의 호제법이므로, 최대 공약수는 유클리드의 호제법을 이용해서 구해주었다. 유클리드 호제법 포스트보기 👉 유클리드 호제법(Uclidean algorithm) 먼저, 두 수의 최대 공약수를 구해 준 후, 각 수를 최대 공약수와의 최대 공약수를 다시 구해주면된다. 그리고 나서 각 수를 구한 .. 더보기
Codility Lesson12 - ChocolatesByNumbers 🔍 문제 N개의 초콜릿을 원 형태로 나열한 뒤, 0번째 초콜릿을 먹고 포장지만 남긴다. 그리고나서 현재 먹은 초콜릿 자리 + M의 자리에 있는 초콜릿을 먹는다. 원의 형태로 나열되어 있으므로 초콜릿의 자리는 (i + M)%N의 공식으로 구하면 된다. 이 순서로 초콜릿을 먹어가면서 이미 먹고 포장지만 남은 초콜릿의 자리로 다시 돌아오게된다면 먹는것을 멈춘다. 이 과정을 거쳤을 때 먹게되는 초콜릿의 개수를 구하면 된다. ChocolatesByNumbers coding task - Learn to Code - Codility There are N chocolates in a circle. Count the number of chocolates you will eat. app.codility.com ✏️ 풀이 .. 더보기
유클리드 호제법(Uclidean algorithm) 최대 공약수란? 주어진 정수들의 공통된 약수들 중 가장 큰 약수를 말한다. 최대공약수를 구하는 방법은 소인수 분해와, 유클리드 호제법이있다. 두가지 방법으로 192와 72의 최대 공약수를 구하는 방법을 살펴보자. 소인수 분해 소인수 분해로 구할 때는 먼저 주어진 수들을 각자 소인수 분해한다. 그 후에 중복되는 부분을 서로 곱해주면 최대 공약수를 구할 수 있다. 192 = 2^6 * 3 = 2 * 2 * 2 * 2 * 2 * 2 * 3 72 = 2^3 * 3^2 = 2 * 2 * 2 * 3 * 3 이때, 중복되는 2^3 * 3 = 2 * 2 * 2 * 3 = 24로 두수의 최대 공약수는 24이다. 유클리드 호제법 유클리드 호제법은 두 정수의 최대 공약수를 재귀적으로 구하는 방법이며 소인수 분해보다 훨씬 빠.. 더보기
자료구조 - 스택과 큐(Stack and Queue), 링버퍼(Ring buffer) 스택(Stack) 스택은 데이터를 일시적으로 저장하기 위한 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO, Last In First Out)이다(가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.). 스택에 데이터를 넣는 작업을 푸시(push)라고 하고, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다. 이때, 푸시와 팝을 하는 위치를 꼭대기(top)이라고 하고, 스택의 가장 아랫부분을 바닥(bottom)이라고 한다. 스택의 push와 pop은 꼭대기 top자리에서만 이루어지므로 복잡도는 O(1)이다. 큐(Queue) 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조이다. 스택과 다르게 큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, Fisrt In F.. 더보기
검색 알고리즘 - 선형 검색, 이진 검색 검색 알고리즘이란 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 알고리즘이다. 알고리즘에 들어가기 앞서, 복잡도에 대해 알아보자. 복잡도 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다. 시간 복잡도(time complexity): 실행에 필요한 시간을 평가한 것 공간 복잡도(space complexity): 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것 선형 검색(linear search) 요소가 직선 모양으로 늘어선 배열에서의 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨앞부터 순서대로 요소를 검색하면 되는데, 이것이 선형 검색(linear search) 또는 순차 검색(sequential search)이라는 알고리즘이다. [검색이 종료되는 종료 조건.. 더보기
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.. 더보기

티스토리툴바