몽상실현개발주의

[BOJ] 1963 / 소수 경로 / Python 파이썬 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 [BOJ] 1963 / 숨바꼭질 문제와 유사한 문제였다. BFS 로 완전탐색을 하면서 memoization 으로 중복 탐색하는 경우를 제거하여 풀이하였다. 소수 판단은 "에라토스테네스의 체" 로 미리 만들어 주었고, 새롭게 생성되는 비밀번호는 자리수별로 0~9까지 변경하여 만들어 주었다. from collections import deque #..

[BOJ] 1476 / 날짜 계산 / Python 파이썬 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 풀이 각각의 수 E, S, M을 1부터 시작하는 15, 28, 19 진법으로 생각하여 풀이하였다. check = [1, 1, 1] cnt = 1 while True: if check == ESM: print(cnt) break check[0] = (check[0] + 1) % 16 if not check[0]: check[0] = 1 check[..

[BOJ] 10610 / 30 / Python 파이썬 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 풀이 주어진 숫자들의 조합으로 가장 큰 30의 배수를 찾는 문제이다. 숫자를 정렬하여 0이 포함되는지 확인하고, 나머지 숫자들이 3의 배수인지 확인하였다. 3의 배수는 각 자리수를 더한 값이 3의로 나누어 떨어지는 숫자이다. nums = list(map(int, list(input()))) nums.sort(reverse=True) def che..

[BOJ] 1676 / 팩토리얼 0의 개수 / Python 파이썬 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 N! 을 구한뒤, 0이 아닌 숫자가 나올때까지의 개수를 세어주는 문제이다. N! 을 구하고 숫자를 문자열로 변환하여 구하였다. N = int(input()) res = 1 for i in range(2, N+1): res *= i res = str(res)[::-1] for i in range(len(res)): if res[i] != '0': print(i) break

[BOJ] 10872 / 팩토리얼 / Python 파이썬 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 팩토리얼을 구하는 문제이다. for 문을 이용하여 간단히 구하였다. N = int(input()) result = 1 for i in range(2, N+1): result *= i print(result)

[BOJ] 2089 / -2진수 / Python 파이썬 https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net 풀이 -2 진수로 변환하는 문제이다. -2 로 나누었을 때 나머지는 0 또는 1 이 나와야 2진수로 표현이 된다. 하지만 정수를 -2로 나누었을때 나머지는 -1, 0, 1 이 나오게 되므로 -1 이 나오는 경우를 고려해 주어야 한다. 나머지가 -..

[BOJ] 11653 / 소인수분해 / Python 파이썬 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이 소인수분해를 한 결과를 오름차순으로 하나씩 출력하는 문제이다. while 문을 이용하여 소수들을 반복하여 나눠 출력하였다. N = int(input()) i = 2 while N != 1: if N % i: i += 1 else: print(i) N = N // i

[BOJ] 6588 / 골드바흐의 추측 / Python 파이썬 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 풀이 골드바흐의 추측 : 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 1000000 이하의 짝수에서 골드바흐의 추측을 검증하는 문제이다. 우선 에라토스테네스의 체를 이용하여 1000000 의 홀수 소수를 구하고, 구해진 홀수 소수를 탐색하여 조건을 검증 하였다. import sys primes..