[Zero-Base DS]스터디노트_알고리즘(01)

주요 학습내용

1. 알고리즘이란

2. 선형 검색

3. 이진 검색

4. 순위

5. 버블 정렬

6. 삽입 정렬

7. 선택 정렬

8. 최댓값/최솟값

9. 최빈값

I. 알고리즘(Algorithm)이란

알고리즘이란 어떤 문제의 해결을 위하여, 입력된 자료를 토대로 하여 원하는 출력을 유도하여 내는 규칙의 집합.
여러 단계의 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다.
[출처: 표준국어대사전]

II. 선형 검색

1. 선형 검색(Linear Search)

• 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는 알고리즘
• 구현이 쉽고 리스트의 정렬 여부와 상관 없이 사용할 수 있다는 장점이 있지만, 리스트의 모든 요소를 확인해야 하기 때문에 리스트의 길이가 길수록 비효율적

2. 파이썬 예제(선형 검색)

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

# 사용자가 입력한 숫자 위치 찾기

searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1  # 존재하지 않는 인덱스, -1로 지정하고 시작

n = 0
while True:  # 계속해서 무한루프
    if n == len(datas):
        searchResultIdx = -1
        break
    elif datas[n] == searchData:
        searchResultIdx = n
        break

    n += 1
print(f'datas: {datas}')
print(f'data length: {len(datas)}')
print(f'searchResultIdx: {searchResultIdx}')

출력 결과 :

3. 보초법

• 마지막 인덱스에 찾으려는 값을 추가하고 이를 보초(Sentinel)값으로 사용
  

4. 파이썬 예제(보초법)

datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
# 2) 보초법: 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다

searchData = int(input('찾으려는 숫자 입력: '))

searchResultIdx = -1  # 존재하지 않는 인덱스 값 -1로 지정

datas.append(searchData)
n = 0
while True:
    if datas[n] == searchData:
        if n != len(datas) - 1:  # n이 추가한 항목 x 이전에 찾은 항목
            searchResultIdx = n
        break

    n += 1

print(f'datas: {datas}')
print(f'data length: {len(datas)}')
print(f'searchResultIdx: {searchResultIdx}')

출력 결과 : (찾으려는 숫자(7)이 마지막 인덱스에 추가된 것을 확인할 수 있다)

III. 이진 검색

1. 이진 검색

• 정렬되어 있는자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색
• 원하는 값을 찾을 때 까지 검색할 데이터의 범위를 반씩 줄여가면서 찾는 알고리즘

2. 파이썬 예제(이진 검색)

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
print(f'datas: {datas}')
print(f'datas length: {len(datas)}')

searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1

staIdx = 0
endIdx = len(datas) - 1
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]

