이자다의 기록

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번기둥을..

# 연습문제 5-1 n번째 피보나치 수를 구하는 알고리즘을 재귀호출을 이용해서 구현해 보시오. def fibo (n): if n==0: return 0 if n==1: return 1 return fibo(n-1) + fibo(n-2) print(fibo(7)) #결과 13 print(fibo(10)) #결과 55 #재귀호출 문제는 자신없어서 암담했는데 일단 배운대로 종료조건 설정하고 고민해보다가 #문제 힌트의 (7번값 = 5번값 + 6번값) 을 보고 대강 감을 잡고 풀었다. #이번 재귀호출은 그림으로 표현하자면 트리 구조처럼 된다. #fibo(5)를 호출하면 (4)와 (3)이 호출되고, (4)는 (3)과 (2)를 호출하고, (3)은 (2)와 (1)을 호출한다. #이렇게 하나의 함수가 두개의 함수를 호출..

def gcd(a,b): # Greatest Common Divisor, GCD, 최대공약수 i = min(a,b) # a, b 중 최솟값 i를 구한다. i가 최대공약수인지 검사한다. while True: # 반복문의 실행조건이 True라서 중간에 강제로 중지시키지 않는 한 계속 돌아간다. if a%i==0 and b%i==0: # i가 최대공약수라면 함수를 끝내버리는 것으로 반복문도 끝내버림. return i i = i-1 # i가 최대공약수가 아니면 1 줄이고 다시 돌린다. print(gcd(1, 5)) #결과 1 print(gcd(3, 6)) #결과 3 print(gcd(60, 24)) #결과 12 print(gcd(81,27)) #결과 27 print(gcd(232, 112)) #결과 8 def ..

# 연습문제 4-1. 1부터 n까지의 합 구하기를 재귀호출로 만들기. def re_sum_n (n): if n l[n-1]: # n=2일때 맨 처음값을 최댓값으로 두고 맨 끝값을 차례대로 비교. print("n = ", n, "max_n = ", max_n, "max_n이 다음위치의 원소보다 값이 더 커서 max_n은 그대로 유지") return max_n else: print("n = ", n, "max_n = ", max_n, "max_n의 다음자리가 값이 더 커서 다음자리 값을 반환") return l[n-1] #맨 처음값을 최댓값으로 가정하고 다음값과 비교한 후, 리스트의 길이를 1씩 늘임과 동시에 비교할 리스트 끝자리의 원소도 한자리씩 넘어가며 최댓값과 차례대로 비교. #최댓값, 비교하는 수: ..