순차탐색
앞서 공부한 알고리즘을 구현하는 과정에서도 굉장히 빈번하게 사용한 탐색 방법이며, 굉장히 단순하다. 리스트 내의 특정 값을 찾기 위해 맨 앞부터 차례대로 확인하는 방법이다.
def sequential_search(n,target,array):
for i in range(n):
if array[i] == target:
return i+1
print("생성할 원소 개수를 입력한 다음 한 칸을 띄고 찾을 문자열을 입력하세요")
input_data = input().split()
n = int(input_data[0])
target = input_data[1]
print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()
print(sequential_search(n,target,array))이진탐색
배열 내부의 데이터가 정렬되어 있어여만 사용할 수 있다는 조건이 있다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정이다. 한 번 확인할 때마다 탐색해야 하는 원소의 개수가 절반씩 줄어든다는 점에서 O(logN)의 시간복잡도를 갖는다.
def binary_search(array,target,start,end):
if start > end:
return None
mid = (start+end)//2
if array[mid]>target:
binary_search(array,target,start,mid-1)
else:
binary_search(array,target,mid+1,end)
n,target = list(map(int,input().split()))
array = list(map(int,input().split()))
result = binary_search(array,target,0,n-1)
if result == None:
print("원소가 존재하지 않습니다.")
else:
print(result+1)예제 코드만 보면 굉장히 단순하다고 생각할 수 있지만, 정작 참고할 소스코드가 없는 실전 상황에서의 구현은 상당이 어려운 작업이라고 한다. 이진탐색은 코딩테스트에 있어 굉장히 중요한 알고리즘으로, 코드를 반복연습하여 암기하는 할 필요가 있다고 생각된다.
입력데이터가 많을 때, 한 줄 입력받아 출력하기
import sys
input_data = sys.stdin.readline().rstrip()
print(input_data)
