본문 바로가기
반응형

백준397

(Python/🥈2)백준 알고리즘 4948번: 베르트랑 공준 문제 출처:https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 풀이: array = list() for i in range(2, 246913): # 범위 설정 count = 0 for j in range(2, int(i**0.5)+1): # 2n의 제곱근 if i % j == 0: # 소수 아닌거 찾고 count += 1 # 소수면 카운트 올림 break if count == 0: # 소수 이면 array.append(i) # 리스트에 추가.. 2022. 5. 17.
(Python/🥈3)백준 알고리즘 1929번: 소수 구하기 문제 출처:https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 틀린 풀이: M,N = input().split() M = int(M) N = int(N) # M,N = map(int,input().split()) for i in range(M,N+1): #3부터 16까지 if i != 1: for k in range(2,i): if i % k ==0: break else: print(i) 처음에 이렇게 작성해서 답은 나오지만 시간초과가 나왔다. 이중포문을 사용해 빅오가 O(n^2.. 2022. 5. 17.
(Python/🥈5)백준 알고리즘 11653번: 소인수분해 문제 출처:https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 풀이: N = int(input()) i = 2 # 제일 작은 나누는 수 선언 while N != 1: # 입력받은 수 1이 아닐떄 if N%i ==0: # N 나누기 i 의 몫이 0 >> 즉 2의배수일때 N /= i # N은 2로 나누고 다시 N에 저장 print(i) # 2출력 else: # 2의 배수가 아니면 i +=1 # 최소공배수를 +1 if i>N: # 쭉 진행하다가 최소공배수보다 바뀌는 N보다 클떄 break # for문 탈출 다른 풀이: n = int(input()) d = 2 while d.. 2022. 5. 17.
(Python/🥈5)백준 알고리즘 2581번: 소수 문제 출처:https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 풀이: M = int(input()) N = int(input()) sum = 0 list = list() for i in range(M,N+1): if i != 1: for k in range(2,i): if i % k ==0: break else: sum += i list.append(i) print(sum,min(list)) 처음에 이렇게 했더니 런타임 에러가 났다. 확인해보니 -1 나오는게.. 2022. 5. 16.
에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다. 이 방법은 마치 체로 치듯이 수를 걸러낸다. 코드: def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n m = int(n ** 0.5) # 제곱근 for i in range(2, m + 1): if sieve[i] == True: # i가 소수인 경우 for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정 sieve[j] = False # 소수.. 2022. 5. 16.
Greedy-Algorithm (탐욕 알고리즘) Greedy-Algorithm 탐욕 알고리즘은 현재 사용 가능한 최상의 옵션을 선택하여 문제를 해결하는 접근 방식 하향식 접근 방식으로 작동한다. 이 알고리즘은 모든 문제에 대해 최상의 결과를 생성하지 않을 수 있다. 문제에 다음 속성이 있는 경우 사용할 수 있는지 여부를 결정할 수 있다. 1. 그리디 초이스 속성 한 번 선택한 이전 단계를 다시 고려하지 않고 각 단계에서 최선의 선택을 선택하여 문제에 대한 최적의 솔루션을 찾을 수 있다면 탐욕적인 접근 방식을 사용하여 문제를 해결할 수 있습니다. 이 속성을 탐욕 선택 속성이라 한다. 2. 최적의 하부구조 문제에 대한 최적의 전체 솔루션이 하위 문제에 대한 최적의 솔루션에 해당하는 경우 탐욕적인 접근 방식을 사용하여 문제를 해결할 수 있다. 이 속성을 최.. 2022. 5. 16.
반응형

티스토리툴바