알고리즘 & 문제풀이/알고리즘

유클리드 알고리즘 이란? 2개의 정수 또는 두 다항식의 최대공약수를 구하는 방법이다. 알고리즘은 "A > B 일때 A와 B의 최대공약수는 B와 나머지 R의 최대공약수와 같다." 큰 수(A)를 작은 수(B)로 나눈다. ( A > B ) 나눈 수(B)를 A로 대입 나머지(R)을 B로 대입하여 계속 나눠준다. ( A(B) % B(R) = (R)) 나머지가 0이 된다면 이전에 B에 대입한 R이 최대공약수이다. 예시 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21 42는 21로 나누어 떨어진다. 반목문 const gcd =(a,b){ let tmp; while..

Greedy Algorithm 이란? 말 그대로 탐욕스러운, 욕심 많은 이라는 뜻이다. 매번 선택을 할 때마다 항상 최선의 방법을 선택한다. 그리디는 매 선택(지역적)으로는 최선을 택하지만 그 선택들이 최종(전역적)으로 봤을 때 최선이라는 보장은 없다. 매순간 최적을 따라가면 ex) 1-1-1-100 보다는 1-1-10-10이 전체적으로 봤을때는 더 짧은 길 이기 때문. 그리디 알고리즘 속성 그리디 알고리즘이 성립하려면 두가지의 조건이 필요하다. 탐욕 선택 속성 (Greedy Choice Property) : 이전의 선택이 다음 선택에 영향을 주지 않는다. 최적 부분 구조 (optimal substructure) : 매 선택의 순간의 최선이 전역적에 대한 최선이어야 한다. 이해를 위한 예시 및 문제 마시..

에라토스테네스의 체 에라토스테네스의 체는 소수 찾기 알고리즘이다. "소수"란 1과 자신 이외에 자연수로는 나눌 수 없는 자연수이다. ( 2, 5, 7 등) 1~100까지의 숫자를 나열. 소수가 아닌 1을 제거. 2를 제외한 2의 배수를 제거. 3을 제외한 3의 배수를 제거. 4의 배수는 2의 배수로 이미 지워졌으므로 5를 제외한 5의 배수를 제거한다. 6또한 3의 배수로 지워졌으므로 7을 제외한 7의 배수를 제거. 11 부터는 11^2 > 100 이기에 지울 필요가 없다. 이런 알고리즘으로 주어진 n이하의 소수를 찾고 싶을 때 사용할 수 있다. 자바스크립트로 구현 function solution(n) { //n + 1 개의 요소를 가진 배열 생성 모두 true로 변경 후 소수제외값 0,1 을 false..

시간 복잡도를 고려한 풀이? 🤔 코딩 테스트 문제를 처음 풀었을 때 문제를 풀기에 급급했지만 막상 테스트에 통과하고 난 후 이 코드가 맞나? 이게 효율적인가?라는 생각을 해본 적이 있다면 이미 시간 복잡도에 대해 고민해 본 것이나 다름없다! 시간 복잡도를 고려한다는 건 입력값에 따라 로직이 실행되는 시간이 증가하고 감소하는 시간의 비율을 최소화하여 구성했다는 뜻이다. 시간 복잡도는 3가지의 표기법이 있는데 Big-O(빅-오) -> 최악을 고려 ( 걸리는 시간의 최대를 고려 ) Big-Ω(빅-오메가) -> 최선을 고려 ( 걸리는 시간의 최선을 고려 ) Big-θ(빅-세타) -> 평균을 고려 ( 걸리는 시간의 평균을 고려 ) 시간 복잡도에서 가장 자주 사용되는 표기법은 빅오 표기법으로 최악을 고려해야 한다...