이자다의 기록

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) ..

적게 공부하고 더 많이 배우는 방법 - YouTube 한 심리학자의 강연을 요약한 영상인데 내용을 인상깊게 봐서 숙지하기 위해 블로그에 따로 정리해둔다. 1. 시간 쪼개기 공부를 효율적으로 하기 위한 첫 번째 방법은 시간을 쪼개는 것이다. 대학생들의 평균적으로 25~30분정도 집중을 유지 가능하고 그 이상부터는 집중이 흐트러진다. 공부의 효율은 시작 후 30분 정도에 급격히 집중력이 떨어지고 그 상태로 계속 공부하면 효율이 바닥을 친다. 심리학에서는 보상을 받으면 그걸 더 하게 되고, 처벌을 받으면 그걸 더 안하게 된다는 것이 잘 알려져 있다. 만약 몇시간씩 공부하게 된다면 기분 좋은 공부는 30분 밖에 못하고 그 이후부터는 고통 속에서, 공부를 저주하면서 보내게 된다. 아 수학 진짜 재미없다, 영어 진..

연습문제 풀기 전에 이전에 못한 선택정렬의 빅오 표기법에 대해 알아보자. 선택정렬의 비교 방법은 리스트 안의 자료를 한번씩 비교하는 방법과 거의 같다. 문제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)이다. 물론 찾는 값이 리스트의 맨 처음에 있을 수 있고 중간에 있을 수도 있지만 일단 보수적인 관점에서 최악의..

def hanoi(n, from_pos, to_pos, aux_pos): # from출발점, to도착점, aux중간과정에 사용할 보조기둥 if n==1: print(from_pos, "->", to_pos)#원판 한개를 옮기는 문제면 그냥 옮기면 됨 return hanoi(n-1, from_pos, aux_pos, to_pos) # 출발점에서 중간과정으로 원판n-1개 이동. 도착점 기둥을 이용해서 print(from_pos, "->", to_pos) #가장 큰 원반을 목적지로 이동 hanoi(n-1, aux_pos, to_pos, from_pos) # 중간 기둥에서 도착점 기둥으로 원판 n-1개 이동 print("n=1") hanoi(1, 1, 3, 2) #원판 1개를 1번기둥에서 3번기둥으로 2번기둥을..