알고리즘5 소수판별, 에라토스테네스의 체 소수 소수란 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수를 말한다. 에라토스테네스의 체 란 소수를 판별하는 알고리즘이다. 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 단일 숫자 소수 여부 확인 어떤 수가 소수인지 여부를 확인할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 빠르게 판별할 수 있다. import math num = 10 def isPrime(num) : if(num 2022. 1. 27. [백준][Python][5430] AC https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제설명 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이.. 2021. 11. 13. [Python][백준 1406] 에디터. https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net - 처음 이문제를 접했을 때 list로 접근하여 문자 사이에 값을 넣는 방법으로 풀려고 했으나 그럴경우 시간이 초과되어 다른 방법으로 해결하였습니다. deque 2개를 사용하여 커서 기준으로 왼쪽 과 오른쪽으로 구분하여 풀었습니다. 소스코드 import sys from collections import deque N = sys.stdin.readline().strip() M = int(sys.std.. 2021. 9. 19. [Baekjoon][Python][10989] 수 정렬하기3 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 설명 이전문제에서보다 N의 범위가 증가하였습니다. N의 범위 때문에 정렬 알고리즘(병합, 퀵, 힙)을 사용하기엔 어렵고 수의 범위가 작아진 것을 확인할 수 있습니다( 0 2021. 9. 16. [백준][Python] 2751번. 수 정렬하기 2 설명 이 문제는 숫자들을 오름차순으로 정렬하는 문제이다. 정렬하는데 있어 문제가 N의 범위가 100만까지 가기 때문에 시간복잡도가 중요한 문제이다. 시간복잡도가 O(N2) 인 정렬은 사용할 수 없다. 여기서 O(NlogN) 인 고급 정렬 알고리즘(병합 정렬, 퀵 정렬, 힙 정렬)을 이용하거나 기본 정렬 라이브러리를 사용하는 방법이 있다. ( ※ 파이썬의 기본 정렬함수 ( sort(), sorted() ) 는 퀵 정렬로 되어있다. ) 소스코드 import sys N = int(input()) list = [int(sys.stdin.readline()) for _ in range(N)] list.sort() for val in list : sys.stdout.write(str(val)+'\n') 해설 파이썬.. 2021. 9. 12. 이전 1 다음
