선형검색

선형에서 데이터를 찾는다
문제를 풀어내기위한 일련의 절차 및 방법

datas = [3,2,5,7,9,1,0,8,6,4]
print(datas)
print(len((datas)))

searchData = int(input('숫자입력'))
searchDataIndex = -1

n = 0
while True :
    if n == len(datas) :
        searchDataIndex = -1
        break
    elif datas[n] == searchData :
        searchDataIndex = n
        break

    n += 1

print(searchDataIndex)

찾으려는 숫자 n을 리스트 끝에 넣어서

n을 찾긴 찾았는데 맨 끝의 값이 아니면 검색 성공으로 뽑고 아니면 검색 실패한걸로 뽑고

선형검색(실습)

nums = [4,7, 10, 2, 4, 7,0,2,7,3,9]

searchIndex = -1

search = int(input('찾으려는 숫자'))

n = 0

while True :
    if n == len(nums) :
        break
    if nums[n] == search :
        searchIndex = n
        break
    n += 1

print(searchIndex)

nums = [4,7,10,2,4,7,0,2,7,3,9]

searchN = int(input('찾으려는 숫자 입력'))
searchIndex = []

n = 0
while n<len(nums) :
    if n == len(nums):
        break
    elif nums[n] == searchN:
        searchIndex.append(n)
    n += 1
    continue

print(searchIndex)
print(len(searchIndex))

이진 검색

가운데 데이터를 이용한다
검색 범위 좁히기 위함임

data = [1,2,3,4,5,6,7,8,9,10,11]
print(data)
print(len(data))

searchData = int(input('찾으려는 데이터'))
searchDataIndex = -1

startIndex = 0
endIndex = len(data)-1
midIndex = (startIndex+endIndex)//2
midValue = data[midIndex]
print(midIndex)
print(midValue)

while searchData <= data[len(data)-1] and searchData >= data[0] :
    if searchData == data[len(data)-1] :
        startIndex = len(data)-1
        break

    if searchData < midValue :
        endIndex = midIndex
        midIndex = (startIndex+endIndex)//2
        midValue = data[midIndex]
        print(f"midIndex : {midIndex}")
        print(f"midValue : {midValue}")
    if searchData > midValue :
        startIndex = midIndex
        midIndex = (startIndex+endIndex)//2
        midValue = data[midIndex]
        print(f"midIndex : {midIndex}")
        print(f"midValue : {midValue}")
    elif searchData == data[midIndex] :
        searchDataIndex = midIndex
        break

print(searchDataIndex)

이진검색(실습)

nums = [4,10,22,5,0,17,7,11,9,61,88]
nums.sort()

searchVaule = int(input('찾으려는 값 입력'))
searchIndex = -1

startIndex = 0
endIndex = len(nums)-1
midIndex = (startIndex+endIndex)//2
midValue = nums[midIndex]
print(f'midValue : {midValue}')
print(f'midIndex : {midIndex}')

while searchVaule <= nums[len(nums)-1] and searchVaule >= nums[0] :
    if searchVaule ==  nums[len(nums)-1] :
        searchIndex = len(nums)-1
        break
    if searchVaule > midValue :
        startIndex = midIndex
        midIndex = (startIndex + endIndex)//2
        midValue = nums[midIndex]
        print(f'midIndex : {midIndex} / midValue : {midValue}')
    elif searchVaule < midValue :
        endIndex = midIndex
        midIndex = (startIndex + endIndex)//2
        midValue = nums[midIndex]
        print(f'midIndex : {midIndex} / midValue : {midValue}')

    elif searchVaule == midValue :
        searchIndex = midIndex
        break

print(f'searchIndex : {searchIndex}')

순위

import  random

nums = random.sample(range(10,101), 20)
ranks = [0 for i in range (20)]
print(nums)
print(ranks)

for index, nums1 in enumerate(nums) :
    for num2 in nums :
        if nums1 < num2 :
            ranks[index] += 1

print(nums)
print(ranks)

for idx, num in enumerate(nums) :
    print(f'num : {num} \t rank : {ranks[idx]+1}')

순위(실습)

import  random

nums = random.sample(range(10,101), 20)
ranks = [0 for i in range (20)]
print(nums)
print(ranks)

for index, nums1 in enumerate(nums) :
    for num2 in nums :
        if nums1 < num2 :
            ranks[index] += 1

print(nums)
print(ranks)

