투자 귀재 규식이3 이미 sublist_max 함수를 각각 Brute Force과 Divide and Conquer 방식으로 작성했는데요. Brute Force로 풀었을 때는 시간 복잡도가 O(n2), Divide and Conquer를 사용했을 때는 O(nlgn)였습니다. 이에는 시간 복잡도를 O(n)로 한 번 더 단축해보세요! ❧ 테스트 셋 def sublist_max(profits): # Code # Test print(sublist_max([7, -3, 4, -8])) print(sublist_max([-2, -3, 4, -1, -2, 1, 5, -3, -1])) ❧ 출력 예시 8 7 ❧ 정답 def sublist_max(profits): # max_profit_so_far : 현재 인덱스 이전까..

7 28 22 16 투자 귀재 규식이2 저번 문제에서 sublist_max 함수를 Brute Force 방식으로 작성했습니다. 이번에는 같은 문제를 Divide and Conquer 방식으로 풀어볼 텐데요. 시간 복잡도는 O(nlg_n_)이 되어야 합니다. 이번 sublist_max 함수는 3개의 파라미터를 받습니다. profits: 며칠 동안의 수익이 담겨 있는 리스트 start: 살펴볼 구간의 시작 인덱스 end: 살펴볼 구간의 끝 인덱스 sublist_max는 profits의 start부터 end까지 구간에서 가능한 가장 큰 수익을 리턴합니다. 합병 정렬을 구현할 때 merge_sort 함수를 깔끔하게 작성하기 위해 추가로 merge 함수를 작성했던 것 기억 나시나요? 마찬가지로 퀵 정렬을 구현할 ..

중복되는 항목 찾기 (N + 1)의 크기인 리스트에, 1부터 N까지의 임의의 자연수가 요소로 할당되어 있습니다. 그렇다면 어떤 수는 꼭 한 번은 반복되겠지요. 예를 들어 [1, 3, 4, 2, 5, 4]와 같은 리스트 있을 수도 있고, [1, 1, 1, 6, 2, 2, 3]과 같은 리스트가 있을 수도 있습니다. (몇 개의 수가 여러 번 중복되어 있을 수도 있습니다.) 이런 리스트에서 반복되는 요소를 찾아내려고 합니다. 중복되는 어떠한 수 ‘하나’만 찾아내도 됩니다. 즉 [1, 1, 1, 6, 2, 2, 3] 예시에서 1, 2를 모두 리턴하지 않고, 1 또는 2 하나만 리턴하게 하면 됩니다. 중복되는 수를 찾는 시간 효율적인 함수를 설계해보세요. ❧ 테스트 셋 def find_same_number(some..

빠르게 산 오르기 신입 사원 장그래는 마부장님을 따라 등산을 가게 되었습니다. 탈수를 방지하기 위해서 1km당 1L의 물을 반드시 마셔야 하는데요. 다행히 등산길 곳곳에는 물통을 채울 수 있는 약수터가 마련되어 있습니다. 다만 매번 줄서 기다려야 한다는 번거로움이 있기 때문에, 시간을 아끼기 위해서는 최대한 적은 약수터를 들르고 싶습니다. 함수 select_stops는 파라미터로 약수터 위치 리스트 water_stops와 물통 용량 capacity를 받고, 장그래가 들를 약수터 위치 리스트를 리턴합니다. 앞서 설명한 대로 약수터는 최대한 적게 들러야겠죠. 참고로 모든 위치는 km 단위이고 용량은 L 단위입니다. 그리고 등산하기 전에는 이미 물통이 가득 채워져 있으며, 약수터에 들르면 늘 물통을 가득 채운..

거듭 제곱 빨리 구하기 거듭 제곱을 계산하는 함수 power를 작성하고 싶습니다. power는 파라미터로 자연수 x와 자연수 y를 받고, xy를 리턴합니다. 가장 쉽게 생각할 수 있는 방법은 반복문으로 단순하게 x를 y번 곱해 주는 방법입니다. 위 알고리즘의 시간 복잡도는 O(y)인데요. O(lgy)로 더 빠르게 할 수 있는 알고리즘을 구현하시오. 주의사항 return x ** y는 답이 아닙니다. 우리는 거듭 제곱을 구하는 원리를 파악하여 효율적인 ‘알고리즘’을 구현하십시오. ❧ 테스트 셋 def power(x, y): # Code # Test print(power(3, 5)) print(power(5, 6)) print(power(7, 9)) ❧ 출력 예시 243 15625 40353607 ❧ 정답 ..

투자 귀재 규식이 1 규식이는 친구들 사이에서 투자의 귀재로 알려져 있습니다. 페이수북과 인수타그램에 자신의 성과를 과시하기 때문인데요. 사실 규식이가 그 정도의 실력자는 아닙니다. 성과가 좋을 때에만 SNS에 공유해서 그렇게 비춰질 뿐이죠. 계속해서 멋진 모습을 보여주기 위해, 특정 기간 중 수익이 가장 큰 구간을 찾아내는 함수 sublist_max를 작성해 보려고 합니다. Brute Force 방법을 이용해서 이 문제를 한 번 풀어봅시다! 주의사항 우선 함수 sublist_max는 파라미터로 리스트 profits를 받는데요. profits에는 며칠 동안의 수익이 담겨 있습니다. 예를 들어서 profits가 [7, -3, 4, -8]이라면 첫 날에는 7달러를 벌었고, 둘째 날에는 3달러를 잃었고, 셋째..

10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 10162(Baekjoon). 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 각각 5분, 1분, 10초이다. 냉동음식마다 전자레인지로 요리해야할 시간 T가 초단위로 표시되어 있다. 우리는 A, B, C 3개의 버튼을 적절히 눌러서 그 시간의 합이 정확히 T초가 되도록 해야 한다. 단 버튼 A,..

1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 1065(Baekjoon). 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다. 출력 첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. b의 최대공약수를 출력한다. ❧ 테스트..

최대공약수 구하기 두 정수 $a$, $b$를 입력받아서, $a$, $b$의 최대공약수를 출력하시오. codeup.kr 2623(Codeup). 최대 공약수 구하기 카드 두 정수 a, b를 입력받아서, a, b의 최대공약수를 출력하시오. 입력 정수 a, b가 공백으로 구분되어 입력된다.(1 0: gcd = C A, B = B, C C = A % B print(gcd) 1️⃣ 유클리드 호제법 사용 2️⃣ 소수를 구하는 방법 사용 시, 시간 복잡도 : O(n) 3️⃣ 유클리드 호제법 사용 시, 시간 복잡도 : O(logn) 유클리드 호제법 [ 1. 교과서 속 주개념] [ 1) 유클리드 호제법] 두 정수 a, b의 최대공약수를 G(a, b)라고 하자. 정수 a, b, q r (b ≠ 0)에 대하여 a = bq ..