에라토스테네스의 체 알고리즘 특정한 수의 범위 안에 존재하는 모든 소수를 찾아야 할 때 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘 에라토스테네스의 체 알고리즘의 구체적인 동작 과정 1) 2부터 N까지의 모든 자연수를 나열한다. 2) 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 3) 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않음 !) 4) 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다. 에라토스테네서의 체 알고리즘 동작 예시 1) 2부터 N까지의 모든 자연수를 나열한다. 2) 아직 처리하지 않은 가장 작은 수 2를 제외한 2의 배수는 모두 제거한다 3) 아직 처리하지 않은 가장 작은 수 3을 제외한 3의 배수는 모두 제거..

import math a,b = map(int, input().split()) math.gcd(a,b) math.lcm(a,b)

백준 단계별로 풀어보기(집합과 맵) 파트에서 계속 시간초과가 발생했다. 해결방법으로는 두가지 정도로 요약할 수 있는데, 첫번째로는 리스트 대신 딕셔너리 사용, 두번째로는 개수를 세는 문제에서 for문을 돌면서 세지 말고 파이썬 함수 Counter를 사용하는 것이다. 이 두가지에 대해서 정리를 해보고자 한다. 딕셔너리 diction_name = {} diction_name[key_name] = value_name 딕셔너리를 { }를 통해 하나 만든다. 리스트와 달리 값을 추가할 때 list_name.append(value)가 아니라 key를 찾아서 value를 지정해주는 형식 Counter from collections import Counter c = Counter(nm_name) key 값으로는 이름,..

정의 재귀함수는 함수 안에 함수를 호출하는 함수 (자기 자신을 호출하는 형태) 함수 내에서 그 함수를 다시 사용하는 것 더보기 ⚠ return : 함수를 실행했던 위치로 돌아가라, 함수를 여기서 끝내라는 의미 주의할점 재귀함수는 자기 자신을 호출하기 때문에, 잘못하면 무한히 호출할 수 있다. 따라서 탈출 조건이 필수이다. 예제 간단한 예제 def recursion(n) : # n이 0이면 빠져나오기 if n == 0 : return 0 # n 출력 print(n) # 다시 recursion 함수에 n-1 입력 return recursion(n-1) ---------------------------------------------------------------------------------- recur..