travel data science
[알고리즘] 2. 탐색과 정렬 본문
순차 탐색(특정 값 찾기): 리스트 안에 있는 원소를 하나씩 순차적으로 비교하면서 탐색, O(n)
def search_list(a, x):
ind=0
for i in a:
if i==x:
return ind
ind+=1
return -1#찾는 값(x)가 리스트에 없다면 -1을 반환
선택 정렬(작은 수부터 큰 수로 배열): 가장 작은 수를 선택하여 정렬함, O(n^2)
def sel_sort(a):
for i in range(0, len(a)):
min_idx=i
for k in range(i, len(a)):
if a[min_idx]>a[k]:
min_idx=k
a[i], a[min_idx]=a[min_idx], a[i]
return a
삽입 정렬(작은 수부터 큰 수로 배열): 학생을 뽑아 리스트 사이에 삽입하여 정렬함
def ins_sort(a):
for i in range(1, len(a)):
key=a[i]
j=i-1
while j>=0 and a[j]>key:
a[j+1]=a[j]
j-=1
a[j+1]=key
return a
a리스트에서 수를 뽑아서 앞의 수보다 작으면 계속 앞으로 가다가 그 자리가 되면 집어 넣는다. 리스트의 진행과정을 출력해서 보면 이해가 편하다.
병합 정렬(작은 수부터 큰 수로 배열): 정렬한(재귀호출) 두 조의 제일 앞 부분을 비교하여 새로운 list에 추가하여 배열(병합)함
'''쉬운 version'''
def merge_sort(happy):
if len(happy)<=1:
return happy
a=merge_sort(happy[:len(happy)//2])
b=merge_sort(happy[len(happy)//2:])
result=[]
while a and b:
if a[0]<b[0]:
result.append(a.pop(0))
else:
result.append(b.pop(0))
while a:
result.append(a.pop(0))
while b:
result.append(b.pop(0))
return result
'''일반 version'''
def merge_sort_2(a):
if len(a)<=1:
return a
g1=a[:len(a)//2]
g2=a[len(a)//2:]
merge_sort_2(g1)
merge_sort_2(g2)
g1_i=0
g2_i=0
a_i=0
while g1_i<len(g1) and g2_i<len(g2):
if g1[g1_i]<g2[g2_i]:
a[a_i]=g1[g1_i]
a_i+=1
g1_i+=1
else:
a[a_i]=g2[g2_i]
a_i+=1
g2_i+=1
while g1_i<len(g1):
a[a_i]=g1[g1_i]
a_i+=1
g1_i+=1
while g2_i<len(g2):
a[a_i]=g2[g2_i]
a_i+=1
g2_i+=1
return a
여기서 point는 재귀함수가 발현되기 전에 종결 조건을 작성하는 것임.
병합 정렬은 분할정복 설계기법임. 분할하여 문제를 풀게되면 풀기 어려웠던 문제도 쉽게 풀 수 있기 때문임.
큐: 선입선출(ex. 줄서기), 인큐(enqueue: 큐에 자료를 집어넣음)/디큐(dequeue: 큐에서 자료를 꺼냄[a.pop(0)])
스택: Last In First Out(ex. 접시 쌓기, 인터넷 뒤로가기 기능), 푸시(push: 자료를 집어넣음)/팝(pop: 자료를 꺼냄[a.pop()])
큐와 스택: 자료를 일렬로 보관함. '자료를 넣는 동작'과 '자료를 빼는 동작'을 할 수 있지만 동작 방식 다름
'''isalpha()함수'''
s='ga.yeon"g'
result=[]
for i in s:
if i.isalpha(): # 문자인지 아닌지 확인 후 boolean값을 반환
result.append(i)
print(result) # ==> [g,a,y,e,o,n,g]
'''큐와 스택을 활용한 회문찾기'''
def palindrome(s):
qu=[]
st=[]
for i in s:
if i.isalpha():
qu.append(i.lower())
st.append(i.lower())
while qu:
if qu.pop(0)!=st.pop():
return False
return True
딕셔너리: key와value의 대응 관계를 : 로 구분하여 저장하는 자료 구조
→ key가 중복되지 않기 때문에 이미 존재하는 키에 새 값을 넣으면 기존 값은 지워지고 새 값으로 덮어짐.
d[key]=value / del d[key] / clear() / key in d
'''딕셔너리를 이용하여 동명 이인 찾기'''
def find_same_name(a):
name_dict={}
for i in a:
if i in name_dict:
name_dict[i]+=1
else:
name_dict[i]=1
name_set=set()
for i in name_dict:
if name_dict[i]>1:
name_set.add(i)
return name_set
example=['siu', 'gayeong', 'siu', 'mom']
print(find_same_name(example))
for문이 겹쳐져서 사용되면 계산복잡도 O(n^2)가 되기 때문에 가급적 자제.
계산복잡도 뿐만이 아니라 공간복잡도도 고려를 해야 함.
'Python study' 카테고리의 다른 글
[Django] operational error (0) | 2022.02.07 |
---|---|
Django html코딩을 편리하게 하기 위한 vscode extensions모음 (0) | 2022.01.22 |
[알고리즘] 1. 알고리즘의 정의와 재귀함수 (2) | 2021.10.09 |
백준 1316번 문제 (0) | 2021.10.08 |
백준 2941번 문제 (0) | 2021.10.08 |