이자다의 기록

11-1 거품정렬 과정을 알고리즘으로 적어보라 def bubble_sort(a): n=len(a) while 1: change=False for i in range(0, n-1): if a[i] > a[i+1]: a[i], a[i+1] = a[i+1], a[i] change=True if change==False: return d=[2, 4, 5, 1, 3, 9, 11, 22, 7, 2] bubble_sort(d) print(d) 결과: [1, 2, 2, 3, 4, 5, 7, 9, 11, 22] 처음엔 재귀함수를 써야하나 했는데 생각해보니 반복문으로 충분하겠더라. 첫 시도에선 while문 탈출 조건을 True/False가 아니라 변수 하나에 0을 저장하고 앞뒤 값이 바뀌지 않을때마다 변수에 1을 더해서 ..

퀵 정렬은 '피벗(pivot)'이라는 기준을 하나 선정하고 피벗보다 큰 리스트, 피벗보다 작은 리스트로 리스트를 나누어 정렬하고 다시 합하는 정렬 방식이다. 쉽게 설명한 퀵 정렬 알고리즘은 아래와 같다 def quick_sort(a): n = len(a) if n > [1, 2, 3, 4, 5] 가 된다. 그리고 이번 정렬에서도 재귀함수가 쓰였는데 동작 방식은 다음과 같다. 1. 리스트a = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]일 때 피벗은 리스트의 마지막 원소로 정한다고 가정한다. 2. 리스트 a는 피벗=5를 기준으로 피벗보다 크고 작은 리스트 두개로 나뉜다. [3, 1, 2, 4], 5, [6, 8, 9, 10, 7] 3. [3, 1, 2, 4]는 마지막 원소를 피벗으로 삼는다. ..

10-1 교재의 병합정렬은 오름차순인데 이를 내림차순으로 바꾸려면 어디를 바꿔야할까? def merge_sort(a): #리스트a를 입력으로 받음 n=len(a) if n g2[i2]: # g1의 원소가 더 크면 a[ia] = g1[i1] #리스트a에 g1의 원소를 덮어씌움 i1 += 1 #g1 원소번호 1 증가 ia += 1 #리스트a 원소번호 1 증가 else: a[ia] = g2[i2] #리스트a에 g2의 원소를 덮어씌움 i2 += 1 #g2원소번호 1 증가 ia += 1 #리스트a 원소번호 1 증가 # 두 리스트 중 아직 자료가 남은 리스트의 자료를 결과에 추가 while i1 < len(g1): a[ia] = g1[i1] i1 += 1 ia += 1 while i2 < len(g2): a[ia]..

병합정렬의 과정은 다음과 같다. 1. 리스트a를 입력으로 받는다. 2. 리스트를 중간을 기준으로 두개로 나누고 각각을 정렬한다. 3. 각 리스트의 첫번째 값을 비교하여 더 작거나, 더 큰 값을 최종 결과 리스트에 집어넣는다. 4. 3번 과정을 두 리스트 중 하나가 모두 빌 때까지 반복한다. 5. 아직 값이 남아있는 리스트의 값들을 전부 최종 결과 리스트에 차례대로 집어 넣는다. 6. 최종 결과 리스트에 정렬된 값이 전부 들어갔으니 이를 반환한다. 교재에서 쉽게 설명한 병합 알고리즘이다. def merge_sort(a): #리스트a를 입력으로 받음 n=len(a) if n

9-1 일반적인 삽입정렬 알고리즘을 사용해서 리스트[2, 4, 5, 1, 3]을 정렬하는 과정 서술 문제09 삽입정렬 이론공부 포스팅에 자세히 적어놨음. 9-2 정렬 알고리즘을 오름차순에서 내림차순으로 바꿔라. def insert_sort(a): n=len(a) for i in range(1, n): # 1부터 n-1까지 key=a[i] #i번 위치에 있는 값을 key에 저장 j=i-1 #j를 i 바로 왼쪽 위치에 저장 #리스트의 j번 위치에 있는 값과 key를 비교해 key가 삽입될 적절한 위치를 찾음 while j>=0 and a[j] < key: a[j+1]= a[j] #삽입할 공간이 생기도록 값을 오른쪽으로 한칸 이동 j-=1 a[j+1] = key #찾은 삽입 위치에 key를 저장 d = [2,..

