일지 & 개발

문제 요약 알고리즘 분류: 유클리드 호제법 난이도: Silver1 문제내용: A, B 1의 개수가 주어지면 A, B의 최대 공약수를 구해라 사이트 주소: https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 문제 풀이 이번 문제는 유클리드 호제법이다. 유클리드 호제법에 대한 설명은 여기에서 확인해보면된다. 하지만 1의개수가 최대 억이상 갈수 있어서 일반적인 유클리 호제법으로 풀다가는 메로리 초과와 시간 초과 나올수 있기 때문에 ..

문제 요약 알고리즘 분류: 유클리드 호제법 난이도: Gold4 문제내용: 종이의 적힌 수에서 M으로 나누었을 때 나머지가 같은 M의 수를 모두 구하세요. M은 1보다 커야 한다. 사이트:https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 문제풀이 import sys input = sys.stdin.readline array = [int(input()) for _ in range(int(input()))] min_num = min(array) result = [] ..

이론 1. 유클리드 호제법이란? 두 개의 정수 혹은 다수의 자연수에서 최대공약수를 구하는 알고리즘이다. 원리는 두 수가 서로 나눠서 나머지를 구한다. 만약 나머지가 0이면 그 수가 최대 공약수가 되는것이다. 만약에 나머지가 0이 아니면 나머지가 0일 될때까지 두 수를 나누어 주면 된다. 기존 최대공약수를 구할때는 2개 이상에 각 수의 약수를 구한다음 공통으로 있는 약수중 최대값을 구해야 했다. 위의 그림을 보면 30, 24에서 학교에서 기본것으로 배운 토대로 최대공약수를 구한다면 먼저, 약수를 구해서 공통된 수가 6, 3, 2, 1이고 이중에서 가장 큰것이 6이다. 6이라는 숫자가 30, 24 최대 공약수이다 수가 30, 24라서 각 약수의 수가 적어서 구하는데 금방 걸리는데 100단위 또는 1000단위..