분류 전체보기
-
[알고리즘] 코드잇 - 투자 귀재 규식이2(Python)알고리즘 2023. 9. 29. 19:38
실습설명 저번 챕터에서 sublist_max() 함수를 Brute Force 방식으로 작성했습니다. 이번에는 같은 문제를 Divide and Conquer 방식으로 풀어볼 텐데요. 시간 복잡도는 O(n lg n)이 되어야 합니다. 이번 sublist_max() 함수는 3개의 파라미터를 받습니다. - profits : 며칠 동안의 수익이 담겨 있는 리스트 - start : 살펴볼 구간의 시작 인덱스 - end : 살펴볼 구간의 끝 인덱스 sublist_max()는 profits의 start부터 end까지 구간에서 가능한 가장 큰 수익을 리턴합니다. 합병정렬을 구현할 때 merge_sort() 함수를 깔끔하게 작성하기 위해 추가로 merge() 함수를 작성했던 것 기억 나시나요? 마찬가지로 퀵 정렬을 구현할..
-
[알고리즘] 코드잇 - 중복되는 항목 찾기1(Python)알고리즘 2023. 9. 29. 19:17
실습설명 (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 하나만 리턴하게 하면 됩니다. 중복되는 수를 찾는 시간 효율적인 함수를 설계해 보세요. 힌트1 Brute Force 접근법을 이용해서 리스트 내에 있는 모든 조합을 다 확인하면 쉽게 답을 구할 수 ..
-
[알고리즘] 코드잇 - 빠르게 산 오르기(Python)알고리즘 2023. 9. 29. 19:03
실습설명 신입 사원 장그래는 마부장님을 따라 등산을 가게 되었습니다. 탈수를 방지하기 위해서 1km당 1L의 물을 반드시 마셔야 하는데요. 다행히 등산길 곳곳에는 물통을 채울 수 있는 약수터가 마련되어 있습니다. 다만 매번 줄서 기다려야 한다는 번거로움이 있기 때문에, 시간을 아끼기 위해서는 최대한 적은 약수터를 들르고 싶습니다. 함수 select_stops()는 파라미터로 약수터 위치 리스트 water_stops와 물통 용량 capacity를 받고, 장그래가 들를 약수터 위치 리스트를 리턴합니다. 앞서 설명한 대로 약수터는 최대한 적게 들러야 겠죠. (탈수로 인해서 정상에 도달하지 못하는 경우는 없다고 가정합니다.) 참고로 모든 위치는 km단위이고 용량은 L단위입니다. 그리고 등산하기 전에는 이미 물통..
-
[알고리즘] 코드잇 - 거듭 제곱 빠르게 계산하기(Python)알고리즘 2023. 9. 29. 18:47
실습설명 거듭 제곱을 계산하는 함수 power()를 작성하고 싶습니다. power()는 파라미터로 자연수 x와 자연수 y를 받고 x^y를 리턴합니다. 가장 쉽게 생각할 수 있는 방법은 반복문으로 단순하게 x를 y번 곱해 주는 방법입니다. def power(x, y): total = 1 # x를 y번 곱해 준다 for i in range(y): total *= x return total 이 알고리즘의 시간 복잡도는 O(y)인데요. O(lg y )로 더빠르게 할 수는 없을까요? 주의사항 return x**y는 답이 아닙니다. 우리는 거듭 제곱을 구하는 원리를 파악하여 효율적인 알고리즘을 구현하고 싶은 것입니다. 답안 def power(x, y): if y == 0: return 1 # 계산을 한 번만 하기 ..
-
[알고리즘] 코드잇 - 투자 귀재 규식이1(Python)알고리즘 2023. 9. 29. 18:39
실습설명 규식이는 친구들 사이에서 투자의 귀재로 알려져 있습니다. 페이수북과 인수타그램에 자신의 성과를 과시하기 때문인데요. 사실 규식이가 그정도의 실력자는 아닙니다. 성과가 좋을 때에만 SNS에 공유해서 그렇게 비춰질 뿐이죠. 계속해서 멋진 모습을 보여주기 위해, 특정 기간 중 수익이 가장 큰 구간을 찾아내는 함수 sublist_max()를 작성해보려고 합니다. Brute Force 방법을 이용해서 이 문제를 한번 풀어 봅시다. 함수설명 우선 함수 sublist_max()는 파라미터로 리스트 profits를 받는데요. profits에는 며칠 동안의 수익이담겨 있습니다. 예를 들어서 profits 가 [7, -3, 4, -8]이라면 첫 날에는 7달러를 벌었고, 둘째 날에는 3달러를 잃었고, 셋째 날에는 ..
-
[알고리즘] Greedy Algorithm : 수강신청알고리즘 2023. 9. 29. 16:51
실습설명 이번 학기 코드잇 대학교의 수업 리스트가 나왔습니다. [(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 6), (13, 16), (9, 11), (1, 8)] 리스트에 담겨있는 튜플들은 각각 하나의 수업을 나타냅니다. 각 튜플의 0번째 항목은 해당 수업의 시작교시, 그리고 1번 항목은 해당 수업이 끝나는 교시입니다. 예를 들어서 0번 인덱스에 있는 튜플값은 (4,7)이니까 해당 수업은 4교시에 시작해서 7교시에 끝나는 거죠. (2,5)를 듣는다고 가정합시다. (4,7)수업은 (2,5)가 끝나기 전에 시작하기 때문에, 두 수업은 같이 들을 수 없습니다.반면, 수업(1,3)과 (4,7)은 시간이 겹치지 않기 때문에 동시에 들을 수 있습니다. (단, (2,5), (5,..
-
[알고리즘] Greedy Algorithm : 지각 벌금 적게 내기알고리즘 2023. 9. 29. 16:37
실습설명 익중이네 밴드부는 매주 수요일 오후 6시에합주를 하는데요. 멤버들이 너무 상습적으로 늦어서, 1분에 1달러씩 내야 하는 벌금 제도를도입했습니다. 그런데마침익중이와 친구 넷이놀다가 또 지각할 위기입니다. 아직 악보도 출력해 놓지 않은 상황이죠. 어어차피 같이 놀다 늦은 것이니 벌금을 다섯명이서 똑같이 나눠 내기로 하고, 벌금을 가능한 적게 내는 방법을 고민해 보기로 합니다. 다섯 사람이 각각 출력해야 하는페이지 수는 3장, 1장, 4장, 3장, 2장 입니다. 프린터는 한 대밖에 없고 1장을 출력하기 위해서는 1분이 걸립니다. 현재 순서대로 출력한다면, 아래와 같이 총 39달러의 벌금을 내야 합니다. 1. 첫 번쨰 사람 : 3분지각 2. 두 번째 사람 : 3 + 1분 지각 3. 세 번째 사람 : 3..
-
[알고리즘] Greedy Algorithm : 최대 곱 구하기알고리즘 2023. 9. 29. 15:24
실습설명 def max_product(card_lists): # 여기에 코드를 작성하세요 # 테스트 코드 test_cards = [[1, 2, 3], [4, 6, 1], [8, 2, 4], [3, 2, 5], [5, 2, 3], [3, 2, 1]] print(max_product(test_cards)) 여럿이서 카드게임을 하고 있는데,각 플레이어는3장의 카드를 들고 있습니다.위의 경우 첫 번째, 플레이어는 1,2,3을 들고 있고, 두번째 플레이어는 4,6,1을 들고 있고, 세번째 플레이어는 8,2,4를 들고 있는거죠. 함수 max_product는 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 리턴합니다. max_product를 Greedy Algorithm 방식으로 구현해 보세요. d..