분류 전체보기127 코딩테스트에서 자주 사용되는 파이썬 주요 라이브러리 [Python] 코딩테스트에서 자주 사용되는 주요 라이브러리 코딩테스트를 준비하며 반드시 알아야 하는 라이브러리 6가지! 1. 내장 함수: 기본 내장 라이브러리 2. itertools: 순열과 조합 3. heapq: 힙(Heap) 기능 제공, 우선순위 큐 기능 구현 4. bisect: 이진 탐색(Bi da2uns2.tistory.com 메모/참고 자료 2023. 6. 20. 백준 알고리즘 2609번: 최대공약수와 최소공배수 문제 정보 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 핵심 유클리드 호제법을 이용한 최대공약수와 최소공배수를 구한다 유클리드 호제법에 대한 간단한 설명은 다음 게시물에서 확인할 수 있다 유클리드 호제법: 두 수의 최대공약수 구하기 유클리드 호제법이란? 두 개의 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 방법 중 하나로, 고대 그리스 수학자인 유클리드가 제안한 알고리즘으로, 매우 간단하면서 효과적인 방법 dduneon.tistory.com 풀이 재귀호출을 사용한 풀이 from sys import stdin N, M = map(int,.. 알고리즘/Python 2023. 6. 19. 유클리드 호제법: 두 수의 최대공약수 구하기 유클리드 호제법이란? 두 개의 자연수의 최대공약수(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. 이전 1 ··· 11 12 13 14 15 16 17 ··· 26 다음
