python - 알고리즘 문제 : 데이터 취업 스쿨 스터디 노트 11/22

이진 검색

검색을 하다가 마지막에 아이템이 2개 남았는데,
찾는 값이 endIdx에 있다면 midIdx = staIdx라서 무한 루프에 빠진다.
이 부분을 해결하는 코드가 추가되었다.

def binarySearch(nums, num):
  print('*** searching start ***')
  searchIdx = -1

  staIdx = 0
  endIdx = len(nums) - 1
  midIdx = (staIdx + endIdx) // 2

  while True:
    print(f'staIdx: {staIdx}, midIdx: {midIdx}, endIdx: {endIdx}')

    if staIdx + 1 == endIdx:
      midIdx = endIdx

    if num in nums[staIdx:midIdx]:
      endIdx = midIdx
      midIdx = (staIdx + endIdx) // 2

    elif num in nums[midIdx+1:endIdx+1]:
      staIdx = midIdx
      midIdx = (staIdx + endIdx) // 2

    elif num == nums[midIdx]:
      searchIdx = midIdx
      print(f'{num}의 index: {searchIdx}')
      break

    else:
      print(f'리스트에 {num}이 없습니다.')
      break


numbers = [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16,
           17, 20, 21, 23, 24, 27, 28]

searchNum = int(input('input search number: '))

print(f'numbers: {numbers}')
print(f'search number: {searchNum}')
binarySearch(numbers, searchNum)

>>>
numbers: [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, ...]
search number: 28
*** searching start ***
staIdx: 0, midIdx: 8, endIdx: 17
staIdx: 8, midIdx: 12, endIdx: 17
staIdx: 12, midIdx: 14, endIdx: 17
staIdx: 14, midIdx: 15, endIdx: 17
staIdx: 15, midIdx: 16, endIdx: 17
staIdx: 16, midIdx: 16, endIdx: 17 ⭐이 부분에서 무한루프 발생 가능
28의 index: 17

순위에 따라 정렬하기

import random

def ranking(nums):
  ranks = [0 for i in range(len(nums))]

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

  return ranks

def sorting(nums, ranks):
  sorted = [0 for i in range(len(nums))]

  for idx, value in enumerate(ranks):
    sorted[value] = nums[idx]

  return sorted


numbers = random.sample(range(50, 101), 10)
ranks = ranking(numbers)
sNumbers = sorting(numbers, ranks)

print(f'numbers: {numbers}')
print(f'ranks: {ranks}')
print(f'sorted Numbers: {sNumbers}')

>>>
numbers: [56, 97, 85, 89, 59, 61, 77, 92, 72, 87]
ranks: [9, 0, 4, 2, 8, 7, 5, 1, 6, 3]
sorted Numbers: [97, 92, 89, 87, 85, 77, 72, 61, 59, 56]

평균, 최댓값, 최솟값, 편차 구하는 클래스

class ScoreStatistics:
    def __init__(self, s):
        self.scores = s
        self.total = 0
        self.avg = 0
        self.min = 0
        self.max = 0
        
    def getMinScore(self):
        if self.scores == None or len(self.scores) == 0:
            return None
        
        self.min = self.scores[0]
        for score in self.scores:
            if self.min > score:
                self.min = score
        
        return self.min

    def getMaxScore(self):
        if self.scores == None or len(self.scores) == 0:
            return None
        
        self.max = self.scores[0]
        for score in self.scores:
            if self.max < score:
                self.max = score
        
        return self.max
    
    def getTotalScore(self):
        if self.scores == None or len(self.scores) == 0:
            return None
        
        # 초기화하지 않으면 호출할 때마다 값이 누적될 수 있음
        self.total = 0
        for score in self.scores:
            self.total += score
            
        return self.total
    
    def getAvgScore(self):
        if self.scores == None or len(self.scores) == 0:
            return None
        
        self.avg = round(self.getTotalScore() / len(self.scores), 2)
        
        return self.avg
        
    def getMaxDeviation(self):
        result = abs(self.getAvgScore() - self.getMaxScore())
        return round(result, 2)

    def getMinDeviation(self):
        result = abs(self.getAvgScore() - self.getMinScore())
        return round(result, 2)


import random
scores = random.sample(range(51, 101), 10)
ss = ScoreStatistics(scores)

print(f'scores: {scores}')
print(f'total: {ss.getTotalScore()}')
print(f'avg: {ss.getAvgScore()}')
print(f'min: {ss.getMinScore()}')
print(f'max: {ss.getMaxScore()}')
print(f'min-deviation: {ss.getMinDeviation()}')
print(f'max-deviation: {ss.getMaxDeviation()}')

>>>
scores: [57, 80, 87, 93, 100, 69, 70, 95, 54, 91]
total: 796
avg: 79.6
min: 54
max: 100
min-deviation: 25.6
max-deviation: 20.4

