Notice
Recent Posts
Recent Comments
Link
«   2025/08   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Tags
more
Archives
Today
Total
관리 메뉴

travel data science

[알고리즘] 2. 탐색과 정렬 본문

Python study

[알고리즘] 2. 탐색과 정렬

가방이 2021. 10. 11. 00:56

순차 탐색(특정 값 찾기): 리스트 안에 있는 원소를 하나씩 순차적으로 비교하면서 탐색, 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)가 되기 때문에 가급적 자제.

계산복잡도 뿐만이 아니라 공간복잡도도 고려를 해야 함.