티스토리 뷰
728x90
문제
https://programmers.co.kr/learn/courses/30/lessons/12953
자연수 array 입력받으면 array 수들의 최소 공배수 return
접근 방법
유클리드 알고리즘을 사용하면 두 수의 최소공배수를 빠르게 구할 수 있다.
> 유클리드 알고리즘
두 수 a, b가 있으면
최소 공배수는 a*b / 최대 공약수 인데,
최대 공약수 구하는 방법은
r = a&b 에서 나눈 나머지를 r이라고 하면
if r == 0 {b는 최대 공약수}
else {
b = a
a = r
// 로 해서 다시 반복
}
하다 보면 최대 공약수가 구해진다.
위 과정은 소인수 분해를 하는 과정을 사용한 것이다. 최대 공약수를 구했으면 이 값을 이용해 최소 공배수를 구할 수 있다.
최소공배수 = a*b/최대공약수
하지만 위 문제는 두 수를 비교하는 문제가 아니라 여러 수를 비교하는 문제이기 때문에 까다롭다.
해결
이는 stack을 이용하면 풀 수 있다.
arr안의 갯수가 2 이상일 경우, 두 수를 pop 해서 최소공배수를 구해준 뒤 push 해주는 식으로 반복해주면 된다.
코드
728x90
'개발 블로그 > 알고리즘' 카테고리의 다른 글
[Swift] 프로그래머스 - 짝지어 제거하기 (0) | 2020.10.21 |
---|---|
[Swift] 프로그래머스 - 수식 최대화 (0) | 2020.10.21 |
[Swift] 프로그래머스 - N-Queen (0) | 2020.10.09 |
[Swift] 백준 - N-Queen (0) | 2020.10.05 |
[Swift] 백준 - 종이의 개수 (0) | 2020.10.03 |
댓글
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Stack
- 자기PR
- today extension
- 괄호연산
- presentStyle
- 1차 뉴스 클러스터링
- RxDataSource
- 위젯
- ios
- 프로그래머스 캐시
- 백준 1946
- 알고리즘
- 아키택처
- 카카오블라인드2018
- ReactorKit
- Level 3
- VIPER 패턴
- 백준 신입사원
- TransitionStyle
- BaseViewController
- UIModalPresentationStyle
- 카카오 블라인드2018
- Github Search
- RxSwift
- BaseTableViewController
- 프로그래머스 추석트래픽
- 프로그래머스 오픈채팅방
- Swift
- 카카오 블라인드 2018
- Widget
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함