제로베이스 데이터취업스쿨 DAY16 알고리즘문제풀이1~4

검색 알고리즘

1. 선형검색

def searchNumByLineAlgorithm(ns, sn):

    searchResultIdx = -1

    print(f'Numbers : {ns}')
    print(f'searchNum : {sn}')

    n = 0
    while True:

        if n == len(ns):
            print('Search FAIL!!')
            break

        if ns[n] == sn:
            searchResultIdx = n
            print('Search SUCCESS!!')
            break

        n += 1

    return searchResultIdx

import lineMod
import random

if __name__ == '__main__':
    rNums = random.sample(range(1,21), 10)
    searchNum = int(input('찾으려는 숫자: '))

    resultIdx = lineMod.searchNumByLineAlgorithm(rNums, searchNum)

if resultIdx == -1:
    print('서치 실패~~!!')
else:
    print(f'{resultIdx} index에 위치')

2. 이진검색

def searchNumByBinaryAlgorithm(ns, sn):

    searchResultIdx = -1
    sIdx = 0
    eIdx = len(ns) - 1
    mIdx = (sIdx + eIdx) // 2
    mVal = ns[mIdx]

    while sn >= ns[0] and sn < ns[eIdx]:
        if sn ==  ns[eIdx]:
            searchResultIdx = eIdx
            break

        if sIdx+1 == eIdx:
            if ns[sIdx] != sn and ns[eIdx] != sn:
                print('찾으려는 숫자가 없습니다.')
                break
                
        if sn > mVal:
            sIdx = mIdx
            mIdx = (sIdx + eIdx) // 2
            mVal = ns[mIdx]

        if sn < mVal:
            eIdx = mIdx
            mIdx = (sIdx + eIdx) // 2
            mVal = ns[mIdx]

        if sn == mVal:
            searchResultIdx = mIdx
            break

    return searchResultIdx

import binaryMod

if __name__ == '__main__':

    nums = [1,2,4,6,7,8,10,11,13,15,16,17,20,21,23,24,27,28]
    searchNum = int(input('찾으려는 숫자: '))

    resultIdx = binaryMod.searchNumByBinaryAlgorithm(nums, searchNum)

if resultIdx == -1:
    print('서치 실패~~!!')
else:
    print(f'{resultIdx} index에 위치')

순위 알고리즘

1. 순위

def rankAlgorithm(ns):
    ranks = [0 for i in range(20)]

    for idx, num1 in enumerate(ns):
        for num2 in ns:
            if num1 < num2:
                ranks[idx] += 1

    print(ns)
    print(ranks)

    for i, n in enumerate(ns):
        print(f'num:{n}\trank:{ranks[i]+1}')

    sortedNums = [0 for n in range(len(ns))]

    for idx, rank in enumerate(ranks):
        sortedNums[rank] = ns[idx]

    return sortedNums

import random
import rankMod

if __name__ == '__main__':

    nums = random.sample(range(50, 101), 20)
    sNums = rankMod.rankAlgorithm(nums)

    print(sNums)

정렬 알고리즘

1. 버블정렬

import copy

def bubbleModAlgorithm(ns, asc=True):

    c_ns = copy.copy(ns)
    length = len(c_ns) - 1

    if asc:
        for i in range(length):
            for j in range(length - i):
                if c_ns[j] > c_ns[j+1]:
                    c_ns[j], c_ns[j+1] = c_ns[j+1], c_ns[j]
    else:
        for i in range(length):
            for j in range(length - i):
                if c_ns[j] < c_ns[j+1]:
                    c_ns[j], c_ns[j+1] = c_ns[j+1], c_ns[j]

    return c_ns

import bubbleMod

if __name__ == '__main__':
    nums = [10,4,1,13,11,16,19,14,6,5]

    sortNumsAsc = bubbleMod.bubbleModAlgorithm(nums)
    sortNumsDesc= bubbleMod.bubbleModAlgorithm(nums, asc=False)
    print(sortNumsAsc)
    print(sortNumsDesc)

