https://school.programmers.co.kr/learn/courses/30/lessons/12940
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
- 두 수는 1이상 1000000이하의 자연수입니다.
발상
주어진 두 수의 최대공약수와 최소공배수를 구하는 문제이다.
최대공약수는 유클리드 호제법이라는 널리 알려진 알고리즘이 존재하고, 최소공배수는 최대공약수를 이용하여 간단하게 구할 수 있다.
알고리즘 공부를 하다 보면 자주 볼 수 있는 문제이기 때문에 유클리드 호제법은 기억해 두는 것이 좋을 것 같다.
간단요약
public int gcd(int p, int q){
//0으로 나눌 수 없음
if(q==0) return 0;
//재귀호출
return gcd(q, p%q);
}추가적인 설명과 이미지를 통한 이해는 위키피디아를 활용하면 좋을 것 같다.
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95
유클리드 호제법 - 위키백과, 우리 모두의 백과사전
ko.wikipedia.org
의사코드
1. 최대공약수 알고리즘 구현
2. 최소공배수 알고리즘 구현
3. 인자를 사용하여 gcd, lcm 호출 후 결과배열 생성
4. 반환
개선
실무 개발할 때는 가독성이 더 중요하지만, 코딩테스트나 알고리즘 준비에서는 가독성이 조금 떨어지더라도 시간복잡도나 공간복잡도를 개선한 코드가 높은 점수를 받는다.
수학적인 테크닉들도 계속 숙달하도록 하자.
'IT > Algorithm' 카테고리의 다른 글
| [programmers] 이상한 문자 만들기 (0) | 2022.07.13 |
|---|---|
| [programmers] 예산 (0) | 2022.07.12 |
| [programmers] 3진법 뒤집기 (0) | 2022.07.10 |
| [programmers] 크레인 인형뽑기 게임 (0) | 2022.07.08 |
| [programmers] 문자열 내 p와 y의 개수 (0) | 2022.07.08 |