분류 전체보기
-
[알고리즘] 합병정렬 : merge 함수 작성알고리즘 2023. 9. 28. 17:01
합병정렬에서의 Divide and Conquer 1. Divide 리스트를 반으로 나눈다. 2. Conquer 왼쪽 리스트와 오른쪽 리스트를 각각 정렬한다. 3. Combine 정렬된 두 리스트를 하나의 정렬된 리스트로 합병한다. 실습설명 합병 정렬 알고리즘 중 사용되는 merge 함수를 작성해 보세요. merge 함수는 정렬된 두 리스트 list1과 list2를 받아서, 하나의 정렬된 리스트를 리턴합니다. 해설 힌트1 merge 함수는 정렬된 두 리스트 list1과 list2를 파라미터로 받고, 합쳐진 리스트(merged_list)를 리턴해주는데, 처음에는 merged_list를 빈 리스트로 정의한다. merged_list = [] list1과 list2는 이미 정렬되어 있기 때문에, merged_li..
-
[알고리즘] Divide and Conquer 분할정복 : 1부터 n까지의합알고리즘 2023. 9. 28. 15:51
선행 : 재귀개념 분할정복 : 부분문제를 풀고, 그 솔루션을 활용하여 문제를 해결한다. 1. Divide : 인풋 x를 x1과 x2로 나눈다. 2. Conquer : f(x1) ,f(x2) -> divide/conquer/combine로 나눠질 수 있음 3. Combine : f(x) 계산 실습설명 Divide and Conquer를 이용해서 1부터 n까지더하는 예시를 보았는데요. 코드로 한 번 구현해 봅시다. 우리가 작성할 함수 consecutive_sum은 두 개의 정수 인풋 start와 end를 받고, start부터 end까지의 합을 리턴합니다. end는 start보다 크다고 가정합니다. 답안 def consecutive_sum(start, end): # 여기에 코드를 작성하세요 if start =..
-
[알고리즘] Brute Force : 런던 폭우알고리즘 2023. 9. 28. 11:50
실습설명 런던에 엄청난 폭우가 쏟아진다고 가정합시다. 정말 재난 영화에서나 나올법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도입니다. 그렇게 되었을 때, 건물과 건물 사이에 얼만큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 trapping_rain을 작성해 보려고 합니다. 함수 trapping_rain은 건물 높이 정보를 보관하는 리스트 buildings를 파라미터로 받고, 담기는 빗물의 총량을 리턴해 줍니다. 예를 들어서 파라미터 buildings로 [3, 0, 0, 2, 0, 4]가 들어왔다고 합시다. 그러면 0번 인덱스에 높이 3의건물이, 3번 인덱스에 높이 2의 건물이, 5번 인덱스에 높이 4의 건물이 있다는 뜻입니다. 1번, 2번, 4번 인덱스에는 건물이 없습니다. ..
-
[알고리즘] Brute Force : 카드 뭉치 최대 조합, 가까운 매장 찾기알고리즘 2023. 9. 28. 11:37
Brute Force : 모든 경우의수 알고리즘 접근법(비효율적임) 장점 : 직관적이고 명확하다. 답을 확실하게 찾을 수 있다.(인풋값이 작다면 괜찮음) 실습설명 카드 두 뭉치가 있습니다. 왼쪽 뭉치에서 카드를 하나 뽑고 오른쪽 뭉치에서 카드를 하나 뽑아서, 두 수의 곱이 가장 크게 만들고 싶은데요. 어떻게 하면 가장 큰 곱을 구할 수 있을까요? 함수 max_product는 리스트 left_cards와 리스트 right_cards를파라미터로 받습니다. left_cards는 왼쪽 카드 뭉치의 숫자들, right_cards는 오른쪽 카드 뭉치 숫자들이 담겨있고, max_product는 left_cards에서 카드 하나와 right_cards에서 카드 하나를 뽑아서 곱했을 때 그 값이 최대가 되는 값을 리턴합..
-
[알고리즘] 하노이의탑알고리즘 2023. 9. 24. 22:35
설명) 하노이의 탑 게임 아시나요? 이 게임의 목표는 왼쪽 기둥에 있는 원판들을 모두 오른쪽 기둥으로 옮기는 것입니다. 지켜야할 규칙은 두가지입니다. 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있어서는 안된다. (출저: 위키피디아) 하노이의 탑 게임의 해답을 출력해주는 함수 hanoi를 쓰세요. hanoi는 파라미터로 원판 수 num_disks, 게임을 시작하는 기둥 번호 start_peg, 그리고 목표로 하는 기둥 번호 end_peg를 받고, 재귀적으로 문제를 풀어 원판을 옮기는 순서를 모두 출력합니다. 문제) def move_disk(disk_num, start_peg, end_peg): print("%d번 원판을 %d번 기둥에서 %d번 기둥으로 이동" % (disk..
-
[알고리즘] 리스트 뒤집기알고리즘 2023. 9. 24. 22:11
실습설명) 파라미터로 리스트 some_list를 받고, 뒤집힌 리스트를 리턴해 주는 재귀 함수 flip을 쓰세요. 반복문은 쓰면 안됩니다! 문제) # 파라미터 some_list를 거꾸로 뒤집는 함수 def flip(some_list): # 여기에 코드를 작성하세요 # 테스트 코드 some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9] some_list = flip(some_list) print(some_list) 실행결과) [9, 8, 7, 6, 5, 4, 3, 2, 1] 답안) # 파라미터 some_list를 거꾸로 뒤집는 함수 def flip(some_list): # 여기에 코드를 작성하세요 if(len(some_list)
-
[알고리즘] 자릿수의 합알고리즘 2023. 9. 17. 22:54
실습설명) 파라미터로 정수값 n을 받고 n의 각 자릿수의 합을 리턴해 주는 재귀함수 sum_digits를 작성하세요. 반복문을 쓰지 말고, 재귀(recursion)의 개념을 활용해 주세요! 문제 ) # n의 각 자릿수의 합을 리턴 def sum_digits(n): # 여기에 코드를 작성하세요 # 테스트 코드 print(sum_digits(22541)) print(sum_digits(92130)) print(sum_digits(12634)) print(sum_digits(704)) print(sum_digits(3755)) 실행결과 ) 14 15 16 11 20 답안 ) # n의 각 자릿수의 합을 리턴 def sum_digits(n): # 여기에 코드를 작성하세요 if(n
-
[알고리즘] 숫자합 : 자연수 11부터 n까지의 합알고리즘 2023. 9. 17. 22:43
실습설명 ) n 번째 삼각수(triangle number)는 자연수 11부터 n까지의 합입니다. 파라미터로 정수값 n을 받고 �n 번째 삼각수를 리턴해 주는 재귀 함수 triangle_number를 쓰세요.n은 11 이상의 자연수라고 가정합시다. 함수 안에 반복문은 쓰면 안됩니다! 문제 ) # 1부터 n까지의 합을 리턴 def triangle_number(n): # 여기에 코드를 작성하세요 # 테스트 코드: triangle_number(1)부터 triangle_number(10)까지 출력 for i in range(1, 11): print(triangle_number(i)) 실행결과 ) 1 3 6 10 15 21 28 36 45 55 답안) # 1부터 n까지의 합을 리턴 def triangle_numbe..