(DataStructure & Algorithm) problems (2)

🔑Summarization

---

• 알고리즘 문제풀이 진행

---

📗Contents

---

검색 알고리즘

• 선형검색 : 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾음
  • 보초법 : 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화
• 이진검색
  • 가운데 데이터(중앙값) 이용
    ※ 정렬이 되어있는 상태라 가정함
  • 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터 검색
  • 검색 범위를 좁혀나가면서 원하는 값을 찾음

순위 알고리즘

• 순위 : 수의 크고 작음을 이용해서 수의 순서를 정하는 것

정렬 알고리즘

• 버블정렬 : 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘

• 삽입정렬 : 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다.
• 선택정렬 : - 주어진 리스트 중에 최솟값을 찾아 그 값을 맨 앞에 위치한 값과 교체하는 방식. 자료를 정렬하는 알고리즘

수학 알고리즘

• 최댓값(Max) : 자료구조에서 가장 큰 값을 찾는다
• 최솟값(Min) : 자료구조에서 가장 작은 값을 찾는다
• 최빈값(Mid) : 데이터에서 빈도수가 가장 많은 데이터
• 근삿값(Approximation) : 특정 값(참 값)에 가장 가까운 값
• 평균(Mean) : 여러 수나 양의 중간값을 갖는 수
• 재귀(Recursive) : 나 자신을 다시 호출하는 것

예제문제풀이

• 숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어 보자.

def searchNumberByLineAlgorithm(ns, sn):

    searchResultIdx = -1

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

    n = 0
    while True:

        if n == len(ns):
            print('search FAIL')
            break
        if ns[n] == sn:
            searchResultIdx = n
            print('search SUCCESS')
            print(f'search result INDEX : {searchResultIdx}')

        n += 1

    return searchResultIdx

• 숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어보자.

def searchNumberByBinaryAlgorithm(ns, sn):

    searchResultIdx = -1

    startIdx = 0
    endIdx = len(ns) - 1
    midIdx = (startIdx + endIdx) // 2
    midValue = ns[midIdx]

    print('start Idx : {}, endIdx : {}' .format(startIdx, endIdx))
    print('mid Idx : {}, midvalue : {}'.format(midIdx, midValue))

    while sn >= ns[0] and sn <= ns[len(ns) - 1]:

        if sn == ns[len(ns) - 1]:
            searchResultIdx = len(ns) - 1
            break

        if startIdx + 1 == endIdx:
            if ns[startIdx] != sn and ns[endIdx] != sn:
                break

        if sn > midValue:
            startIdx = midIdx
            midIdx = (startIdx + endIdx) // 2
            midValue = ns[midIdx]
            print('start Idx : {}, endIdx : {}'.format(startIdx, endIdx))
            print('mid Idx : {}, midvalue : {}'.format(midIdx, midValue))

        elif sn < midValue:
            endIdx = midIdx
            midIdx = (startIdx + endIdx) // 2
            midValue = ns[midIdx]
            print('start Idx : {}, endIdx : {}'.format(startIdx, endIdx))
            print('mid Idx : {}, midvalue : {}'.format(midIdx, midValue))

        elif sn == midValue:
            searchResultIdx = midIdx
            break

    return searchResultIdx

• 최솟값 알고리즘을 이용해서 숫자로 이루어진 리스트에서 최솟값과 최솟값의 갯수를 찾는 모듈을 만들어보자.
  (리스트는 1부터 50까지의 난수 30개를 이용하되, 중복이 허용되도록 한다

class MinAlgorithm:

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

    def setMinNum(self):
        self.minNum = 50

        for n in self.nums:
            if self.minNum > n:
                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

• 사용자가 정수 두개를 입력하면 작은 정수와 큰 정수 사이의 모든 정수의 합을 구하는 프로그램을 재귀 알고리즘을 이용해서 만들어보자.

class NumsSum:

    def __init__(self, n1, n2):
        self.bigNum = 0
        self.smallNum = 0
        self.setN1N2(n1, n2)

    def setN1N2(self, n1, n2):
        self.bigNum = n1
        self.smallNum = n2

        if n1 < n2:
            self.bigNum = n2
            self.smallNum = n1

    def addNum(self, n):
        if n <= 1:
            return n
        return n + self.addNum(n - 1)

    def sumBetweenNums(self):
        return self.addNum(self.bigNum - 1) - self.addNum(self.smallNum)