달성한 목표
강의 : 자료구조문풀1-3 / 알고리즘1-2
팀플 : 팀 스터디 미팅
정리할 파트
강의 : 자료구조문풀1-3 / 알고리즘1-2
자료구조 문제풀이
39 리스트
42
중복된 숫자 빼기
numbers = [2, 22, 7, 8, 9, 2, 7, 3, 5, 2, 7, 1, 3]
print(f'numbers: {numbers}')
idx = 0
while True:
if idx >= len(numbers):
break
if numbers.count(numbers[idx]) >= 2:
numbers.remove(numbers[idx])
continue
idx += 1
print(f'numbers : {numbers}')44 튜플
47 **
49 딕셔너리
51
split()
: str 내 공백이 있다면, 그 공백을 기준으로 글자들을 분리해서 list로 반환해주는 함수.
aboutPython = '파이썬은 1991년 프로그래머인 귀도 반 로섬이 발표한 고급 프로그래밍 언어이다.'
splitList = aboutPython.split()
print(splitList)
# 결과
['파이썬은', '1991년', '프로그래머인', '귀도', '반', '로섬이', '발표한', '고급', '프로그래밍', '언어이다.']알고리즘
앞서 배운 편리한 기능들(api/프로그램 language)이 어떤 수학적인 부분 혹은 어떤 일반화를 통해서 만들어질 수 있는지, 그 절차에 대해 알아보는 과목
1 선형 검색
: 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
ex/ 인덱스 0부터 순차적으로 검색한다.
datas = [3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
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(f'searchResultIdx: [{searchResultIdx}]')보초법
: 마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.
(검색 성공: 마지막 이전에 검색된 경우
/ 검색 실패: 마지막에 검색된 경우)
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
datas.append(searchData)
n = 0
while True:
# if n == len(datas):
# searchResultIdx = -1
# break
if datas[n] == searchData:
if n != len(datas) - 1:
searchResultIdx = n
break
n += 1
print(f'searchResultIdx: [{searchResultIdx}]')2
- 존재하는 여러개의 찾으려는 값 모두 찾기
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdxs = []
nums.append(searchData)
n = 0
while True:
if nums[n] == searchData:
if n != len(nums) - 1:
searchResultIdxs.append(n)
else:
break
n += 1
print(f'searchResultIdx: [{searchResultIdx}]')3 이진 검색
: "정렬되어 있는" 자료구조에서 중앙값과 크고 작음을 이용해서 데이터를 검색한다.
(검색 범위를 좁혀나가면서 내가 원하는 데이터를 찾는 방식)
datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
searchData = int(input('찾으려는 숫자 입력: '))
searchResultIdx = -1
staIdx = 0
endIdx = len(datas) - 1
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
print(f'midIdx: {midIdx}')
print(f'midVal: {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(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')
elif searchData < midVal:
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
print(f'midIdx: {midIdx}')
print(f'midVal: {midVal}')
elif searchData == midVal:
searchResultIdx = midIdx
break
print(f'searchResultIdx: [{searchResultIdx}]')
4
5 순위
: 수의 크고 작음을 이용해서 수의 순서를 정하는 것
import random
scores = random.sample(range(50, 101), 20)
ranks = [0 for i in range(20)]
for idx, sco1 in enumerate(scores):
for sco2 in scores:
if sco1 < sco2:
ranks[idx] += 1
print(scores)
print(ranks)
for i, s in enumerate(scores):
print(f'score:{s} \t rank:{ranks[i] + 1}')6 ***
- 중간/기말 석차, 등수 편차 class
7 버블 정렬 ***
: 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 큰 숫자를 가장 끝으로 옮기는 알고리즘
nums = [10, 2, 7, 21, 0]
# print(f'not sorted nums: {nums}')
length = len(nums) - 1
for i in range(length):
for j in range(length-i):
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(nums)
print()
print(f'sorted nums: {nums}')
# 결과
[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]
sorted nums: [0, 2, 7, 10, 21]8 ***
- 깊은 복사, 얕은 복사
9 삽입 정렬
: 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다.
nums = [5, 10, 2, 1, 0]
# ascending
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(f'nums: {nums}')
nums = [0, 5, 2, 10, 1]
# descending
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(f'nums: {nums}')
# 결과
nums: [5, 10, 2, 1, 0]
nums: [2, 5, 10, 1, 0]
nums: [1, 2, 5, 10, 0]
nums: [0, 1, 2, 5, 10]
nums: [5, 0, 2, 10, 1]
nums: [5, 2, 0, 10, 1]
nums: [10, 5, 2, 0, 1]
nums: [10, 5, 2, 1, 0]