2. 삽입정렬

import copy

def insertModAlgorithm(ns):
    c_ns = copy.copy(ns)

    for i1 in range(1, len(c_ns)):
        i2 = i1 - 1
        cNum = c_ns[i1]

        while c_ns[i2] > cNum and i2 >= 0:
            c_ns[i2+1] = c_ns[i2]
            i2 -= 1
        c_ns[i2 + 1] = cNum

    return c_ns

3. 선택정렬

import copy

def selectModAlgorithm(ns):
    c_ns = copy.copy(ns)

    for i in range(len(c_ns)-1):
        minIdx = i

        for j in range(i+1, len(c_ns)):
            if c_ns[minIdx] > c_ns[j]:
                minIdx = j

        c_ns[i], c_ns[minIdx] = c_ns[minIdx], c_ns[i]

    return c_ns

4. 병합정렬

import copy

def mSort(ns):
    c_ns = copy.copy(ns)

    if len(c_ns) < 2:
        return c_ns

    midIdx = len(c_ns) // 2
    leftNums = mSort(c_ns[0:midIdx])
    rightNums = mSort(c_ns[midIdx:len(c_ns)])

    mergeNums = []
    leftIdx = 0; rightIdx = 0

    while leftIdx < len(leftNums) and rightIdx < len(rightNums):
        if leftNums[leftIdx] < rightNums[rightIdx]:
            mergeNums.append(leftNums[leftIdx])
            leftIdx += 1
        else:
            mergeNums.append(rightNums[rightIdx])
            rightIdx += 1

    mergeNums += leftNums[leftIdx:]
    mergeNums += rightNums[rightIdx:]

    return mergeNums

최댓값 알고리즘

1. 최댓값, 최댓값 개수

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0
        self.maxNumCnt = 0

    def setMaxNum(self):
        self.maxNum = 0

        for n in self.nums:
            if n > self.maxNum:
                self.maxNum = n

    def getMaxNum(self):
        self.setMaxNum()
        return self.maxNum

    def setMaxNumCnt(self):
        self.setMaxNum()

        for n in self.nums:
            if self.maxNum == n:
                self.maxNumCnt += 1

    def getMaxNumCnt(self):
        self.setMaxNumCnt()
        return self.maxNumCnt

import maxMod
import random

if __name__ == '__main__':
    nums = []
    for n in range(30):
        nums.append(random.randint(1, 50))
    print(nums)

    ma = maxMod.MaxAlgorithm(nums)
    print(ma.getMaxNum())
    print(ma.getMaxNumCnt())

2. 로또번호 빈도수

class LottoMode:

    def __init__(self, ln):
        self.lottoNums = ln
        self.modeList = [0 for n in range(1, 47)]

    def getLottoNumMode(self):

        for roundNums in self.lottoNums:
            for num in roundNums:
                self.modeList[num] += 1

        return self.modeList

    def printModList(self):
        if sum(self.modeList) == 0:
            return None

        for idx, m in enumerate(self.modeList):
            if idx !=0:
                print(f'번호:{idx}\t {m}번\t\t\t{"* " * m}')

import random
import mod

lottoNumsList = []
for i in range(30):
    lottoNums = random.sample(range(1,46), 6)
    lottoNumsList.append(lottoNums)

lm = mod.LottoMode(lottoNumsList)
lm.getLottoNumMode()
lm.printModList()

최솟값 알고리즘

1. 최솟값, 최솟값 개수

class MinAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.minNum = 0
        self.minNumCnt = 0

    def setMinNum(self):
        self.minNum = 100

        for n in self.nums:
            if n < self.minNum:
                self.minNum = n

    def getMinNum(self):
        self.setMinNum()
        return self.minNum

    def setMinNumCnt(self):
        self.setMinNum()

        for n in self.nums:
            if self.minNum == n:
                self.minNumCnt += 1

    def getMinNumCnt(self):
        self.setMinNumCnt()
        return self.minNumCnt

