Q1. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오.
input = "abadabac"
def find_not_repeating_first_character(string):
existing_char = []
for character in string:
if character not in existing_char:
existing_char.append(character)
else:
existing_char.remove(character)
if existing_char:
return existing_char[0]
else:
return "_"
result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))Note:
list.remove(element)
Q2. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오.
소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다.
input = 20
def find_prime_list_under_number(number):
prime_list = []
for n in range(2, number + 1):
for i in prime_list:
if n % i == 0:
break
else:
prime_list.append(n)
return prime_list
result = find_prime_list_under_number(input)
print(result) # [2, 3, 5, 7, 11, 13, 17, 19]
Note:
for n in range(): for i in list:
Q3. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다.
할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.
input = "011110"
def find_count_to_turn_out_to_all_zero_or_all_one(string):
to_zero = 0
to_one = 0
if string[0] == '0':
to_one += 1
elif string[0] == '1':
to_zero += 1
for i in range(len(string) -1):
if string[i] != string[i+1]:
if string[i+1] == '0':
to_one += 1
elif string[i+1] == '1':
to_zero += 1
return min(to_zero, to_one)
result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result) # answer = 1Q4. 요세푸스 문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
def josephus_problem(n, k):
eliminated = []
ppl_list = list(range(1, n + 1))
next_idx = k - 1
while ppl_list:
result = ppl_list.pop(next_idx)
eliminated.append(result)
# if there are still ppl
if len(ppl_list) != 0:
# find next_idx and wrap it for circular data strucutre
next_idx = (next_idx + (k - 1)) % len(ppl_list)
print("<", ", ".join(map(str, eliminated)), ">", sep='')
n, k = 7, 3
# n, k = map(int, input().split())
josephus_problem(n, k)Q5. 배달 가능 여부를 반환하시오.
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]
def is_available_to_order(menus, orders):
menus_set = set(menus)
for order in orders:
if order not in menus_set:
return False
return True
result = is_available_to_order(shop_menus, shop_orders)
print(result)Recursion
Q6. 다음과 같이 문자열이 입력되었을 때, 회문이라면 True 아니라면 False 를 반환하시오.
input = "abcba"
def is_palindrome(string):
if len(string) <= 1:
return True
if string[0] != string[-1]:
return False
return is_palindrome(string[1:-1])
print(is_palindrome(input))Q7. Merge Sort
array = [5, 3, 2, 1, 6, 8, 7, 4]
def merge_sort(array):
if len(array) <= 1:
return array
mid = len(array) // 2
left_array = array[:mid]
right_array = array[mid:]
return merge(merge_sort(left_array), merge_sort(right_array))
def merge(array1, array2):
result = []
array1_index = 0
array2_index = 0
while array1_index < len(array1) and array2_index < len(array2):
if array1[array1_index] < array2[array2_index]:
result.append(array1[array1_index])
array1_index += 1
else:
result.append(array2[array2_index])
array2_index += 1
if array1_index == len(array1):
while array2_index < len(array2):
result.append(array2[array2_index])
array2_index += 1
if array2_index == len(array2):
while array1_index < len(array1):
result.append(array1[array1_index])
array1_index += 1
return result
print(merge_sort(array)) # [1, 2, 3, 4, 5, 6, 7, 8] DFS
Q8. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.
def find_target_number(numbers, target_number):
def dfs(index, current_sum):
# 탈출 조건: 모든 숫자를 사용했을 때
if index == len(numbers):
# 현재 합계가 타겟 넘버와 같으면 1 반환, 아니면 0 반환
return 1 if current_sum == target_number else 0
# 현재 숫자를 더하거나 빼는 경우를 모두 탐색
return dfs(index + 1, current_sum + numbers[index]) + dfs(index + 1, current_sum - numbers[index])
# 시작 조건: 첫 번째 숫자부터 시작하고, 현재 합계는 0
return dfs(0, 0)
# 예제 사용
numbers = [1, 1, 1, 1, 1]
target_number = 3
print(find_target_number(numbers, target_number))
Note:
- 문제의 재귀적 성질: 각 단계에서 숫자를 더하거나 빼는 선택은 이전 선택에 의존적이며, 각 선택 후에는 동일한 문제의 더 작은 하위 문제를 해결하게 됩니다. 이러한 성질은 재귀적 접근 방식과 일치합니다.
- 모든 가능한 조합 탐색 필요: 주어진 숫자들로 만들 수 있는 모든 조합을 탐색해야 하는데, 이는 깊이 우선 탐색(DFS)으로 효과적으로 처리할 수 있습니다. DFS는 가능한 모든 경로를 깊이 방향으로 탐색하며, 이 경우 각 숫자를 더하거나 뺄 수 있는 두 가지 경로를 모두 탐색합니다.
- 브랜치 프루닝이 필요 없는 경우: 이 문제에서는 탐색 과정에서 브랜치(가지)를 미리 가지치기(프루닝)할 필요가 없습니다. 모든 가능한 조합을 확인해야 하기 때문에, 재귀와 DFS는 이를 단순화시키는데 유용합니다.
- 구현의 간결성: 재귀 함수를 사용하면 문제의 해결 방법을 명확하고 간결하게 표현할 수 있습니다. 재귀적 접근은 복잡한 반복문 사용을 피하고, 코드의 가독성을 향상시킬 수 있습니다.
이러한 이유로, 재귀와 DFS는 조합 문제, 순열 문제, 그리고 여러 상태를 탐색해야 하는 다양한 문제에서 자주 사용되는 기법입니다. 문제의 구조와 요구 사항을 분석한 후, 이러한 접근 방식이 효과적일 것이라고 판단되면 재귀 함수와 DFS를 사용하는 것이 좋습니다
OR
numbers = [2, 3, 1]
target_number = 0
result_count = 0 # target 을 달성할 수 있는 모든 방법의 수를 담기 위한 변수
def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
if current_index == len(array): # 탈출조건!
if current_sum == target:
global result_count
result_count += 1 # 마지막 다다랐을 때 합계를 추가해주면 됩니다.
return
get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
current_sum + array[current_index])
get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
current_sum - array[current_index])
get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0)
# current_index 와 current_sum 에 0, 0을 넣은 이유는 시작하는 총액이 0, 시작 인덱스도 0이니까 그렇습니다!
print(result_count) # 2가 반환됩니다!Note:
globalto access variable declared outside of the function within the function
Q9. 다음과 같이 숫자로 이루어진 배열이 두 개가 있다.
하나는 상품의 가격을 담은 배열이고, 하나는 쿠폰을 담은 배열이다.
쿠폰의 할인율에 따라 상품의 가격을 할인 받을 수 있다.
이 때, 최대한 할인을 많이 받는다면 얼마를 내야 하는가?
단, 할인쿠폰은 한 제품에 한 번씩만 적용 가능하다.
shop_prices = [30000, 2000, 1500000]
user_coupons = [20, 40]
def get_max_discounted_price(prices, coupons):
prices.sort(reverse=True)
coupons.sort(reverse=True)
idx = 0
current_sum = 0
while idx < len(coupons) and idx < len(prices):
current_sum += prices[idx] * ((100 - coupons[idx])/100)
idx += 1
while idx < len(prices):
current_sum += prices[idx]
idx += 1
return int(current_sum)
print("정답 = 926000 / 현재 풀이 값 = ", get_max_discounted_price([30000, 2000, 1500000], [20, 40]))
print("정답 = 485000 / 현재 풀이 값 = ", get_max_discounted_price([50000, 1500000], [10, 70, 30, 20]))
print("정답 = 1550000 / 현재 풀이 값 = ", get_max_discounted_price([50000, 1500000], []))
print("정답 = 1458000 / 현재 풀이 값 = ", get_max_discounted_price([20000, 100000, 1500000], [10, 10, 10]))Note:
list.sort(reverse = True)
Q9. 멜론에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 한다.
노래는 인덱스 구분하며, 노래를 수록하는 기준은 다음과 같다.
-
속한 노래가 많이 재생된 장르를 먼저 수록한다. (단, 각 장르에 속한 노래의재생 수 총합은 모두 다르다.)
-
장르 내에서 많이 재생된 노래를 먼저 수록한다.
-
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.
노래의 장르를 나타내는 문자열 배열 genres와
노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때,
베스트 앨범에 들어갈 노래의 인덱스를 순서대로 반환하시오.
def get_melon_best_album(genres, plays):
# 장르별 총 재생 수와 노래 정보를 저장할 딕셔너리 초기화
genre_play_dict = {}
song_info_dict = {}
for i, (genre, play) in enumerate(zip(genres, plays)):
# 장르별 총 재생 수 계산
if genre in genre_play_dict:
genre_play_dict[genre] += play
else:
genre_play_dict[genre] = play
# 노래 정보 저장
if genre in song_info_dict:
song_info_dict[genre].append((i, play))
else:
song_info_dict[genre] = [(i, play)]
# 장르별 총 재생수에 따라 장르 정렬
sorted_genres = sorted(genre_play_dict, key=lambda x: x[1], reverse=True)
best_album = []
for genre in sorted_genres:
# 각 장르 내에서 노래를 재생 수 내림차순으로 정렬(재생 수가 같다면 인덱스 오름차순)
sorted_songs = sorted(song_info_dict[genre], key=lambda x: (-x[1], x[0]))
print(sorted_songs)
# 각 장르에서 상위 2개의 노래 선택
song_indices = []
# Iterate over the first two tuples in the sorted_songs list
for song_index, _ in sorted_songs[:2]:
song_indices.append(song_index)
best_album.extend(song_indices)
# best_album.extend([song_index for _, song_index in sorted_songs[:2]])
return best_album
# 예제
genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]
print(get_melon_best_album(genres, plays)) # 정답 = [4, 1, 3, 0]Note:
for i, (genre, play) in enumerate(zip(genres, plays)):
if genre in song_info_dict: song_info_dict[genre].append((i, play)) else: song_info_dict[genre] = [(i, play)] _ {'classic': [(0, 500), (2, 150), (3, 800)], 'pop': [(1, 600), (4, 2500)]}
sorted_songs = sorted(song_info_dict[genre], key=lambda x: (-x[1], x[0]))Reverse ordering by - x[1] (play counts), and use x[0] if x[1] is equal (if play counts are the same, use the index for ordering)
songindex, play_counts (play_counts does not matter so )
for songindex, in sorted_songs[:2]:
song_indices.append(song_index)
