알고리즘90 유클리드 호제법: 두 수의 최대공약수 구하기 유클리드 호제법이란? 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법 중 하나로, 고대 그리스 수학자인 유클리드가 제안한 알고리즘으로, 매우 간단하면서 효과적인 방법 원리? 자연수 a와 b가 있다고 하면, a를 b로 나눈 나머지를 구한다. 나머지를 r이라고 한다. 나머지 r이 0이라면, b는 a와 b의 최대공약수이다. 따라서 알고리즘을 종료하고 b를 결과로 출력한다. 만약 나머지 r이 0이 아니라면, b를 a로 대체하고, r을 b로 대체한다. 다시 말해서 GCD(a, b) = GCD(b, r) 인 것이다. 식으로 풀면, a = bq + r 일 때 GCD(a, b) = GCD(b, r)이다 예시? 48과 18의 최대공약수(GCD)를 구해보면, 1. 48 % .. 알고리즘/개념 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. 백준 알고리즘 9663번: N-Queen (Python) 문제 정보 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 핵심 1. 백트래킹을 사용하되, 시간복잡도를 고려할 것 퀸을 놓을 수 있는 경우의 수는 어마무시하기 때문에, 시간복잡도를 고려해주지 않으면 엄청난 실행시간이 소요된다 2. 2차원 배열을 사용하지 말것 2차원 배열을 사용하면 직관적으로 퀸이 놓을수 있는 위치를 파악할 수는 있지만 매우 비효율적인 방법이다. 2차원 배열을 사용하지 않고도, 1차원 배열로 문제를 풀이할 수 있다 (아래에서 설명) 3. Python으로 굳이 제출하지 말것 이건 백준 알고리즘 질문게시판에서 본.. 알고리즘/Python 2023. 6. 17. 이전 1 ··· 9 10 11 12 13 14 15 ··· 18 다음
