알고리즘/Python36

• 백준 알고리즘 15686번: 치킨 배달 (Python) 문제 정보 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 핵심 모든 치킨집들 중 M개의 치킨집을 갖는 부분집합들을 구해서, 각 집까지의 최소 치킨 거리를 갖는 부분집합을 구하기 풀이 from sys import stdin from itertools import combinations N, M = map(int, stdin.readline().split()) house = [] chicken = [] for i in range(N): row = list(map(int, stdin.readl.. 알고리즘/Python 2023. 6. 26.

• 백준 알고리즘 2609번: 최대공약수와 최소공배수 문제 정보 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 핵심 유클리드 호제법을 이용한 최대공약수와 최소공배수를 구한다 유클리드 호제법에 대한 간단한 설명은 다음 게시물에서 확인할 수 있다 유클리드 호제법: 두 수의 최대공약수 구하기 유클리드 호제법이란? 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법 중 하나로, 고대 그리스 수학자인 유클리드가 제안한 알고리즘으로, 매우 간단하면서 효과적인 방법 dduneon.tistory.com 풀이 재귀호출을 사용한 풀이 from sys import stdin N, M = map(int,.. 알고리즘/Python 2023. 6. 19.

• 백준 알고리즘 1929번: 소수 구하기 (Python) 문제 정보 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 핵심 앞서 설명한 에라토스테네스의 체를 활용하여 문제를 풀이해야 함 해당 글은 아래 참고 링크를 확인하면 될것 같다 풀이 from sys import stdin M, N = map(int, stdin.readline().split()) prime = [True for _ in range(N+1)] prime[0], prime[1] = False, False for i in range(2, int(N**0.5)+1): if prime[i]: j = 2 while i*j 알고리즘/Python 2023. 6. 19.

• 백준 알고리즘: 1978번 소수 찾기 문제 정보 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 핵심 소수를 구하는 방법을 알면 된다 정수 N을 2부터 N-1까지 나누었을 때 나누어지는 수가 없다면 소수라고 할 수 있다 이 문제의 경우 주어지는 수가 1,000 이하로 정해져 있고, 수가 비교적 작기 때문에 직접 주어지는 N을 2 ~ N-1 으로 하나하나 나누어서 소수인지 아닌지를 판별하면 되지만 수가 커지는 경우는 에라토스테네스의 체 알고리즘을 사용하여 풀이해야 한다 나는 에라토스테네스의 체 알고리즘을 사용하여 풀이하였다 에라토스테네스의 체에 관한 내용은 아래 참고에 링크를 달아두었으니, 모른다면 확인하면 좋을것 .. 알고리즘/Python 2023. 6. 19.

• 백준 알고리즘 1037번: 약수 (Python) 문제 정보 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 핵심 간단한 수학적 지식이 있다면 풀 수 있는 문제이다 예를 들어 8의 약수를 생각해 보면, 1, 2, 4, 8 다음과 같은데, 1과 8이 한 쌍을 이루고 2와 4가 한 쌍을 이룬다 (두 수를 곱하면 8이 되는 것이다) 여기서 1과 8은 진짜 약수가 아니므로 해당 문제에서 주어지지 않고 2와 4가 주어진다 이 두 수를 곱해주면 되는데 이 경우 주어진 진짜 약수들 중 가장 작은 수와 가장 큰 수를 곱하면 우리는 N을 알 수 있는 것이다 다만 9의.. 알고리즘/Python 2023. 6. 18.