알고리즘 문제65 다이나믹 프로그래밍 예제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 # 정수 X를 입력받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 dp 테이블 초기화 d = [0] * 30001 # 다이나믹 프로그래밍(Dynamic programming) 진행(보텀업) for i in range(2, x+1): # 현재의 수에서 1을 빼는 경우 d[i] = d[i - 1] +1 # 현재의 수가 2로 나누어 떨어지는 경우 if i % 2 == 0: d[i] = min(d[i], d[i // 2] +1) if i % 3 == 0: d[i] = min(d[i], d[i // 3] +1) if i % 5 == 0: d[i] = min(d[i], d[i // 5] +1) Colored b.. 2020. 10. 22. 다이나믹 프로그래밍 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 # 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍) def fibo(x): print('f('+str(x)+')', end=' ') # 종료 조건(1 혹은 2일 때 1을 반환) if x == 1 or x == 2: return 1 # 이미 계산한 적 있는 문제라면 그대로 반환 if d[x] != 0: return d[x] # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 .. 2020. 10. 22. 다이나믹 프로그래밍 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 # 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍) def fibo(x): print('f('+str(x)+')', end=' ') # 종료 조건(1 혹은 2일 때 1을 반환) if x == 1 or x == 2: return 1 # 이미 계산한 적 있는 문제라면 그대로 반환 if d[x] != 0: return d[x] # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 .. 2020. 10. 22. 이진 탐색 예제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 # 이진 탐색 소스코드 구현(반복문) def binary_search(array,target, start, end): while start target: end = mid -1 else : start = mid +1 return None # N(가게의 부품 개수) 입력 n = int(input()) # 가게에 있는 전체 부품 번호를 공.. 2020. 10. 22. 이진 탐색 1 2 3 4 5 6 7 8 # 순차 탐색 소스 코드 구현 def sequential_search(n,target,array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i +1 #현재의 위치 반환(인덱스는 0부터 시작하므로 1더하기) Colored by Color Scripter cs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 # 이진 탐색 소스코드 구현(재귀 함수) def binary_search(array, target, start, end): if start > en.. 2020. 10. 22. 정렬 예제 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 # 위에서 아래로 (내림차순) # N을 입력받기 n = int(input()) # N개의 정수를 입력받아 저장 array =[] for i in range(n): array.append(int(input())) # 파이썬 기본 정렬 라이브러리를 이용하여 정렬 수행 array = sorted(array, reverse=True) # 정렬이 수행된 결과를 출력 for i in array: print(i, end=" ") cs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 # 성적이 낮은 순서로 학생 출력하기 # 1 2020. 10. 22. 이전 1 ··· 7 8 9 10 11 다음