본문 바로가기

알고리즘

(5)

[Kotlin] 백준 2609 - 최대공약수와 최소공배수(유클리드 호제법) 문제두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.풀이1. 최대공약수를 구한다. 최대공약수는 큰값을 작은값으로 나누었을 때, 나머지가 나오지 않는 첫 시점의 값이다.2. 유클리드 호제법을 알고있냐는 문제이다.코드import java.util.*fun main() = with(Scanner(System.`in`)) { var n1: Int = nextInt() var n2: Int = nextInt() val m: Int // 최대공약수 // 예외처리 n1 > n2로 변환 if(n2 > n1){ val temp ..

[Kotlin] 백준 2309 - 일곱 난쟁이 문제왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.풀이1. 합이 100이 되는 경우를 찾는다.2. 난쟁이의 7명의 키 총합을 구하..

[Kotlin] 백준 10870 - 피보나치 수 5 문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.풀이1. n번째 자리의 값은 n-1번째, n-2번째 값의 합이다. -> n-1, n-2번째 값을 기억하고 있어야한다. -> 배열 자료구조를 채택해서 값을 저장..

[Kotlin] 배준 3460 - 이진수 문제양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치를 모두 찾는 프로그램을 작성하시오. 최하위 비트(least significant bit, lsb)의 위치는 0이다.첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. (1 ≤ T ≤ 10, 1 ≤ n ≤ 10^6)풀이1. 2진수의 경우, 2로 나눈 나머지가 존재한다면(나머지는 1) 해당 위치 1의 값이 온다.2. 테스트 케이스 당 n의 값을 2로 계속 나눈다면 최대 log(n)번 수행해야한다. O(TlogN)3. T는 최대 10 n의 최댓값은 10^6으로 이므로 최대 log(10^7)의 시간복잡도를 가지므로 2로 계속 나누는 방법을 채택한다.소스 코드import java.uti..

[Algorithm] 최대 공약수, 최소 공배수 구하기 GCD(Greatest Common Divisor) 최대 공약수 구하기 유클리드 호제법 사용 def gcd(a, b): while b: a, b = b, a % b return a a = b x q + r 이라고 했을 때, GCD(a, b) = GCD(b, r)를 만족한다. 간단 증명: 수학적으로 증명하는 방법이 있지만 이해를 위해서 간단히 설명하자면 아래와 같이 표현할 수 있다. b = r x m + n으로 표현할 때, n이 0이라면 b = rm으로 표현된다. 즉, b와 r의 최대 공약수 GCD(b, r) = m이 된다. a = bq + r = rmq + r = r(mq + 1) 이므로 GCD(a, b) = r 이다. => GCD(a, b) = GCD(b, r) = GCD(r, 0) = r LCM(Lo..

이전 1 다음

728x90

티스토리툴바