일지 & 개발

문제 요약 알고리즘 분류: 유클리드 호제법 난이도: 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의개수가 최대 억이상 갈수 있어서 일반적인 유클리 호제법으로 풀다가는 메로리 초과와 시간 초과 나올수 있기 때문에 ..

문제 요약 알고리즘 분류: 유클리드 호제법 난이도: Silver4 문제내용: 첫 번째 링과 그 뒤의 각 링의 비례 하는 회전 수를 기약 분수 형태로 표현해라. 사이트 주소: https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 문제 풀이 1. 문제 접근 방법 이 문제는 회전의 비례를 구해야 한다. 예를 들어 A가 20 바퀴를 돌아가고 B가 12 바퀴 돌아 간다고 가정 한다면 A : B = 20 : 12 = 10 : 6 = 5 : 3 으로 표현 할수있다. 그래서 기약 분수를 구하기 위..