본문 바로가기
728x90
반응형

Algorithm17

[유클리드 호제법 알고리즘] 최대공약수, 최소공배수 구하기 유클리드 호제법 1. 최대공약수 최대공약수를 구하는 가장 쉬운 알고리즘, 유클리드 호제법 두 수 A와 B가 주어졌다고 생각해보자. (A>B) A와 B의 최대 공약수는 n이라고 하자. 그러면 A=n*?, B=n*?? 이런 구조일 것이다. 결국 A-B, B-(A-B), (A-B)-(B-(A-B)) ,,,,,,,, 이런 식으로 계속 빼다보면 언젠가 최소 단위인 n이 나올 것이다. 이 그림을 보면 이해가 될 것이다. A에서 B를 빼고, 다시 B에서 그 A-B를 빼고 이런 과정을 반복하다 보면 언젠가 n이 나오고 맨 마지막엔 0이 나올 것이다. 둘 다 n이 남았으니 말이다. 여기서 아이디어를 추가해보자. 계속 빼는 것도 좋지만, A와 B의 차이가 크면 너무 무의미한 계산의 반복이다. 결국 A%B, A를 B로 나눈.. 2022. 1. 14.
소수(Prime Number)인지 아닌지 확인하는 코드 JAVA로 구현하기 소수 소수는 1과 자기 자신만을 약수로 가지는 자연수를 의미한다. 사실 생각해보면 아주 간단하다. 하지만 이걸 막상 코드로 작성하려고하면 한 번 고민을 해봐야 한다. N이라는 숫자가 소수인지 아닌지를 return하는 함수를 만든다고 가정해보자. (1) 2 ~ N-1 을 싹 다 넣어서 약수인지 아닌지 확인하면 된다. 참고로 약수인지는 나눠서 나머지가 0이면 약수인 것이다. 하지만 이 과정은 너무 계산이 길다. Big O 로 적으면 O(n) 이를 조금 줄여보자. 가장 쉽게 생각할 수 있는 방법은 절반을 나누는 방법이다. 하지만 한 번만 더 생각해도 정말 바보같은 생각임을 알 수 있다. 약수라는 것은 곱으로 이루어져있기에 말이다. 곱으로 이루어져있다는 아이디어를 활용하면 아주 간단해진다. 만약 N의 약수가 있.. 2022. 1. 13.
JAVA로 순열(Permuation) 구현하기 우리가 등학교 때 배웠던 '순열 & 조합' 기억할 것이다. (아마 '확률과 통계' 과목에 나왔던 것으로 기억하는데, 예전 문과는 '미적분과 통계 기본'이라는 과목으로 배웠을 것이다.) nPr 이 모양을 보면 기억이 날 것이다. nPr은 'n개 중 r개를 중복을 허용하지 않으면서 뽑는 모든 순서의 수'이다. 계산은 사실 간단하다. nPr = n!/(n-r)! 이 공식으로 교과서에 나와있던 걸 어렴풋이라도 기억할 것이다. 이걸 코딩으로 구현한다고 생각해보자. 그저 nPr 값만 구현한다고 하면 int numOfPer(int n, int r){ return factorial(n)/factorial(n-r); } int factorial(int n){ if(n==1) return 1; return n*factor.. 2022. 1. 13.
[프로그래머스] 코딩테스트 > 연습스택/큐 > 기능개발 문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자.. 2021. 12. 20.
728x90
반응형

티스토리툴바