def find_ins_idx(r, v): #리스트r, 삽입값v. v가 들어갈 위치를 돌려주는 함수 #이미 정렬된 리스트r의 자료를 앞에서부터 차례로 확인하며 for i in range(0, len(r)): if v < r[i]: #삽입값v가 r[i]보다 작으면 i를 반환해서 r[i]보다 앞에 v를 삽입. #r[i]앞에 v를 놓아야 정렬 순서가 유지된다 return i # i자리에 값을 삽입하면 기존의 i자리의 값은 한자리 뒤로 밀려남. #적절한 위치 못찾은거면 모든 자료보다 삽입값이 큰거니까 제일 뒤에 삽입 return len(r) def ins_sort(a): result = [] #새 리스트 만들기. 결과 저장 while a: #리스트 a에 값이 남아있을 때까지 반복 value = a.pop(0) ..

연습문제 풀기 전에 이전에 못한 선택정렬의 빅오 표기법에 대해 알아보자. 선택정렬의 비교 방법은 리스트 안의 자료를 한번씩 비교하는 방법과 거의 같다. 문제03의 동명이인 찾기와 비슷한 경우다. 0번째 위치는 자신을 제외한 전 위치와 비교하니 n-1번 비교, 1번째는 n-2번 비교. 이런식으로 쭉 가다가 n-2번째의 n-1번째와 1번 비교하게 되고, n-1번째는 비교할 대상이 없으니 0번 비교하게 된다. 정리하자면 이렇게 되는데 위치 비교횟수 0 3 1 2 2 1 3 0 이는 1부터 마지막 수까지 전부 더하는 것과 같기 때문에 n(n-1)/2 공식을 쓸 수 있다. 즉 빅 오 표기법으로 선택정렬은 O(n^2)라고 나타낸다. O(n^2)인 알고리즘이므로 입력 크기가 커질수록 정렬하는 시간이 굉장히 오래 걸리..

쉽게 설명한 선택 정렬 알고리즘 def find_min_idx(a): #최소값 찾기 n=len(a) min_idx=0 #최소값 위치 for i in range(1, n): if a[i]

7-1 찾는 값이 나오는 모든 위치를 리스트로 돌려주는 탐색 알고리즘을 만들어 보세요. 찾는 값이 없다면 빈 리스트를 돌려줍니다. #연습문제 7-1 def search_list_all(a, x): # 탐색 대상 리스트a, 찾는값x result=[] # 반환값 저장용 리스트 n=len(a) for i in range(0, n): if a[i]==x: result.append(i) return result v = [12, 234, 32, 423, 12, 55, 34, 23, 43, 11, 12, 22, 11] print(search_list_all(v, 12)) # [0, 4, 10] print(search_list_all(v, 11)) # [9, 12] print(search_list_all(v, 222)..

def search_list (a, x): # 리스트a, 찾는값x n=len(a) for i in range(0, n): # a[0]부터 a[n-1]까지 탐색. if a[i]==x: return i #값을 찾으면 리스트 내의 위치를 반환함 return -1 v=[17, 32, 21, 2, 32, 52, 12] print(search_list(v, 17)) #0 print(search_list(v, 12)) #6 print(search_list(v, 124)) #-1 이 알고리즘을 보수적인 관점에서, 최악의 경우로 분석하면 리스트 길이가 n일 때 비교가 최대 n번 필요하므로 계산 복잡도는 O(n)이다. 물론 찾는 값이 리스트의 맨 처음에 있을 수 있고 중간에 있을 수도 있지만 일단 보수적인 관점에서 최악의..