최댓값, 최빈값 구하는 클래스

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

    def setMaxNumber(self):
        self.maxNum = 0
        self.masNumIdx = 0

        for idx, value in enumerate(self.nums):
            if self.maxNum < value:
                self.maxNum = value
                self.maxNumIdx = idx

    def getMaxNum(self):
      return self.maxNum

    def getMaxNumIdx(self):
      return self.maxNumIdx


class Mode:
    def __init__(self, nums, max):
        self.nums = nums
        self.maxNum = max
        self.indexes = []
    
    def setIndexList(self):
        self.indexes = [0 for i in range(self.maxNum + 1)]
        
        for num in self.nums:
            self.indexes[num] += 1
            
    def getIndexList(self):
        # index가 초기화되지 않은 경우
        if sum(self.indexes) == 0:
            return None
        else: return self.indexes
    
    def printAges(self):
        n = 1
        #⭐⭐⭐
        while True:
            maxModeAlo = Max(self.indexes)
            maxModeAlo.setMaxNumber()
            maxModeNum = maxModeAlo.getMaxNum()
            maxModeNumIdx = maxModeAlo.getMaxNumIdx()
            
            # maxModeNum이 초기화되지 않은 경우
            if maxModeNum == 0: break
            
            print(f'[{n:0>3}] {maxModeNumIdx}세 빈도수: {maxModeNum}', end=' ')
            print('*' * maxModeNum)
            
            self.indexes[maxModeNumIdx] = 0;
            
            n += 1

import random
ages = []
for i in range(100):
  ages.append(random.randint(25, 50))

maxAgeAlo = Max(ages)
maxAgeAlo.setMaxNumber()
maxAge = maxAgeAlo.getMaxNum()

maxModeAlo = Mode(ages, maxAge)
maxModeAlo.setIndexList()
maxModeAlo.printAges()

>>>
[001] 26세 빈도수: 8 ********
[002] 34세 빈도수: 7 *******
[003] 43세 빈도수: 6 ******
(...)

근삿값 : 지점

minAbs 값을 적당한(?) 양수로 설정한 후 실행해보니, depth에 큰 수가 입력될 때 에러가 발생했다. 문제에서 의도하는 바는 아니겠지만... 음수로 수정해봤다.

❗ int(float())

depth = float(input('depth: '))
depth = round(depth, 2)
temps = {0:24, 5:22, 10:20, 15:16, 20:13, 25:10, 30:6}

minAbs = -1
for key in temps.keys():
  absSub = abs(depth - key)
  print(f'[{key}] absSub: {absSub}')
  if minAbs > absSub or minAbs == -1:
    minAbs = absSub
    nearNum = key

temperature = temps[nearNum]

print(f'depth: {depth}')
print(f'temperature: {temperature}')

>>>
depth: 22.5
temperature: 13

>>>
depth: 22.6
temperature: 10

✔ depth: 22.5 ➡ temperature: 13

depth: 22.5
[0] absSub: 22.5
[5] absSub: 17.5
[10] absSub: 12.5
[15] absSub: 7.5
[20] absSub: 2.5
[25] absSub: 2.5
[30] absSub: 7.5

근삿값 : 구간

이런 방법도 있구나 싶었던 문제

weight = float(input('weight: '))
height = float(input('height: '))
bmi = round(weight / (height ** 2), 2)

# ⭐⭐⭐
bmiChart = {18.5:['저체중', '정상'], 23:['정상', '과체중'],
            25:['과체중','비만']}

minSub = -1
for key in bmiChart.keys():
    absSub = abs(bmi - key)
    if minSub > absSub or minSub == -1:
        minSub = absSub
        nearIdx = key

if bmi <= nearIdx:
    condition = bmiChart[nearIdx][0]
else:
    condition = bmiChart[nearIdx][1]

print(f'BMI: {bmi}')
print(f'condition: {condition}')

>>>
weight: 54
height: 1.65
BMI: 19.83
condition: 정상

재귀 : 두 수 사이의 모든 정수의 합

def numSum(num1, num2):
    if num1 == num2 - 1:
        return 0

    nextNum = num1 + 1
    return nextNum + numSum(nextNum, num2)

num1 = int(input('num1: '))
num2 = int(input('num2: '))

if num1 > num2:
    smallNum = num2
    largeNum = num1
else:
    smallNum = num1
    largeNum = num2    
    
result = numSum(smallNum, largeNum)
print(f'{smallNum}과 {largeNum} 사이의 모든 정수의 합: {result}')

>>>
num1: 10
num2: 3
3과 10 사이의 모든 정수의 합: 39

🚗 오늘 알고리즘 문제 풀이를 끝으로 파이썬 과정이 마무리 되었다.
알았던 것도 다시 보면 새롭고 그렇다.
앞으로도 정리한 내용을 한 번씩 복습하거나, 새로운 문제를 풀어봐야겠다.

🚕 내일부터 EDA 과정이 시작된다.
아마 파이썬보다 더 생소한 개념이 많지 않을까?
어렵더라도 차근차근 따라가다보면 익숙해질 거라고 생각한다. 🙌