본문 바로가기

전체 글115

[BOJ/PYTHON] 11689. GCD(n, k) = 1 백준 문제 링크: https://www.acmicpc.net/problem/11689 문제 요약 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하기 핵심 아이디어 오일러 피 함수를 쓰면 된다. 오일러 피 함수란 n이하의 서로소 개수를 구할 때 사용하는 함수이다. n을 구성하는 소인수인 p들에 대해, n에 (1 - 1/p)를 곱하면 된다. 60의 경우 소인수분해하면 2^235라서, 2, 3, 5가 p이다. 오일러피 함수를 이용해 60 이하의 이하의 서로소 개수를 구하면, 60 * 1/2 * 2/3 * 4/5 = 16이다. 풀이 # gold1-11689. GCD(n, k) = 1 import sys, math input = sys.stdin.readlin.. 2023. 8. 17.
[BOJ/PYTHON] 11401. 이항 계수 3 백준 문제 링크: https://www.acmicpc.net/problem/11401 문제 요약 이항 계수를 1,000,000,007로 나눈 나머지 핵심 아이디어 팩토리얼의 경우 바텀업으로 for문을 돌려서 팩토리얼문을 구해두고, 페르마의 소정리를 이용해서 구해주면 된다. 풀이 # gold1-11401. 이항 계수 3 import sys input = sys.stdin.readline large = 1000000007 n, k = map(int, input().split()) factorial = [1 for _ in range(n+1)] def square(a): a = a % large a = a * a return a % large def binary_power(n, k): if k == 1: re.. 2023. 8. 17.
[BOJ/PYTHON] 4375. 1 백준 문제 링크: https://www.acmicpc.net/problem/4375 문제 요약 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수 구하기 핵심 아이디어 num이라는 변수를 정의한 후, while문을 돌면서 나눠떨어지면 자릿수를 출력하고 아니면 num * 10 + 1으로 뒤에 1을 더해주면 된다. 풀이 # silver3-4375. 1 import sys input = sys.stdin.readline while True: try: n = int(input()) num = 1 while True: if num % n == 0: print(len(str(num))) break else: num = num * 10 + .. 2023. 8. 17.
[BOJ/PYTHON] 1074. Z 백준 문제 링크: https://www.acmicpc.net/problem/1074 문제 요약 배열을 Z모양(왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로)으로 탐색할 때, r행 c열을 몇 번째로 방문했는지 핵심 아이디어 재귀를 쓰면 되는데, 큰 거부터 구획으로 돌고 작은 거로 재귀로 넘어와야 한다. 이때 탐색 횟수를 더해주는 식으로 모든 칸을 일일이 다 재귀를 돌면 메모리 초과가 나온다. 사분면을 나눠 몇 사분면인지 체크 후 해당 사분면으로 들어가서 다시 나누면 된다. 풀이 # silver1-1074. Z import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n, r, c = map(int, input().split().. 2023. 8. 17.
[BOJ/PYTHON] 2438. 별 찍기 - 1 백준 문제 링크: https://www.acmicpc.net/problem/2438 문제 요약 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제 핵심 아이디어 for문을 돌아가며 별을 찍어주면 된다. 풀이 # bronze5-2438. 별 찍기 - 1 import sys input = sys.stdin.readline n = int(input()) for i in range(1, n + 1): print("*" * i) 실행 시간 메모리 31256KB, 시간 40ms (python3) 2023. 8. 17.
[BOJ/PYTHON] 1182. 부분수열의 합 백준 문제 링크: https://www.acmicpc.net/problem/1182 문제 요약 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수 핵심 아이디어 브루트포스로 다 구해주면 된다. 경우의 수를 백트래킹을 사용해 구해줬다. 풀이 # silver2-1182. 부분수열의 합 import sys input = sys.stdin.readline n, s = map(int, input().split()) nums = list(map(int, input().split())) cnt = 0 # 경우의 수 array = [] def back(depth, nums_sum): global cnt if depth == n: if nums_s.. 2023. 8. 17.

티스토리툴바