for idx, num in enumerate(nums) :
    print(f'num : {num} \t rank : {ranks[idx]+1}')

import  random

midScore = random.sample(range(0,100),20)
midRank = [0 for i in range(20)]
endScore = random.sample(range(0,100),20)
endRank = [0 for i in range(20)]

print(midScore)
print(midRank)
print(endScore)
print(endRank)

for idx, num1 in enumerate(midScore) :
    for num2 in midScore:
        if num1 < num2 :
            midRank[idx] += 1
for idx, num1 in enumerate(endScore) :
    for num2 in endScore:
        if num1 < num2 :
            endRank[idx] += 1

for i in range(20):
    print(f'midRank : {midRank[i]} \t endRank : {endRank[i]} \t deviation : {midRank[i]-endRank[i]}')

버블정렬

처음부터 끝까지 차례로 비교하자

nums = [10,2,7,21,0]
print(f'not sorted nums = {nums}')

length = len(nums)-1
for i in range(length) :
    for j in range(length-i):
        if nums[j]>nums[j+1]:
            temp = nums[j]
            nums[j], nums[j+1] = nums[j+1], nums[j]
        print(nums)
    print()

print(f'sorted nums = {nums}')

버블정렬(실습)

import random
studentHight = random.sample(range(170,186), 20)

length = len(studentHight)-1
for i in range(length):
    for j in range(length-i):
        if studentHight[j] >studentHight[j+1]:
            studentHight[j], studentHight[j + 1] = studentHight[j+1], studentHight[j]
    print(studentHight)
print()

print(f'sorted student hight : {studentHight}')

삽입정렬

정렬 위치를 찾아 들어가자!

이미 앞에 있는게 정렬되어있다는 가정 하에 정렬

lis = [6,8,2,5,4]
print(f'정렬 전 리스트 : {lis}')

for i in range(1, len(lis)):
    for j in range (i,0,-1):
        if lis[j-1] > lis[j]:
            lis[j-1], lis[j] = lis[j], lis[j-1]
print(f'정렬 후 리스트 : {lis}')

삽입정렬(실습)

문제: 주어진 리스트를 삽입 정렬 알고리즘을 사용하여 내림차순으로 정렬하고, 정렬된 리스트를 반환하는 함수를 작성하세요.

함수 시그니처: def insertion_sort_descending(lst: List[int]) -> List[int]

예시 입력: [5, 2, 8, 1, 9, 3]
예시 출력: [9, 8, 5, 3, 2, 1]

def insertion_sort_descending(lst) :
    for i in range(1, len(lst)) :
        key = lst[i]
        j = i-1
        while j >=0 and lst[j] < key :
            lst[j+1]=lst[j]
            j -= 1
            lst[j+1]=key
    return lst
lst = [5, 2, 8, 1, 9, 3]

result = insertion_sort_descending(lst)
print(result)

어렵다!

선택정렬

nums = [4,2,5,1,3]

for i in range(len(nums)-1) :
    minindex = i
    for j in range(i+1,len(nums)):
        if nums[minindex] > nums[j]:
            minindex =j
    tempNum = nums[i]
    nums[i] = nums[minindex]
    nums[minindex] = tempNum

print(nums)

선택정렬(실습)

import random

class Selection_sort :
    def __init__(self):
        self.score_List = self.student_score()
    def student_score(self):
        score_List = random.sample(range(50,101),20)
        return score_List

    def score_list_ASC(self):
        for i in range(len(self.score_List)-1) :
            min_index = i
            for j in range(i+1, len(self.score_List)):
                if self.score_List[j] < self.score_List[min_index]:
                    min_index = j
            self.score_List[i], self.score_List[min_index] = self.score_List[min_index], self.score_List[i]
        return self.score_List

    def score_list_DSC(self):
        for i in range(len(self.score_List)-1) :
            max_index = i
            for j in range(i+1, len(self.score_List)):
                if self.score_List[j] > self.score_List[max_index]:
                    max_index = j
            self.score_List[i], self.score_List[max_index] = self.score_List[max_index], self.score_List[i]

        return self.score_List

test = Selection_sort()
list = test.student_score()
print(list)
asc = test.score_list_ASC()
print(f'asc : {asc}')
dsc = test.score_list_DSC()
print(f'dsc : {dsc}')

from test import Selection_sort

lst = Selection_sort.student_score()
print(lst)
print(len(lst))

