제로베이스 데이터 파트타임 스쿨 학습 일지 [25.04.30]
[강의 요약]
[Part 03. 자료구조&알고리즘 with Python_ Ch 03. 알고리즘] 강의 수강
01_선형 검색부터 04_이진 검색(실습)까지 강의 수강하였음
🐢 100일 챌린지 🔥 : [▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰░ ] 45/100일 (45%)
[01_선형 검색]
▶ 선형 검색이란?
데이터를 선형(순서대로 나열) 한 상태에서 처음부터 끝가지 차례로 비교하여 원하는 값을 찾는 방식임
아래처럼 나열되어 있는 데이터가 있으면, 인덱스 0부터 9까지 순차적으로 검색한다는 것
[3, 2, 5, 7, 9, 1, 0, 8, 6, 4]숫자 7을 찾고 싶으면
3, 2, 5를 거쳐서 7을 찾는 것
결과는 검색 성공 or 검색 실패임
일일이 하나씩 순서대로 찾아보는 방식으로 간단하지만, 데이터가 많으면 느림
▶ 코드 : 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값 찾기
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
n = 0
while True:
if n == len(datas): # 끝까지 다 확인했는데 못 찾은 경우
searchResultIdx = -1
break
elif datas[n] == searchData:
searchResultIdx = n
break
n += 1
print(f'searchResultIdx: [{searchResultIdx}]')[출력 결과]
찾으려는 숫자 입력: 7
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
datas length: 10
searchResultIdx: [3]
▶ 보초법이란?
데이터를 검색할 때 검색 종료 조건을 단순화하기 위해 검색값을 리스트 끝에 임시로 추가
마지막에 검색값이 도달하면 → 원래 리스트에 없는 값이라는 의미
성공 : 검색값이 리스트 중간에 존재
실패 : 검색값이 맨 마지막 인덱스에서 발견됨
검색을 좀 더 편하고 안전하게 만드는 방법임
마지막에 무조건 찾게 되므로 끝가지 못 찾았는지 매번 체크할 필요가 없음
▶ 코드 : 보초법 적용한 선형 검색
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
datas.append(searchData) # 보초값 추가
n = 0
while True:
if datas[n] == searchData:
if n != len(datas) - 1: # 마지막이 아니라면 찾은 것
searchResultIdx = n
break
n += 1
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
print(f'searchResultIdx: [{searchResultIdx}]')[출력 결과 (존재하는 숫자)]
찾으려는 숫자 입력: 7
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 7]
datas length: 11
searchResultIdx: [3][출력 결과 (존재하지 않는 숫자)]
찾으려는 숫자 입력: 100
datas: [3, 2, 5, 7, 9, 1, 0, 8, 6, 4, 100]
datas length: 11
searchResultIdx: [-1]
[02_선형 검색(실습)]
▶ 실습 코드 : 숫자 1개만 찾기 (처음 등장 위치)
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
nums.append(searchData) # 보초 추가
n = 0
while True:
if nums[n] == searchData:
if n != len(nums) - 1: # 보초값이 아닌 경우
searchResultIdx = n
break
n += 1
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
print(f'searchResultIdx: [{searchResultIdx}]')
if searchResultIdx < 0:
print(f'찾으려는 {searchData}가(이) 없습니다.')
else:
print(f'찾으려는 {searchData}의 위치(인덱스)는 {searchResultIdx}입니다.')[출력 결과 (존재하는 숫자)]
찾으려는 숫자 입력: 7
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 7]
nums length: 12
searchResultIdx: [1]
찾으려는 7의 위치(인덱스)는 1입니다.[출력 결과 (존재하지 않는 숫자)]
찾으려는 숫자 입력: 100
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 100]
nums length: 12
searchResultIdx: [-1]
찾으려는 100가(이) 없습니다.
▶ 실습 코드 : 숫자 여러 개 찾기 (모든 인덱스 + 개수)
nums = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdxs = []
nums.append(searchData) # 보초 추가
n = 0
while True:
if nums[n] == searchData:
if n != len(nums) - 1:
searchResultIdxs.append(n)
else:
break
n += 1
print(f'nums: {nums}')
print(f'nums length: {len(nums)}')
print(f'searchResultIdxs: {searchResultIdxs}')
print(f'searchResultCnts: {len(searchResultIdxs)}')[출력 결과 (존재하는 숫자)]
찾으려는 숫자 입력: 7
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 7]
nums length: 12
searchResultIdxs: [1, 5, 8]
searchResultCnts: 3[출력 결과 (존재하지 않는 숫자)]
찾으려는 숫자 입력: 100
nums: [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9, 100]
nums length: 12
searchResultIdxs: []
searchResultCnts: 0
[03_이진 검색]
▶ 이진 검색이란?
절반씩 줄여가며 찾는 검색 방법임
정렬된 데이터를 전제로, 가운데 값을 기준으로 크고 작음을 비교하며 탐색 범위를 절반으로 줄이는 방식
[1, 2, 3, 4, 5, 6, 7, 8, 9]이런 리스트가 있고 숫자 2를 찾고 싶으면
중앙값 5와 비교 → 2 < 5 → 왼쪽으로 이동
다시 중앙값 3과 비교 → 2<3 → 또 왼쪽으로 이동
중앙값 2 → 찾음!
이런식으로 매번 범위를 반씩 줄이면서 비교하는 것이 이진 검색
장점은 선형 검색보다 빠름(시간복잡도 O(log n))
단점은 데이터가 정렬되어 있어야만 동작함
▶ 코드
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
# datas = [1, 3, 4, 6, 7, 8, 9, 11] # 정렬만 되어 있다면 이진 검색 가능
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
staIdx = 0
endIdx = len(datas) - 1
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')
while searchData <= datas[endIdx] and searchData >= datas[staIdx]:
if searchData == datas[endIdx]:
searchResultIdx = endIdx
break
if searchData > midVal:
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')
elif searchData < midVal:
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')
elif searchData == midVal:
searchResultIdx = midIdx
break
print(f'searchResultIdx: [{searchResultIdx}]')[출력 결과 (존재하는 숫자)]
찾으려는 숫자 입력: 9
datas: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
datas length: 11
midIdx: 5
midVal: 6
midIdx: 8
midVal: 9
searchResultIdx: [8][출력 결과 (존재하지 않는 숫자)]
찾으려는 숫자 입력: 100
datas: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
datas length: 11
midIdx: 5
midVal: 6
midIdx: 8
midVal: 9
midIdx: 9
midVal: 10
midIdx: 10
midVal: 11
searchResultIdx: [-1]
[04_이진 검색(실습)]
▶ 코드
nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
print(f'nums: {nums}')
nums.sort() # 이진 검색 전 정렬 필수
print(f'nums: {nums}')
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
staIdx = 0
endIdx = len(nums) - 1
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
while searchData <= nums[endIdx] and searchData >= nums[staIdx]:
if searchData == nums[endIdx]:
searchResultIdx = endIdx
break
if searchData > midVal:
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')
elif searchData < midVal:
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')
elif searchData == midVal:
searchResultIdx = midIdx
break
print(f'searchResultIdx: [{searchResultIdx}]')[출력 결과 (존재하는 숫자)]
nums: [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
찾으려는 숫자 입력: 7
midIdx: 5
midVal: 10
midIdx: 2
midVal: 5
midIdx: 3
midVal: 7
searchResultIdx: [3][출력 결과 (존재하지 않는 숫자)]
nums: [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]
nums: [0, 4, 5, 7, 9, 10, 11, 17, 22, 61, 88]
찾으려는 숫자 입력: 100
searchResultIdx: [-1]
[나의 생각 정리]
선형 검색, 이진 검색 전부 코테 문제를 풀 때 사용해 봤다.
데이터가 많은 경우 선형 검색으로는 시간초과가 되는 경우가 꽤 있었고
그럴 때는 이진검색을 사용해서 시간복잡도를 맞추는 방법을 사용했다.
다만 이진 검색은 인덱스 관리가 조금 더 복잡해서 신경을 써야 한다.
[적용점]
코딩 테스트 문제 풀 때 적용 가능
데이터 양에 따라 유연하게 선택해서 코드를 작성하면 좋을 것 같다.
“이 글은 제로베이스 데이터 스쿨 주 3일반 강의 자료 일부를 발췌하여 작성되었습니다.”