728x90
반응형
Today I Learned
어떤 문제가 있었는지
재귀함수에 대한 개념적 이해는 됐지만 직관적으로 풀기는 쉽지 않음을 느낌
내가 시도해 본 것들
# numbers의 요소들을 더하거나 빼서 target_number로 만드는 방법의 갯수를 return
numbers = [1, 1, 1, 1, 1]
target_number = 3
def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target):
pass
# 5를 반환 해야 합니다!
print(get_count_of_ways_to_target_by_doing_plus_or_minus(numbers,target_number))처음에는 array와 target 만 주어지고 어떻게 푸나 했다..
함수의 모양을 안바꾸고 풀 수 있나 이것저것 해봄
하필이면 이문제가 재귀함수 문제라 가능하면 재귀함수로 풀고싶었는데 도저히 방법이 생각이 안남
그래서 일단 그냥 풀어봄
def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target):
arr =[]
idx = 0
count = 0
# while문이 돌면 idx가 1씩 추가됨
while idx < len(array):
# idx가 0이면 최초의 수 넣어주고
if idx == 0:
arr.append(array[idx])
arr.append(-array[idx])
# idx가 len(array)-1 이면 target과 비교 후 같으면 count+1
elif idx == len(array)-1 :
for i in arr:
if i+array[idx] == target or i-array[idx] == target:
count+=1
# 1<idx<len(array)-2 이면 arr 플마 array[idx] 해주고
else:
for i in arr[:]:
arr.append(i+array[idx])
arr.append(i-array[idx])
# array[idx] 값 추가 해주기 이전 arr값 정리
arr = arr[2**idx:]
idx+=1
return count조금 노가다 하면 일단 풀수는 있다.
근데 아무리봐도 재귀함수 문제를 이렇게 푸는것은 문제가 있다
무려 O(2**n)짜리 성능이라고..
어떻게 해결 했는지
일단 문제를 풀었으니 답을 확인해봤는데
또 오기생겨서 코드 한줄한줄씩만 먼저 봤다 힌트만 얻고 풀어보려고..
그런데 이게 웬걸
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):
pass
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)답지의 함수 / 파라메터 / 변수가 다르다..
이거 너무 억울해..
물론 답을 내긴 했는데 첨부터 이렇게 나왔으면
재귀함수로 만들 수 있었는데 ㅠㅠㅠㅠㅠㅠㅠ
numbers = [1, 1, 1, 1, 1]
target_number = 3
count = 0
def get_count(array, target, list_sum=0, idx=0):
if idx == len(array):
if list_sum == target:
global count
count +=1
return
get_count(array, target, list_sum + numbers[idx], idx + 1)
get_count(array, target, list_sum - numbers[idx], idx + 1
print(get_count(numbers, target_number))결국 위 형식과 같게 문제 재귀함수로 풀어서 제출함..
무엇을 새롭게 배웠는지
재귀함수의 사용방법 및 활용방법에 크게 고민했던 문제다
재귀함수는 확실히 장점이 있다 변수선언에서 좀 편리한것도 많고..
조만간 자세하게 다뤄봐야 할 듯
알고리즘 강의을 들으면서 아직 나는 코딩초보라는것을 깨닫는 중..
처음봤을때 100% 이해하긴 힘들지만 그래도 70-80%까진 이해하려하는데
그것만으로도 생각보다 시간이 더 많이 걸린다. 예상했던것보다 2-3배?
728x90
반응형
