모각코 4회차

• 탐색( 순차탐색, 이진탐색)

• DP 이코테 문제 풀이

---

순차 탐색: 앞에서부터 데이터를 하나씩 차례대로 확인하는 탐색 방법

def sequential_search(n, target, array):
	for i in range(n):
    	if array[i]== target:
        	return i+1 #현재 위치 반환(인덱스는 0부터 시작하므로 1 더하기)
print("원소개수와 찾고자 하는 문자열을 입력하세요 (ex: 5, hi)")
input_data = input().split()
n = int(input_data[0])
target = input_data[1]

print("원소 개수만큼 문자열을 입력하세요 (ex: hi, hello, bye, good, yeah"))
array = input().split()

# 원소의 인덱스 반환
print(sequential_search(n,target,array)

---

이진 탐색: 범위를 반씩 좁혀가는 탐색 방법

• 반복문 구현

# n , target
n,target = map(int,input().split()) #원소의 개수와 , 타겟 넘버
num = list(map(int,input().split())) #원소 리스트

ans=0
start = 0
end = len(num)-1
while(start<=end):
    print(start,end)
    mid = (start+end)//2
    ans+=1 					#이진탐색 수행 횟수 
    if num[mid] == target:
        print(ans)
        break
    else:
        if num[mid]>target:
            end = mid-1
        else:
            start= mid+1

• 재귀함수 구현

# n , target

n,target = map(int,input().split())
num = list(map(int,input().split()))
ans = 0

start = 0
end = len(num)-1
def binary_search(target,start,end):
    global ans
    mid = (start+end)//2
    ans+=1
    if start>end:
        return None
    elif num[mid] ==target:
        return ans
    else:
        if num[mid] > target:
            return binary_search(target,start,mid-1)
        else:
            return binary_search(target,mid+1,end)

print(binary_search(target,start,end))

---

• 여기서 return 으로 헷갈렸던 부분

return binary_search(target,start,mid-1) 으로 해줘야됐던걸 처음엔
binary_search(target,start,mid-1) 으로만 해줬는데 결과가 None으로 출력됐었다.

return을 통해 함수의 실행을 끝내고 새로운 binary_search 로 들어가야하는 것이였음.

---

이코테 DP 문제 풀이

개미전사

n = int(input())
num_list = list(map(int,input().split()))

dp=[0] * n
dp[0] = num_list[0]
dp[1] = max(num_list[0],num_list[1])

for i in range(2,n):
    dp[i] = max(dp[i-1],dp[i-2]+num_list[i])

print(dp[n-1])