📌 알고리즘 연습문제 [선택]
📋 선형 검색
- 숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어 보자
- 검색 모듈은 선형 검색 알고리즘을 이용하자
- 리스트는 1부터 20까지의 정수 중에서 난수 10개를 이용한다.
-검색에 성공하면 해당 정수의 인덱스를 출력하고, 검색 결과가 없다면 -1을 출력하자
# 선형 검색
# 숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어 보자
# 검색 모듈은 선형 검색 알고리즘을 이용하자
# 리스트는 1부터 20까지의 정수 중에서 난수 10개를 이용한다.
# 검색 과정을 로그로 출력하자
# 검색에 성공하면 해당 정수의 인덱스를 출력하고, 검색 결과가 없다면 -1을 출력하자
import random
def liner(nums, n):
for idx, num in enumerate(nums):
if n == num:
print('search Success!')
print(f'search result INDEX : {idx}')
print(f'>>> Search Results <<<')
print(f'search result index : {idx}')
print(f'search result number : {num}')
return
print(f'>>> Search Results <<<')
print('search Fail:(')
print(f'search result index : -1')
nums = random.sample(range(1, 21), 10)
n = int(input('찾으려는 숫자 입력 : '))
print(f'nums : {nums}')
liner(nums, n)
찾으려는 숫자 입력 : 15
nums : [11, 16, 19, 7, 14, 15, 18, 4, 13, 17]
search Success!
search result INDEX : 5
>>> Search Results <<<
search result index : 5
search result number : 15
📋 이진 검색
- 숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어 보자
- 검색 모듈은 이진 검색 알고리즘을 이용하자
- 리스트는 [1,2,3,6,7,8,10,11,13,15,16,17,20,21,23,24,27,28] 이용한다.
- 검색에 성공하면 해당 정수의 인덱스를 출력하고, 검색 결과가 없다면 -1을 출력하
# 이진 검색
# 숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 다음 요건에 따라 만들어 보자
# 검색 모듈은 이진 검색 알고리즘을 이용하자
# 리스트는 [1,2,3,6,7,8,10,11,13,15,16,17,20,21,23,24,27,28] 이용한다.
# 검색 과정을 로그로 출력하자
# 검색에 성공하면 해당 정수의 인덱스를 출력하고, 검색 결과가 없다면 -1을 출력하자
def binarySearch(nums, n):
staIdx = 0
endIdx = len(nums) - 1
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
print(f' staIdx : {staIdx}, endIdx : {endIdx}')
print(f' midIdx : {midIdx}, midVal : {midVal}')
isSearch = False
while midVal != n and nums[len(nums) - 1] >= n >= nums[0]:
isSearch = True
if midVal < n:
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
print(f'+ staIdx : {staIdx}, endIdx : {endIdx}')
print(f'+ midIdx : {midIdx}, midVal : {midVal}')
else:
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
print(f'- staIdx : {staIdx}, endIdx : {endIdx}')
print(f'- midIdx : {midIdx}, midVal : {midVal}')
print(f'nums : {nums}')
print(f'>>> Search Results <<<')
if isSearch:
print(f'search result index : {midIdx}')
print(f'search result number : {nums[midIdx]}')
else:
print('search Fail:(')
print(f'search result index : -1')
nums = [1, 2, 3, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
n = int(input('input search num : '))
binarySearch(nums, n)
input search num : 11
staIdx : 0, endIdx : 17
midIdx : 8, midVal : 13
- staIdx : 0, endIdx : 8
- midIdx : 4, midVal : 7
+ staIdx : 4, endIdx : 8
+ midIdx : 6, midVal : 10
+ staIdx : 6, endIdx : 8
+ midIdx : 7, midVal : 11
nums : [1, 2, 3, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
>>> Search Results <<<
search result index : 7
search result number : 11
📋 순위 알고리즘 1
- 숫자로 이루어진 리스트에서 아이템의 순위를 출력하고, 순위에 따라 아이템을 정렬하는 모듈을 만들어보자
- 리스트는 50부터 100까지의 난수를 20개를 이용
# 순위 알고리즘
# 숫자로 이루어진 리스트에서 아이템의 순위를 출력하고, 순위에 따라 아이템을 정렬하는 모듈을 만들어보자
# 리스트는 50부터 100까지의 난수를 20개를 이용
import copy
import random
def rank(nums):
# sNums = copy.copy(nums)
# ranks = [0 for i in range(len(nums))]
#
# for i in range(len(sNums) - 1):
# maxIdx = i
# for j in range(i + 1, len(sNums)):
# if sNums[maxIdx] < sNums[j]:
# maxIdx = j
#
# sNums[i], sNums[maxIdx] = sNums[maxIdx], sNums[i]
ranks = [0 for i in range(len(nums))]
for idx, n1 in enumerate(nums):
for n2 in nums:
if n1 < n2:
ranks[idx] += 1
print(f'nums : {nums}')
print(f'ranks : {ranks}')
sNums = [0 for n in range(len(nums))]
for idx, r in enumerate(ranks):
sNums[r] = nums[idx]
print(f'sNums : {sNums}')
nums = random.sample(range(50, 101), 20)
rank(nums)
nums : [61, 70, 51, 97, 57, 86, 77, 95, 63, 58, 91, 50, 94, 68, 54, 60, 92, 81, 59, 69]
ranks : [12, 8, 18, 0, 16, 5, 7, 1, 11, 15, 4, 19, 2, 10, 17, 13, 3, 6, 14, 9]
sNums : [97, 95, 94, 92, 91, 86, 81, 77, 70, 69, 68, 63, 61, 60, 59, 58, 57, 54, 51, 50]
📋 순위 알고리즘 2
- 알파벳 문자들과 정수들에 대한 순위를 정하는 프로그램을 순위 알고리즘을 이용해서 만들어보자
- 단, 알파벳은 아스키코드 값을 이용한다
# 순위 알고리즘
# 알파벳 문자들과 정수들에 대한 순위를 정하는 프로그램을 순위 알고리즘을 이용해서 만들어보자
# 단, 알파벳은 아스키코드 값을 이용한다
def rankAskii(datas):
ascIIDatas = []
ranks = [0 for i in range(len(datas))]
for idx, d in enumerate(datas):
if type(d) == type('str'):
ascIIDatas.append(ord(d))
else:
ascIIDatas.append(d)
for idx, n1 in enumerate(ascIIDatas):
for n2 in ascIIDatas:
if n1 < n2:
ranks[idx] += 1
print(f'datas \t\t:{datas}')
print(f'ascIIDatas \t:{ascIIDatas}')
print(f'ranks \t\t:{ranks}')
datas = [32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']
rankAskii(datas)
datas :[32, 'a', 'z', 45, 'G', 39, 50, 'T', 't', 22, 31, 55, 's', 63, 59, 'E']
ascIIDatas :[32, 97, 122, 45, 71, 39, 50, 84, 116, 22, 31, 55, 115, 63, 59, 69]
ranks :[13, 3, 0, 11, 5, 12, 10, 4, 1, 15, 14, 9, 2, 7, 8, 6]
📌 자료구조 연습문제 [정렬]
📋 버블 정렬
- 숫자가 이루어진 리스트를 버블정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈
# 버블 정렬
# 숫자가 이루어진 리스트를 버블정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈
# 단 정렬하는 과정도 출력한다
def bubbleSort(nums, isAsc=True):
for i in range(1, len(nums) - 1):
for j in range(0, len(nums) - i):
if isAsc:
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
else:
if nums[j] < nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
print(f'sorted nums \t\t: {nums}')
if isAsc:
print(f'sorted nums by ASC\t: {nums}')
else:
print(f'sorted nums by DES\t: {nums}')
nums = [10, 4, 1, 13, 11, 16, 19, 14, 6, 5]
# ascending
bubbleSort(nums)
# descending
bubbleSort(nums, False)
sorted nums : [4, 1, 10, 11, 13, 16, 14, 6, 5, 19]
sorted nums : [1, 4, 10, 11, 13, 14, 6, 5, 16, 19]
sorted nums : [1, 4, 10, 11, 13, 6, 5, 14, 16, 19]
sorted nums : [1, 4, 10, 11, 6, 5, 13, 14, 16, 19]
sorted nums : [1, 4, 10, 6, 5, 11, 13, 14, 16, 19]
sorted nums : [1, 4, 6, 5, 10, 11, 13, 14, 16, 19]
sorted nums : [1, 4, 5, 6, 10, 11, 13, 14, 16, 19]
sorted nums : [1, 4, 5, 6, 10, 11, 13, 14, 16, 19]
sorted nums by ASC : [1, 4, 5, 6, 10, 11, 13, 14, 16, 19]
sorted nums : [4, 5, 6, 10, 11, 13, 14, 16, 19, 1]
sorted nums : [5, 6, 10, 11, 13, 14, 16, 19, 4, 1]
sorted nums : [6, 10, 11, 13, 14, 16, 19, 5, 4, 1]
sorted nums : [10, 11, 13, 14, 16, 19, 6, 5, 4, 1]
sorted nums : [11, 13, 14, 16, 19, 10, 6, 5, 4, 1]
sorted nums : [13, 14, 16, 19, 11, 10, 6, 5, 4, 1]
sorted nums : [14, 16, 19, 13, 11, 10, 6, 5, 4, 1]
sorted nums : [16, 19, 14, 13, 11, 10, 6, 5, 4, 1]
sorted nums by DES : [16, 19, 14, 13, 11, 10, 6, 5, 4, 1]
📋 삽입 정렬
- 숫자가 이루어진 리스트를 삽입 정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈
# 삽입 정렬
# 숫자가 이루어진 리스트를 삽입 정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈
# 단 정렬하는 과정도 출력한다
import copy
def insertSort(nums, isAsc=True):
print(f'\tnot sorted nums : {nums}')
for i in range(1, len(nums)):
i2 = i - 1
if isAsc:
while nums[i2] > nums[i2 + 1] and i2 >= 0:
nums[i2], nums[i2 + 1] = nums[i2 + 1], nums[i2]
i2 -= 1
print(f'\t\tinsert_sort : {nums}')
else:
while nums[i2] < nums[i2 + 1] and i2 >= 0:
nums[i2], nums[i2 + 1] = nums[i2 + 1], nums[i2]
i2 -= 1
val = nums[i2]
print(f'\t\tinsert_sort : {nums}')
if isAsc:
print(f'sorted nums by ASC : {nums}')
else:
print(f'sorted nums by DES : {nums}')
nums = [19, 10, 3, 5, 13, 4, 12, 17, 8, 16]
insertSort(copy.copy(nums))
insertSort(copy.copy(nums),False)
not sorted nums : [19, 10, 3, 5, 13, 4, 12, 17, 8, 16]
insert_sort : [10, 19, 3, 5, 13, 4, 12, 17, 8, 16]
insert_sort : [3, 10, 19, 5, 13, 4, 12, 17, 8, 16]
insert_sort : [3, 5, 10, 19, 13, 4, 12, 17, 8, 16]
insert_sort : [3, 5, 10, 13, 19, 4, 12, 17, 8, 16]
insert_sort : [3, 4, 5, 10, 13, 19, 12, 17, 8, 16]
insert_sort : [3, 4, 5, 10, 12, 13, 19, 17, 8, 16]
insert_sort : [3, 4, 5, 10, 12, 13, 17, 19, 8, 16]
insert_sort : [3, 4, 5, 8, 10, 12, 13, 17, 19, 16]
insert_sort : [3, 4, 5, 8, 10, 12, 13, 16, 17, 19]
sorted nums by ASC : [3, 4, 5, 8, 10, 12, 13, 16, 17, 19]
not sorted nums : [19, 10, 3, 5, 13, 4, 12, 17, 8, 16]
insert_sort : [19, 10, 3, 5, 13, 4, 12, 17, 8, 16]
insert_sort : [19, 10, 3, 5, 13, 4, 12, 17, 8, 16]
insert_sort : [19, 10, 5, 3, 13, 4, 12, 17, 8, 16]
insert_sort : [19, 13, 10, 5, 3, 4, 12, 17, 8, 16]
insert_sort : [19, 13, 10, 5, 4, 3, 12, 17, 8, 16]
insert_sort : [19, 13, 12, 10, 5, 4, 3, 17, 8, 16]
insert_sort : [19, 17, 13, 12, 10, 5, 4, 3, 8, 16]
insert_sort : [19, 17, 13, 12, 10, 8, 5, 4, 3, 16]
insert_sort : [19, 17, 16, 13, 12, 10, 8, 5, 4, 3]
sorted nums by DES : [19, 17, 16, 13, 12, 10, 8, 5, 4, 3]
📋 선택 정렬
- 숫자가 이루어진 리스트를 선택 정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈
# 숫자가 이루어진 리스트를 선택 정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈
# 단 정렬하는 과정도 출력한다
def selectSort(nums, isAsc=True):
for i in range(len(nums)):
idx = i
for j in range(i + 1, len(nums)):
if isAsc:
if nums[idx] > nums[j]:
idx = j
else:
if nums[idx] < nums[j]:
idx = j
nums[i], nums[idx] = nums[idx], nums[i]
print(f'nums : {nums}')
if isAsc:
print(f'sorted nums by ASC: {nums}')
else:
print(f'sorted nums by DES: {nums}')
nums = [6, 4, 13, 7, 9, 3, 8, 16, 19, 10]
print(f'not sorted nums : {nums}')
selectSort(copy.copy(nums))
print('-' * 50)
print(f'not sorted nums : {nums}')
selectSort(copy.copy(nums), False)
not sorted nums : [6, 4, 13, 7, 9, 3, 8, 16, 19, 10]
nums : [3, 4, 13, 7, 9, 6, 8, 16, 19, 10]
nums : [3, 4, 13, 7, 9, 6, 8, 16, 19, 10]
nums : [3, 4, 6, 7, 9, 13, 8, 16, 19, 10]
nums : [3, 4, 6, 7, 9, 13, 8, 16, 19, 10]
nums : [3, 4, 6, 7, 8, 13, 9, 16, 19, 10]
nums : [3, 4, 6, 7, 8, 9, 13, 16, 19, 10]
nums : [3, 4, 6, 7, 8, 9, 10, 16, 19, 13]
nums : [3, 4, 6, 7, 8, 9, 10, 13, 19, 16]
nums : [3, 4, 6, 7, 8, 9, 10, 13, 16, 19]
nums : [3, 4, 6, 7, 8, 9, 10, 13, 16, 19]
sorted nums by ASC: [3, 4, 6, 7, 8, 9, 10, 13, 16, 19]
--------------------------------------------------
not sorted nums : [6, 4, 13, 7, 9, 3, 8, 16, 19, 10]
nums : [19, 4, 13, 7, 9, 3, 8, 16, 6, 10]
nums : [19, 16, 13, 7, 9, 3, 8, 4, 6, 10]
nums : [19, 16, 13, 7, 9, 3, 8, 4, 6, 10]
nums : [19, 16, 13, 10, 9, 3, 8, 4, 6, 7]
nums : [19, 16, 13, 10, 9, 3, 8, 4, 6, 7]
nums : [19, 16, 13, 10, 9, 8, 3, 4, 6, 7]
nums : [19, 16, 13, 10, 9, 8, 7, 4, 6, 3]
nums : [19, 16, 13, 10, 9, 8, 7, 6, 4, 3]
nums : [19, 16, 13, 10, 9, 8, 7, 6, 4, 3]
nums : [19, 16, 13, 10, 9, 8, 7, 6, 4, 3]
sorted nums by DES: [19, 16, 13, 10, 9, 8, 7, 6, 4, 3]
📋 병합 정렬
- 숫자가 이루어진 리스트를 병합 정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈
# 병합 정렬
# 숫자가 이루어진 리스트를 병합 정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈
# 단 정렬하는 과정도 출력한다
def mergeSort(nums, isAsc=True):
if len(nums) < 2:
return nums
midIdx = len(nums) // 2
leftList = mergeSort(nums[:midIdx],isAsc)
rightList = mergeSort(nums[midIdx:],isAsc)
leftIdx = 0
rightIdx = 0
mergeNums = []
while len(leftList) > leftIdx and len(rightList) > rightIdx:
if isAsc:
if leftList[leftIdx] < rightList[rightIdx]:
mergeNums.append(leftList[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightList[rightIdx])
rightIdx += 1
else:
if leftList[leftIdx] > rightList[rightIdx]:
mergeNums.append(leftList[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightList[rightIdx])
rightIdx += 1
mergeNums += leftList[leftIdx:]
mergeNums += rightList[rightIdx:]
if isAsc:
print(f'[ASC] merge : {mergeNums}')
else:
print(f'[DES] merge : {mergeNums}')
return mergeNums
nums = [24, 62, 81, 38, 51, 10, 85, 76, 71, 91, 54, 56, 94, 49, 25, 28, 88, 50, 41, 84]
mergeSort(nums)
mergeSort(nums, False)
[ASC] merge : [24, 62]
[ASC] merge : [38, 51]
[ASC] merge : [38, 51, 81]
[ASC] merge : [24, 38, 51, 62, 81]
[ASC] merge : [10, 85]
[ASC] merge : [71, 91]
[ASC] merge : [71, 76, 91]
[ASC] merge : [10, 71, 76, 85, 91]
[ASC] merge : [10, 24, 38, 51, 62, 71, 76, 81, 85, 91]
[ASC] merge : [54, 56]
[ASC] merge : [25, 49]
[ASC] merge : [25, 49, 94]
[ASC] merge : [25, 49, 54, 56, 94]
[ASC] merge : [28, 88]
[ASC] merge : [41, 84]
[ASC] merge : [41, 50, 84]
[ASC] merge : [28, 41, 50, 84, 88]
[ASC] merge : [25, 28, 41, 49, 50, 54, 56, 84, 88, 94]
[ASC] merge : [10, 24, 25, 28, 38, 41, 49, 50, 51, 54, 56, 62, 71, 76, 81, 84, 85, 88, 91, 94]
[DES] merge : [62, 24]
[DES] merge : [51, 38]
[DES] merge : [81, 51, 38]
[DES] merge : [81, 62, 51, 38, 24]
[DES] merge : [85, 10]
[DES] merge : [91, 71]
[DES] merge : [91, 76, 71]
[DES] merge : [91, 85, 76, 71, 10]
[DES] merge : [91, 85, 81, 76, 71, 62, 51, 38, 24, 10]
[DES] merge : [56, 54]
[DES] merge : [49, 25]
[DES] merge : [94, 49, 25]
[DES] merge : [94, 56, 54, 49, 25]
[DES] merge : [88, 28]
[DES] merge : [84, 41]
[DES] merge : [84, 50, 41]
[DES] merge : [88, 84, 50, 41, 28]
[DES] merge : [94, 88, 84, 56, 54, 50, 49, 41, 28, 25]
[DES] merge : [94, 91, 88, 85, 84, 81, 76, 71, 62, 56, 54, 51, 50, 49, 41, 38, 28, 25, 24, 10]📌알고리즘- 선택과 정렬 연습문제 후기
개념을 어느정도 이해했다고 생각했지만 확실히 직접 문제를 풀어보니 헷갈리는 개념들이 많았다. 특히 삽입 알고리즘에서 현재 인덱스와 이전 인덱스를 비교하면서 반복하는 순서가 계속 헷갈렸다.
문제 상황에 맞는 효율적인 알고리즘을 구현하는 법을 연습할 필요가 있다고 느꼈다.
개발하고싶은사람