알고리즘 - 기초 알고리즘

• 알고리즘 : 어떠한 문제를 풀어맺기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차

◾검색

1. 선형검색

• 선형검색 : 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.

  인덱스	0	1	2	3	4	5	6	7	8	9
  값	3	2	5	7	9	1	0	8	6	4

  • 인덱스 0부터 9까지 순차적으로 검색 : 성공 or 실패

# 선형검색
datas = [3,2,5,7,9,1,0,8,6,4]
print('datas : {}'.format(datas))
print('datas len : {}'.format(len(datas)))

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

n = 0
while True :
    if n == len(datas):
        searchResultIdx = -1
        break
    elif datas[n] == searchData:
        searchResultIdx = n
        break
    n += 1
print('searchResultIdx : {}'.format(searchResultIdx))

• 보초법 : 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정 간략화

  인덱스	0	1	2	3	4	5	6	7	8	9	10
  값	3	2	5	7	9	1	0	8	6	4	찾으려는 값

  • 인덱스 0부터 10까지 순차적으로 검색
    • 검색 성공 : 마지막 이전에 '찾으려는 값'이 검색된 경우
    • 검색 실패 : 마지막에 '찾으려는 값'가 검색된 경우

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

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

datas.append(searchData)

n = 0
while True :
    if datas[n] == searchData:
        if n != len(datas)-1:
            searchResultIdx = n
        break
    n += 1
print('datas : {}'.format(datas))
print('datas len : {}'.format(len(datas)))
print('searchResultIdx : {}'.format(searchResultIdx))

2. 이분검색

• 이진검색 : 정렬되어있는 자료구조에서 중앙값과의 크고 작음을 이용해 데이터 검색
  • 검색대상 2 : 중앙값 5보다 작으므로 왼쪽값에서 재탐색, 값을 찾을 때까지 반복

    인덱스	0	1	2	3	4	5	6	7	8
    값	1	2	3	4	5	6	7	8	9

# 이진검색(이분검색)
datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
print('datas : {}'.format(datas))
print('datas len : {}'.format(len(datas)))

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

staIdx = 0
endIdx = len(datas) - 1
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
print('midIdx : {}'.format(midIdx))
print('midVal : {}'.format(midVal))
while searchData <= datas[len(datas)-1] and searchData >= datas[0]:
    if searchData == datas[len(datas)-1]:
        searchResultIdx = len(datas)-1
        break

    if searchData > midVal:
        staIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = datas[midIdx]
        print('midIdx : {}'.format(midIdx))
        print('midVal : {}'.format(midVal))
    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = datas[midIdx]
        print('midIdx : {}'.format(midIdx))
        print('midVal : {}'.format(midVal))
    elif searchData == midVal:
        searchResultIdx = midIdx
        break
print('searchResultIdx : {}'.format(searchResultIdx))

---

◾순위

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

# 순위
import random
scores = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]

for idx, num1 in enumerate(scores):
    for num2 in scores:
        if num1 < num2 :
            ranks[idx] += 1
print('scores : {}'.format(scores))
print('ranks : {}'.format(ranks))

for idx, num in enumerate(scores):
    print('score : {}\trank : {}'.format(num, ranks[idx]+1))

---

◾기본 정렬

1. 버블 정렬

• 버블 정렬 : 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하며 큰 숫자를 가장 끝으로 옮기는 알고리즘
  • [10, 2, 7, 21, 0]
  • [2, 10, 7, 21, 0] - [2, 7, 10, 21, 0] - [2, 7, 10, 21, 0] - [2, 7, 10, 0, 21]
  • [2, 7, 10, 0, 21] - [2, 7, 10, 0, 21] - [2, 7, 0, 10, 21]
  • [2, 7, 0, 10, 21] - [2, 0, 7, 10, 21]
  • [0, 2, 7, 10, 21]

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

length = len(nums)
for i in range(length):
    for j in range(length - i - 1):
        if nums[j] > nums[j+1]:
            # temp = nums[j]
            # nums[j] = nums[j+1]
            # nums[j+1] = temp
            nums[j], nums[j+1] = nums[j+1], nums[j]
print('sorted nums : {}'.format(nums))

2. 삽입 정렬

• 삽입 정렬 : 정렬되어 있는 자료 배열과 비교해서 정렬 위치를 찾는다.
  • [5, 10, 2, 1, 0]
  • [5, 10, 2, 1, 0] - [5, 10]
  • [5, 10, 2, 1, 0] - [2, 5, 10]
  • [2, 5, 10, 1, 0] - [1, 2, 5, 10]
  • [1, 2, 5, 10, 0] - [0, 1, 2, 5, 10]
  • [0, 1, 2, 5, 10]

# 삽입 정렬
nums = [5, 10, 2, 1, 0]
print(nums)
for i1 in range(1, len(nums)):
    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(nums)

3. 선택 정렬

• 선택 정렬 : 주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘
  • [4, 2, 5, 1, 3]
  • [4, 2, 5, 1, 3] - [1, 4, 2, 5, 3]
  • [1, 4, 2, 5, 3] - [1, 2, 4, 5, 3]
  • [1, 2, 4, 5, 3] - [1, 2, 3, 4, 5]
  • [1, 2, 3, 4, 5] - [1, 2, 3, 4, 5]
  • [1, 2, 3, 4, 5] - [1, 2, 3, 4, 5]

# 선택 정렬
nums = [4, 2, 5, 1, 3]
print('original nums : {}'.format(nums))

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

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

print('sorted nums : {}'.format(nums))

---

◾최대값

• 최대값 : 자료구조에서 가장 큰 값을 찾는다.

# 최대값, max()
nums = [-2, -4, 5, 7, 10, 0, 8, 20, -11]
maxNum = nums[0]
print('nums : {}'.format(nums))
for i in range(1, len(nums)):
    if maxNum < nums[i]:
        maxNum = nums[i]

print('max : {}'.format(maxNum))

---

◾최소값

• 최소값 : 자료구조에서 가장 작은 값을 찾는다.

# 최대값, min()
nums = [-2, -4, 5, 7, 10, 0, 8, 20, -11]
maxNum = nums[0]
print('nums : {}'.format(nums))
for i in range(1, len(nums)):
    if maxNum > nums[i]:
        maxNum = nums[i]

print('max : {}'.format(maxNum))

---

◾최빈값

• 최빈값 : 자료구조에서 빈도수가 가장 많은 데이터

# 빈도수, count
nums = [1, 3, 7, 6, 7, 7, 7, 12, 12, 17]
indexes = [0 for i in range(max(nums) + 1)]

mostNum = 0
count = 0
for num in nums:
    indexes[num] += 1
    if count < indexes[num]:
        mostNum = num
        count = indexes[num]

print('mostNum : {}, count : {}'.format(mostNum, count))

---

◾근사값

• 근사값 : 특정 값(참값)에 가장 가까운 값

# 근사값
import random
nums = random.sample(range(0, 51), 20)
print('nums : {}'.format(nums))
inputNum =int(input('input number : '))
print('inputNum : {}'.format(inputNum))

nearNum = 0
minNum = 50
for n in nums:
    absNum = abs(n - inputNum)
    # print('absNum : {}'.format(absNum))
    
    if absNum < minNum:
        minNum = absNum
        nearNum = n

print('nearNum : {}'.format(nearNum))