알고리즘

두 수를 A와 B라고 하자. 최대공약수 x 최소공배수 = A x B 즉, 최소공배수는 두 수를 곱한 후 최대공약수로 나눈 수 이다. 이를 구할 때는 주로 유클리드 호제법을 이용한다. 간단하니 한 번 외워두면 편하다. A, B에 대해서 A를 B로 나눈 나머지를 r이라고

📍 어떤 조건을 만족하는 위치 중 가장 큰 or 작은 위치는? 💡 이분 탐색 > 정렬된 배열에서 target의 존재 여부와 위치를 알려준다. 재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다. 💡 매개 변수 탐색 > 이분 탐색과

매개 변수 탐색의 일종으로, 이분 탐색과 비슷하다. 차이점은, 📌 이분 탐색 : 단조 증가/감소하는 경우에만 사용 가능📌 삼분 탐색 : 아래/위로 볼록한 경우(넓은 범위)에도 사용 가능 단, 볼록이 여러 번 반복되는 경우는 삼분 탐색이 불가능하다. (한쪽은 단조 증

가장 기본적으로 N을 2부터 N-1 까지 나누어 보고, 나누어떨어지지 않으면 소수로 판정한다. 유의할 점은 1은 소수가 아니라는 것이고 예외 처리한다. 시간복잡도 : O(logN)기본적인 방법과 유사하다. N을 제곱근까지만 나눈다. 시간복잡도 : O(log(√N)N =

✅ 0은 2와 5의 곱으로 만들어진다. 처음 백준 1676번: 팩토리얼 0의 개수을 풀 때는 팩토리얼 함수를 구현해서 연산을 하고, 문자열로 바꾼 후 뒤에서 부터 문자를 세려고 했다. 하지만 결과는 실패. 500!의 경우 숫자가 매우 크다. 검색을 해보니 팩토리얼