UPDOWN GAME
답을 맞춰볼 수 있는 기회를 7번 드리는데 숫자의 범위는 1~100 입니다! 7번 안에 맞춰야 된다면, 여러분은 어떻게 맞추실 건가요?
▶️ 첫 번째 방법 : 중간 숫자부터 시작하여 절반씩 깎아 나가는 것
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
def is_existing_target_number_binary(target, array):
current_min = 0
# array의 index 값이다.
current_max = len(array) -1
# array의 맨 뒤의 index 값이다.
current_guess = (current_min + current_max) // 2
# //는 나머 지값 없이 몫만 나오게 해준다. 역시 동일하게 index 값이다.
while current_min <= current_max:
if array[current_guess] == target:
return True
elif array[current_guess] < target:
current_min = current_guess + 1
# target 값이 추측한 값보다 크니까 최솟값을 크게 해주는 것!
else:
current_max = current_guess - 1
# target 값이 추측한 값보다 작으니까 최댓값을 작게 해주는 것 !
current_guess = (current_min + current_max) // 2
# 조건문을 빠져나오게 되면, 추측값을 새롭게 업데이트 해주는 것
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)True 반환
finding_target = 39
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
def is_existing_target_number_binary(target, array):
current_min = 0
# array의 index 값이다.
current_max = len(array) -1
# array의 맨 뒤의 index 값이다.
current_guess = (current_min + current_max) // 2
# //는 나머 지값 없이 몫만 나오게 해준다. 역시 동일하게 index 값이다.
while current_min <= current_max:
if array[current_guess] == target:
return True
elif array[current_guess] < target:
current_min = current_guess + 1
# target 값이 추측한 값보다 크니까 최솟값을 크게 해주는 것!
else:
current_max = current_guess - 1
# target 값이 추측한 값보다 작으니까 최댓값을 작게 해주는 것 !
current_guess = (current_min + current_max) // 2
# 조건문을 빠져나오게 되면, 추측값을 새롭게 업데이트 해주는 것
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)False 반환
* 시간 복잡도
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
def is_existing_target_number_binary(target, array):
current_min = 0
# array의 index 값이다.
current_max = len(array) -1
# array의 맨 뒤의 index 값이다.
current_guess = (current_min + current_max) // 2
# //는 나머 지값 없이 몫만 나오게 해준다. 역시 동일하게 index 값이다.
find_count = 0
while current_min <= current_max:
find_count += 1
if array[current_guess] == target:
print(find_count)
return True
elif array[current_guess] < target:
current_min = current_guess + 1
# target 값이 추측한 값보다 크니까 최솟값을 크게 해주는 것!
else:
current_max = current_guess - 1
# target 값이 추측한 값보다 작으니까 최댓값을 작게 해주는 것 !
current_guess = (current_min + current_max) // 2
# 조건문을 빠져나오게 되면, 추측값을 새롭게 업데이트 해주는 것
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)
# 3
# True
▶️ 두 번째 방법 : 배열 처음부터 하나씩 찾아 나가는 것
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
def is_existing_target_number_sequential(target, array):
find_count = 0
for number in array:
find_count += 1
if target == number:
print(find_count)
return True
return False
result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result) # 14 True처음부터 하나하나 찾아야하므로 오래 걸린다. 운이 안좋으면 O(N)만큼 걸린다.
Q) Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 2이 존재한다면 True 존재하지 않는다면 False 를 반환하시오.
[0, 3, 5, 6, 1, 2, 4]
이 배열로는 이진 탐색을 이용 할 수가 없다. 배열이 정렬되어있 지 않기 때문이다.
따라서 배열을 오름차순으로 정렬해준 다음에 이진 탐색을 해줘야하는 것이 이 문제의 핵심!
인데 이 부분은 뒷 쪽 강의에서 다뤄주신다고 하셨다!!
재귀 함수
자기 자신을 호출하는 함수이며, 간결하고 효율성 있는 코드를 작성할 수 있다.
def count_down(number):
print(number) # number를 출력하고
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다! 이 number -1 이 킥!
count_down(60)이렇게만 써주면 에러난다. 왜냐하면 끝도 없이 반복하게 되므로, 끝나는 시점을 정해주지 않았기 때문이다.
def count_down(number):
print(number) # number를 출력하고
if number == 0:
return
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다! 이 number -1 이 킥!
count_down(60)def count_down(number):
if number < 0:
return
print(number) # number를 출력하고
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다! 이 number -1 이 킥!
count_down(60)이렇게 if를 어디에 쓰느냐에 따라 조건이 달라짐을 유의하자!