본문 바로가기
반응형

알고리즘149

(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.
(Python/🥉1)백준 알고리즘 2775번: 부녀회장이 될테야 문제 출처:https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 풀이: n = int(input()) # 테스트케이스 갯수 for i in range(n): k = int(input()) #층수 n = int(input()) #호수 result = [i for i in range(1,n+1)] # for문 값을 변수 i 에다가 담음 for j in range(k): for x in range(1,n): result[x] += result[x-1] # j = 1일때 result[1] = 1 .. 2022. 5. 14.
(Python/🥉3)백준 알고리즘 10250번: ACM 호텔 문제 출처:https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 풀이: T = int(input()) # H 층수 W = 방수 N = 손님 for i in range(T): H,W,N = list(map(int,input().split())) num = (N//H +1) #라인 = (N//H)+1 라인 line = N%H # % 나머지반환 if line == 0: #층이 H의 배수이면 num = N//H line = H print(lin.. 2022. 5. 13.
반응형

티스토리툴바