알고리즘이란 어떤 문제를 해결하기 위해 정해 놓은 일련의 절차이다.
🔱선형 검색 linear search
선형으로 나열된 데이터를 맨 앞에서부터 순차적으로 스캔하면서 원하는 값을 찾는 방법이다.
numbers = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
searchNum = 8
searchIdx = -1
n = 0
while True:
# 검색 종료 조건 (1)
if n == len(numbers):
print(f'데이터가 리스트에 없습니다.')
break
# 검색 종료 조건 (2)
if numbers[n] == searchNum:
searchIdx = n
print(f'{searchNum}의 인덱스: {searchIdx}')
break
n += 1
>>>
8의 인덱스: 7보초법 sentinel method
앞의 방법은 검색 종료 조건문을 2번 거친다.
보초법을 이용하면 종료 조건을 1번만 확인하면 된다.
numbers = [4, 7, 10, 2, 4, 7, 0, 2, 7, 3, 9]
searchNum = 7
searchIdx = []
# 리스트의 맨 끝에 searchNum 추가
numbers.append(searchNum)
n = 0
while True:
if numbers[n] == searchNum:
if n != len(numbers) - 1:
searchIdx.append(n)
else:
break
n += 1
print(f'{searchNum}의 인덱스: {searchIdx} ({len(searchIdx)}개)')
>>>
7의 인덱스: [1, 5, 8] (3개)🔱이진 검색 Binary search
배열의 중앙값을 이용하여 데이터를 검색하는 방법으로,
데이터가 오름차순 또는 내림차순 정렬되어 있을 때 이용 가능하다.
스스로 코드를 짜보고 선생님의 방법과 비교해보면서,
어떤 변수가 필요한지 먼저 생각해볼 필요가 있다는 걸 알았다.
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
searchNum = 10
searchIdx = -1
staIdx = 0
endIdx = len(numbers) - 1
while True:
# 찾는 수가 없을 때
if searchNum < numbers[0] or searchNum > numbers[len(numbers) - 1]:
break
midIdx = (staIdx + endIdx) // 2
print(f'midIdx: {midIdx}, value: {numbers[midIdx]}')
if searchNum > numbers[midIdx]:
staIdx = midIdx + 1
elif searchNum < numbers[midIdx]:
endIdx = midIdx - 1
elif searchNum == numbers[midIdx]:
searchIdx = midIdx
break
print(f'{searchNum}의 인덱스: {searchIdx}')
>>>
midIdx: 5, value: 6
midIdx: 8, value: 9
midIdx: 9, value: 10
10의 인덱스: 9🔱순위 rank
수의 크고 작음을 이용해서 수의 순서를 정하는 것이다.
import random
numbers = random.sample(range(50), 10)
ranks = [0 for i in range(20)]
for idx, num1 in enumerate(numbers):
for num2 in numbers:
if num1 < num2:
ranks[idx] += 1
for idx, num in enumerate(numbers):
print(f'num: {num} \t rank: {ranks[idx]+1}')
>>>
num: 18 rank: 9
num: 31 rank: 4
num: 36 rank: 1
num: 25 rank: 7
num: 27 rank: 6
num: 34 rank: 3
num: 7 rank: 10
num: 28 rank: 5
num: 21 rank: 8
num: 35 rank: 2연습 문제
import random
def rank(scores):
ranks = [0 for i in range(len(scores))]
for idx, score1 in enumerate(scores):
for score2 in scores:
if score1 < score2:
ranks[idx] += 1
return ranks
midScores = random.sample(range(50, 101), 5)
endScores = random.sample(range(50, 101), 5)
print(f'mid: {midScores}')
print(f'end: {endScores}')
midRanks = rank(midScores)
endRanks = rank(endScores)
for idx, rank in enumerate(midRanks):
devication = rank - endRanks[idx]
if devication > 0:
devication = '▲ ' + str(abs(devication))
elif devication < 0:
devication = '▼ ' + str(abs(devication))
else:
devication = '-'
print(f'mid: {rank+1} \t end: {endRanks[idx]+1} [ {devication} ]')
>>>
mid: [92, 85, 95, 84, 54]
end: [81, 87, 84, 100, 55]
mid: 2 end: 4 [ ▼ 2 ]
mid: 3 end: 2 [ ▲ 1 ]
mid: 1 end: 3 [ ▼ 2 ]
mid: 4 end: 1 [ ▲ 3 ]
mid: 5 end: 5 [ - ]🔱버블 정렬 bubble sort
인접한 값을 순차적으로 비교하면서 "큰 숫자를 끝으로" 옮기는 방법이다.
import copy
def bubbleSort(list, deepCopy=True):
if deepCopy:
temp = copy.copy(list)
else:
temp = list
endIdx = len(temp) - 1
for i in range(endIdx):
# 한 턴 수행할 때마다 정렬할 대상이 줄어듦
for j in range(endIdx-i):
if temp[j] > temp[j+1]:
temp[j], temp[j+1] = temp[j+1], temp[j]
return temp
numbers = [2, 10, 7, 21, 0]
numbersSorted = bubbleSort(numbers)
print(f'not sorted: {numbers}')
print(f'sorted: {numbersSorted}')
>>>
not sorted: [2, 10, 7, 21, 0]
sorted: [0, 2, 7, 10, 21]2, 10, 7, 21, 0
i=0
2, 10, 7, 21, 0
2, 7, 10, 21, 0
2, 7, 10, 21, 0
2, 7, 10, 0, [21]
i=1
2, 7, 10, 0, [21]
2, 7, 10, 0, [21]
2, 7, 0, [10, 21]
i=2
2, 7, 0, [10, 21]
2, 0, [7, 10, 21]
i=3
0, [2, 7, 10, 21]이르게 정렬이 완료되면?
import copy
def bubbleSort(list, deepCopy=True):
if deepCopy:
temp = copy.copy(list)
else:
temp = list
endIdx = len(temp) - 1
for i in range(endIdx):
# 교환 횟수 카운트
exchange = 0
for j in range(endIdx-i):
if temp[j] > temp[j+1]:
temp[j], temp[j+1] = temp[j+1], temp[j]
exchange += 1
# 교환이 한 번도 이루어지지 않았다 = 이미 정렬되었다
if exchange == 0:
break
return temp
numbers = [1,3,6,4,7]
numbersSorted = bubbleSort(numbers)
print(f'not sorted: {numbers}')
print(f'sorted: {numbersSorted}')
>>>
not sorted: [1, 3, 6, 4, 7]
sorted: [1, 3, 4, 6, 7]🔱삽입 정렬 insertion sort
while문에서 temp를 기준으로 비교하면서 temp의 자리를 찾아간다.
numbers = [7, 5, 10, 2, 1, 0]
# 두 번째 숫자부터 비교 시작
for i in range(1,len(numbers)):
temp = numbers[i]
j = i
while numbers[j-1] > temp and j > 0:
numbers[j] = numbers[j-1]
j -= 1
numbers[j] = temp
print(f'sorted: {numbers}')
>>>
sorted: [0, 1, 2, 5, 7, 10]🔱선택 정렬 selection sort
순차적으로 작은 값을 찾아서 앞에 위치한 값과 자리를 바꾸는 방법이다.
numbers = [4, 2, 5, 1, 3]
for i in range(len(numbers)-1):
minIdx = i
for j in range(i+1, len(numbers)):
if numbers[minIdx] > numbers[j]:
minIdx = j
numbers[i], numbers[minIdx] = numbers[minIdx], numbers[i]
print(f'sorted: {numbers}')
>>>
sorted: [1, 2, 3, 4, 5]🚗 4주차 월요일이다. 시간이 빠르게 간다!
파이썬 과정의 마지막, 알고리즘이다.
얼핏 이해가 되는 것 같지만 제대로 이해하려면 몇 번 반복해야할 것 같다.
계속 붙잡고 있기 보다는 다른 것도 하다가 돌아오고, 그렇게 찬찬히 보려고 한다.
🚕 내일은 알고리즘 이론 강의를 마무리하고 문제 풀이에 들어갈 생각이다.
