전체 탐색 - 조합 전체 탐색 (비트 연산 이용)

N개의 양의 정수가 있고 정수를 몇개 골라 그 합을 W로 만들 수 있는지 궁금하다면 비트 연산을 통해 구할 수 있다.N = 3, -> [1,2,3] , W = 5 일 때배열에서 만들 수 있는 조합은 2**3으로 총 8개 이다.2진법으로 표현하면 000, 001, 010, 011, 100, 101, 110, 111이다.0은 배열에서 고르지 않은것, 1은 배열에서 골라서 더한것에를들면 011은 [2,3]을 의미한다.for(let bit = 0; bit

• format_list_bulleted 코테 준비/알고리즘
• · 2024. 8. 5.
• textsms

숫자의 표현 문제

자연수 n을 연속한 자연수들로 표현 하는 방법1 + 2 + 3 + 4 + 5 = 154 + 5 + 6 = 157 + 8 = 1515 = 15자연수 n의 홀수 약수의 개수와 같다.15의 약수 = 1,3,5,1519의 약수 = 1,199+10 = 1919 = 19

• format_list_bulleted 코테 준비/알고리즘
• · 2024. 8. 5.
• textsms

약수 구하기

약수를 구하는법1부터 구하는 수까지 전부 나머지를 구해보는 방식시간복잡도 : O(N)let num = 10;let sum = 0;for(let i = 1; inum/2이상의 수는 약수에서 나오지 않기때문에 사용할 수 있는 방식시간복잡도 : O(N)let num = 10;let sum = 0;for(let i = 1; i🔆시간복잡도 : O(sqrt(N))let num = 100;let sum = 0;for( let i = 1; i*i i*i === num 이라는 뜻은 제곱수라는 뜻. 따라서 10*10 = 100일때 약수는 10 한개만 포함된다.i = 1일 때 100/1 = 100으로 100이 대응된다.i = 2일 때 100/2 = 50으로 50이 대응된다.따라서 num%i === 0일때의 약수는 2개씩을..

• format_list_bulleted 코테 준비/알고리즘
• · 2024. 8. 5.
• textsms

나머지 연산의 특징

프로그래머스 Lv.2 피보나치 수를 풀때 필요했던 개념입니다.(a+b) % c = (a%c + b%c) % c예를 들면(2+1)% 3 = (2%3 + 1%3) %3 = 0

• format_list_bulleted 코테 준비/알고리즘
• · 2024. 8. 5.
• textsms

뉴턴-랩슨 방법 (sqrt를 쓰지 않고 제곱근을 구하는 법)

뉴턴-랩슨 방법은위의 사진과 같이 한 임의의 점에서 접선을 구하고 그 접선의 절편들을 관찰하면 점점 구하려는 값과 근사합니다.우리는 제곱근을 구하고싶은것인데f(x) = x^2-11을 한다면 x는 sqrt(11)일 것이다.따라서, f(x) = x^2 -k를 한다면 x = sqrt(k)이므로 k의 제곱근을 구할 수 있게된다.이 f(x)를 뉴턴-랩슨 방법에 적용시킨다면Xn+1=Xn-(Xn^2-k)/2Xn=0.5(Xn+k/Xn)로 정리 된다.

• format_list_bulleted 코테 준비/알고리즘
• · 2024. 8. 5.
• textsms

시간복잡도

복잡도-> 만들어낸 알고리즘을 직접 구현해보지 않아도 대략적인 시간을 미리 파악할 수 있다.즉, 어떤 알고즘을 사용할지 검토할 때 비교하기 편하다.알고리즘 A의 계산시간 T(N)이 대략 P(N)에 비례하면T(N) = O(P(N)) 으로알고리즘 A의 복잡도는 O(P(N))이라 한다.ex) T(N) = 3N^2+5N+100일때 T(N) = O(T(N^2))복잡도 종류지수시간 - N이 증가함에 따라 계산시간이 급격하게 늘어남.O(N!), O(2^n)다항시간O(N^d),O(N^2),O(N^3) & 다항식은 아니지만 다항 시간이 필요한 계산량 O(NlogN),O(N*sqrt(N))상수시간 - 문제 크기에 의존하지 않는 상수시간 이내에 처리가 끝남O(1)복잡하지만 빠른 알고리즘만 추구하면 안된다.풀고싶은 문제의 크..

• format_list_bulleted 코테 준비/알고리즘
• · 2024. 8. 5.
• textsms