while searchData <= datas[len(datas)-1] and searchData >= datas[0]:
# datas 안에 있어야 하므로, 범위 지정
    if searchData == datas[len(datas) - 1]:
        searchResultIdx = len(datas)-1
        break

    if searchData > midVal:
        # 다시 재정의
        staIdx = midIdx
        midIdx = (staIdx + datas[endIdx]) // 2
        midVal = datas[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')

    elif searchData < midVal:
        # 다시 재정의
        endIdx = midIdx
        midIdx = (staIdx + datas[endIdx]) // 2
        midVal = datas[midIdx]
        print(f'midIdx: {midIdx}')
        print(f'midVal: {midVal}')

    elif searchData == midVal:
        searchResultIdx = midIdx
        break

print(f'searchResultIdx: {searchResultIdx}')

출력 결과 (1) :

출력 결과 (2) :

IV. 순위

1. 순위

• 수의 크고 작음을 이용해서 수의 순서를 정함
  

2. 파이썬 예제(순위 구하기)

import random

nums = random.sample(range(50,101), 20)
ranks = [0 for i in range(20)]
print(f'nums: {nums}')
print(f'ranks: {ranks}')
# 각각 대응하는 인덱스의 순위를 만들기 위해 nums이랑 같은 길이의 ranks 생성
#  ranks = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


print('-'*50)
# 중첩/중복 for문
for idx, num1 in enumerate(nums):  # idx랑 value 모두 뽑아줌
    for num2 in nums:
        if num1 < num2:
            ranks[idx] += 1
print(f'nums: {nums}')
print(f'ranks: {ranks}')

# 보기 좋게 수정
for idx, num in enumerate(nums):
    print(f'nums: {num}\t rank: {ranks[idx]+1}')

출력 결과 :

V. 버블 정렬

1. 버블 정렬

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

2. 파이썬 예제(버블 정렬)

nums = [10, 2, 7, 21, 0]
print(f'nums: {nums}')
length = len(nums) - 1

for i in range(length):
    for j in range(length - i):  # 계속 끝까지 가는 것이 아닌, i까지
        if nums[j] > nums[j + 1]:
            # 자리 바꾸기 방법 1
            # temp = nums[j]
            # nums[j] = nums[j + 1]
            # nums[j + 1] = temp

            # 자리 바꾸기 방법 2
            nums[j], nums[j + 1] = nums[j + 1], nums[j]
        print(f'sorting nums: {nums}')  # 과정 보기 위해 출력
    print()

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

출력 결과 :

VI. 삽입 정렬

1. 삽입 정렬

• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘

2. 파이썬 예제(삽입 정렬)

# ascending
nums = [5, 10, 2, 1, 0]

for i1 in range(1, len(nums)):  # 인덱스 1부터 (전)인덱스와 비교하므로, 시작number = 1
    i2 = i1 - 1
    cNum = nums[i1]
    # nums의 인덱스 i1값

    while nums[i2] > cNum and i2 >= 0:
        nums[i2 + 1] = nums[i2]
        i2 -= 1
    nums[i2 + 1] = cNum
    print(f'nums: {nums}')
print(f'sorted nums(오름차순): {nums}')


# descending
nums = [0, 5, 2, 10, 1]

for i1 in range(1, len(nums)):  # 인덱스 1부터 (전)인덱스와 비교하므로, 시작number = 1
    i2 = i1 - 1
    cNum = nums[i1]
    while nums[i2] < cNum and i2 >= 0:
        nums[i2 + 1] = nums[i2]
        i2 -= 1
    nums[i2 + 1] = cNum
    print(f'nums: {nums}')
print(f'sorted nums(내림차순): {nums}')

출력 결과 :

VII. 선택 정렬

1. 선택 정렬

• 주어진 리스트 중에 최솟값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘 [사진 출처: 네이버 블로그]

2. 파이썬 예제(선택 정렬)

nums = [4, 2, 5, 1, 3]
print(f'nums: {nums}')
for i in range(len(nums)-1):
    minIdx = i

    for j in range(i + 1, len(nums)):
        if nums[minIdx] > nums[j]:  # 1st num[j] = 2, nums[minIdx] = 4
            minIdx = j  # 최솟값의 인덱스 바꿈

    # 방법 1) temp 생성
    # tempNum = nums[i]
    # nums[i] = nums[minIdx]
    # nums[minIdx] = tempNum
    # 방법 2) 값 바꾸기
    nums[i], nums[minIdx] = nums[minIdx], nums[i]
    print(f'sorting number by ASC: {nums}')
print('='*50)
print(f'sorted number by ASC: {nums}')

출력 결과 :

VIII. 최댓값/최솟값

• 자료구조에서 가장 큰 값과 가장 작은 값

1. 파이썬 예제(최댓값)

# 최댓값

class MaxAlgorithm:

    def __init__(self, ns):  # 디폴트 값 설정
        self.nums = ns
        self.maxNum = 0

    def getMaxNum(self):

        self.maxNum = self.nums[0]  # 인덱스 0부터 시작

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

        return self.maxNum

ma = MaxAlgorithm([-2, -4, 5, 7, 10, 0, 8, 20, -11])
maxNum = ma.getMaxNum()
print(f'max number: {maxNum}')

출력 결과 :

2. 파이썬 예제(최솟값)

# 최댓값

class MaxAlgorithm:

    def __init__(self, ns):  # 디폴트 값 설정
        self.nums = ns
        self.maxNum = 0

    def getMaxNum(self):

        self.maxNum = self.nums[0]  # 인덱스 0부터 시작

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

        return self.maxNum

ma = MaxAlgorithm([-2, -4, 5, 7, 10, 0, 8, 20, -11])
maxNum = ma.getMaxNum()
print(f'max number: {maxNum}')

출력 결과 :

IX. 최빈값

• 데이터에서 빈도수가 가장 많은 데이터
• 우선 최댓값을 구해주고, 추가로 (최댓값의 길이 + 1 의 길이의)인덱스 리스트를 생성한 후, 해당 인덱스에 반복 횟수를 더해주는 방식으로 구현하였다

1. 파이썬 예제(최빈값 + 최댓값)

# 최댓값 산출
# number -> 인덱스로 생각하고, 새로 만들 배열 인덱스 값에 +1

class MaxAlgorithm:

    def __init__(self, ns):
        self.nums = ns
        self.maxNum = 0
        self.maxNumIdx = 0  # 인덱스 값도 하나 생성

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

        for idx, num in enumerate(self.nums):
            if self.maxNum < num:
                self.maxNum = num  # 재할당
                self.maxNumIdx = idx  # 재할당

    def getMaxNum(self):
        return self.maxNum

    def getMaxNumIdx(self):
        return self.maxNumIdx

# 최댓값 구하기
nums = [1, 3, 7, 6, 7, 7, 7, 12, 12, 17]
maxAlo = MaxAlgorithm(nums)
maxAlo.setMaxIdxAndNum()
maxNum = maxAlo.getMaxNum()
print(f'max num: {maxNum}')

# 배열 생성
indexes = [0 for i in range(maxNum+1)]
print(f'indexes: {indexes}')
print(f'indexes length: {len(indexes)}')

# 인덱스 갯수 ++
for n in nums:
    indexes[n] = indexes[n] + 1
print(f'indexes: {indexes}')

# max algorithm 활용하여 다시 indexes 중 최댓값 구하기
ma = MaxAlgorithm(indexes)
getMax = ma.setMaxIdxAndNum()
maxNum = ma.getMaxNum()
maxNumIdx = ma.getMaxNumIdx()
print(f'max num(빈도수): {maxNum}')
print(f'max Indexes(최빈값): {maxNumIdx}')
print(f'즉, {maxNumIdx}의 빈도수가 {maxNum}로 가장 높다.')

출력 결과 :

[자료 출처: 제로베이스 데이터 취업 스쿨]