lst_asc = Selection_sort.score_list_ASC()
print(f'lst_asc : {lst_asc}')
lst_dsc = Selection_sort.score_list_DSC()
print(f'lst_dsc : {lst_dsc}')

최댓값

class MaxAlgorithm :
    def __init__(self,nums):
        self.nums = nums
        self.maxNum = maxNum = 0

    def getMaxNum(self):
        maxNum = self.nums[0]

        for n in self.nums :
            if self.maxNum < n :
                self.maxNum = n
        return self.maxNum

lst = [-2, -4, 5,7,10,0,8,20,-11]
mn = MaxAlgorithm(lst)
result = mn.getMaxNum()
print(result)

여기서

def getMaxNum(self):
maxNum = self.nums[0]

max num을 첫번째 값으로 꼭 해야하나? 궁금했는데

self.maxNum = maxNum = 0만 하게되면
self.maxNum 변수만 선언하고 초기화하지 않는거고,

저 방법을 통해서 maxNum 변수를 self.nums 리스트의 첫 번째 요소로 초기화하면 첫 번째 요소가 현재까지의 최댓값으로 설정되므로, 이후 반복문에서 비교하는 것이 더 직관적이라고 함

최댓값(실습)

class MaxAlgorithm :
    def __init__(self, characters):
        self.characters = characters
        self.max_Char = max_Char = 0
    def find_max_Char(self):
        self.max_Char = self.characters[0]

        for n in self.characters :
            if ord(self.max_Char) < ord(n) :
                self.max_Char = n
        return self.max_Char



characters = ['c','x','Q','A','e','P','p']
mc = MaxAlgorithm(characters)
result = mc.find_max_Char()
print(result)

ord함수는 아스키코드 유니코드로 변경해주는 함수!

최솟값

class MinAlgorithm :
    def __init__(self, lst):
        self.lst = lst
        self.min_Value = min_Value = 0

    def find_min_value(self):
        self.min_Value = self.lst[0]

        for n in self.lst:
            if n < self.min_Value:
                self.min_Value = n
        return self.min_Value


lst = [-2,-4,5,7,10,0,8,20,-11]
test = MinAlgorithm(lst)
result =  test.find_min_value()
print(result)

최솟값(실습)

class MinAlgorithm :
    def __init__(self, lst):
        self.lst = lst
        self.min_value = self.lst[0]

    def find_min_value(self):
        for n in self.lst:
            if ord(self.min_value) > ord(n):
                self.min_value = n
        return self.min_value

lst = ['c','x','Q','A','e','P','p']
test = MinAlgorithm(lst)
result = test.find_min_value()
print(result)

최빈값

class MaxAlgorithm :
    def __init__(self,nums):
        self.nums = nums
        self.maxNum = maxNum = 0

    def getMaxNum(self):
        maxNum = self.nums[0]

        for n in self.nums :
            if self.maxNum < n :
                self.maxNum = n
        return self.maxNum

lst = [1,3,7,6,7,7,7,12,12,17]
mn = MaxAlgorithm(lst)
maxNum = mn.getMaxNum()
indexes = [0 for i in range(maxNum+1)]

for n in lst:
    indexes[n] += 1
print(indexes)

최빈값(실습)

import random
class modeAlgorithm :
    def __init__(self, lst,):
        self.lst = lst
        self.max_value = self.lst[0]
    def find_max_value(self):
        for n in self.lst :
            if self.max_value < n:
                self.max_value = n
        return  self.max_value
    def mode_list(self):
        index_list = [0]*(self.max_value+1)
        for n in self.lst:
            index_list[n] += 1
        return index_list

lst = []
for i in range(100) :
    rn = random.randint(70,100)
    if rn != 100 : rn = rn -(rn%5)
    lst.append(rn)

test = modeAlgorithm(lst)
max_value = test.find_max_value()
result = test.mode_list()

scoreDic = {}
for i in range(len(result)):
    if result[i]![](https://velog.velcdn.com/images/softwater/post/294fc070-045f-4a62-b690-4c249604c8e2/image.png)
![](https://velog.velcdn.com/images/softwater/post/186dad50-902b-4c43-a136-d563ac80d05a/image.png)
 != 0 :
        scoreDic[i] = result[i]

scoreList = list( scoreDic.keys())
countList =list( scoreDic.values())

for i in range(len(scoreDic)):
    score =int(scoreList[i])
    count =int(countList[i])
    show = count * '+'
    print(f'{i+1}.\t{score}점 빈도 수:\t{count}\t{show}')