이자다의 기록

연습문제 풀기 전에 이전에 못한 선택정렬의 빅오 표기법에 대해 알아보자. 선택정렬의 비교 방법은 리스트 안의 자료를 한번씩 비교하는 방법과 거의 같다. 문제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씩 늘임과 동시에 비교할 리스트 끝자리의 원소도 한자리씩 넘어가며 최댓값과 차례대로 비교. #최댓값, 비교하는 수: ..

3-1 n명 중 두 명을 뽑아 짝을 짓는다고 할 때 짝을 지을 수 있는 모든 조합을 출력하는 알고리즘을 만들어 보세요. #연습문제 3-1 def find_partner(n): t=len(n) result=set() for i in range(0, t-1): for j in range (i+1, t): print(n[i], "-", n[j]) listA=["Tom", "Jerry", "Mike", "Roll", "Kim", "Oirat", "Hudson"] find_partner(listA) 실행 결과: Tom - Jerry Tom - Mike Tom - Roll Tom - Kim Tom - Oirat Tom - Hudson Jerry - Mike Jerry - Roll Jerry - Kim Jerry -..

def find_same_name (a): n=len(a) #리스트a의 길이 저장 result=set() #결과 저장할 빈 집합 생성 for i in range (0, n-1): #비교 기준을 선정하는 반복문 for j in range (i+1, n): #비교 대상을 선정하는 반복문, i+1이 아니라 1을 사용하면 첫 바퀴는 괜찮지만- if a[i]==a[j] : #다음바퀴에 비교 기준이 넘어가도 비교 대상은 첫바퀴와 동일하므로 원하는 결과가 나오지 않는다. result.add(a[i]) # 중복된 이름이 나오면 집합에 추가한다. return result name=["Tom", "Jerry", "Mike", "Tom"] print(find_same_name(name)) name2=["Tom", "Jerr..