최빈값 알고리즘

1. 가장 많은 빈도수의 나이

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0
        self.maxNumIdx = 0

    def setMaxIdxAndNum(self):
        self.maxNum = 0
        self.maxNumIdx = 0

        for i, n in enumerate(self.nums):
            if n > self.maxNum:
                self.maxNum = n
                self.maxNumIdx = i

    def getMaxNum(self):
        return self.maxNum

    def getMaxIdx(self):
        return self.maxNumIdx

import maxMod

class ModeAlogorithm:

    def __init__(self, ns, mn):
        self.nums = ns
        self.maxNum = mn
        self.indexes = []

    def setIndexList(self):
        self.indexes = [0 for i in range(self.maxNum + 1)]

        for n in self.nums:
            self.indexes[n] += 1

    def getIndexList(self):
        if sum(self.indexes) == 0:
            return None
        else:
            return self.indexes

    def printAges(self):

        n = 1
        while True:
            maxAlo = maxMod.MaxAlgorithm(self.indexes)
            maxAlo.setMaxIdxAndNum()
            maxNum = maxAlo.getMaxNum()
            maxNumIdx = maxAlo.getMaxIdx()

            if maxNum == 0:
                break

            print(f'{n:0>3} {maxNumIdx} 빈도수 : {maxNum}\t\t', end='')
            print('* ' * maxNum)
            self.indexes[maxNumIdx] = 0

            n+=1

import modeMod
import maxMod
ages = [25,27,27,24,31,34,33,31,29,25,
        45,37,38,46,47,22,24,29,33,35,
        27,34,37,40,42,29,27,25,26,27,
        31,31,32,38,25,27,28,40,41,34]

print(f'총 {len(ages)}명')
companyNums = maxMod.MaxAlgorithm(ages)
companyNums.setMaxIdxAndNum()
maxAge = companyNums.getMaxNum()
maxAgeIdx = companyNums.getMaxIdx()
print(f'가장 많은 나이 : {maxAge}')
print(f'가장 많은 나이 인덱스 : {maxAgeIdx}')

modAlo = modeMod.ModeAlogorithm(ages, maxAge)
modAlo.setIndexList()
print(modAlo.getIndexList())
print(modAlo.printAges())

근삿값 알고리즘

1. 깊이에 따른 수온

class NearAlogorithm:

    def __init__(self, d):
        self.temps = {0:24, 5:22, 10:20, 15:26, 20:13, 25:10, 30:6}
        self.depth = d
        self.nearNum = 0
        self.minNum = 24

    def getNearNum(self):

        for n in self.temps.keys():
            absNum = abs(n - self.depth)
            if absNum < self.minNum:
                self.minNum = absNum
                self.nearNum = n

        return self.temps[self.nearNum]

import nearMod

depth = int(input('depth : '))
print(f'{depth}m')

na = nearMod.NearAlogorithm(depth)
temp = na.getNearNum()
print(f'{temp}도')

2. BMI

class BmiNearAlgorithm:

    def __init__(self, b):
        self.bmiSection = {18.5:['저체중', '정상'],
                           23:['정상', '과체중'],
                           25:['과제충', '비만']}
        self.bmi = b
        self.condition = ''
        self.nearNum = 0
        self.minNum = 25

    def getCondition(self):

        for n in self.bmiSection.keys():
            absNum = abs(n - self.bmi)
            if absNum < self.minNum:
                self.minNum = absNum
                self.nearNum = n

        print(self.nearNum)

        if self.bmi <= self.nearNum:
            self.condition = self.bmiSection[self.nearNum][0]
        else:
            self.condition = self.bmiSection[self.nearNum][1]

        return self.condition

import  nearMod

height = float(input('키(m) : '))
weight = float(input('몸무게(kg) : '))
bmi = round(weight / height ** 2, 2)
print(f'BMI : {bmi}')

bmiInfo = nearMod.BmiNearAlgorithm(bmi)
print(f'{bmiInfo.getCondition()}')