출근하는 방법1 영훈이는 출근할 때 계단을 통해 사무실로 가는데요. 급할 때는 두 계단씩 올라가고 여유 있을 때는 한 계단씩 올라 갑니다. 어느 날 문득, 호기심이 생겼습니다. 한 계단 또는 두 계단씩 올라가서 끝까지 올라가는 방법은 총 몇 가지가 있을까요? 계단 4개를 올라간다고 가정하면, 이런 방법들이 있습니다. 1, 1, 1, 1 2, 1, 1 1, 2, 1 1, 1, 2 2, 2 총 5개 방법이 있네요. 함수 staircase는 파라미터로 계단 수 n을 받고, 올라갈 수 있는 방법의 수를 효율적으로 찾아서 리턴합니다. ❧ 테스트 셋 def staircase(n): # Code # Test print(staircase(0)) print(staircase(6)) print(staircase(15)) ..

삼송전자 주식 분석 태호는 주식 분석이 취미입니다. 요즘 제일 핫한 종목은 삼송전자인데요. 삼송전자의 주식을 딱 한 번 사고 팔았다면 최대 얼마의 수익이 가능했을지 궁금합니다. 그것을 계산해 주는 O(n) O(n) 함수 max_profit을 작성하세요. max_profit은 파라미터로 일별 주식 가격이 들어 있는 리스트 stock_prices를 받고 최대 수익을 리턴합니다. 주식은 딱 한 번만 사고 한 번만 팝니다. 그리고 사는 당일에 팔 수는 없습니다. 하나의 예시로, 지난 6일간 삼송전자의 주식 가격이 이렇다고 가정합니다. max_profit([7, 1, 5, 3, 6, 4])이 기간 동안 낼 수 있는 최대 수익은 둘째 날 1에 사서 다섯째 날 6에 팔면 총 5의 수익이 생깁니다. ❧ 테스트 셋 de..

투자 귀재 규식이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 ❧ 정답 ..

자료형 : 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 딕셔너리 등 정수형 (Integer) : 양의 정수, 0, 음의 정수 실수형 (Real Number) : 변수에 소수점을 붙이면 실수형으로 나타낸다. 지수 표현 방식: e나 E를 이용한 지수 표현 방식 이용기본적으로 e, E를 이용한 지수 표기 방식을 사용하면 시스템 상에서 자동으로 실수형으로 판단한다. Ex. 1e9 : 10의 9제곱(1,000,000,000) round() : 소수점 이하 수를 반올림하여 입력 값까지 반환└ round(123.456, 2) → 123.46 수 자료형의 연산 / : 나눠진 결과 반환 → 기본 리턴값 : 실수형 % : 나머지 연산 결과 반환 // : 몫 연산 결과 반환 ** : 거듭 제곱 연산 결과 반환 리스..

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