이자다의 기록

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

팩토리얼을 구하는 알고리즘 1 def fact(n): f=1 #결과 저장 변수f for i in range (1,n+1): #1부터 n+1 미만까지 f= f*i print(n, f) return f print(fact(1)) print("") print(fact(3)) print("") print(fact(10)) 각 단계마다 무슨 값을 가지는지 보기 쉽게 print함수를 몇개 추가했다. 결과는 아래와 같다. 1 1 1 3 1 3 2 3 6 6 10 1 10 2 10 6 10 24 10 120 10 720 10 5040 10 40320 10 362880 10 3628800 3628800 Process finished with exit code 0 입력n이 1일 때 1에 1을 곱하고 결과는 1. 입력n이 ..

def find_min (a): n=len(a) min_val=a[0] for i in range (1, n): if min_val>a[i]: min_val=a[i] return min_val v=[23,43,64,13,97,43,23,56] print(find_min(v)) 출력은 정상적으로 13으로 나온다

def find_max (a): n=len(a) # 입력받은 리스트의 길이를 변수n에 저장 max_v = a[0] #최대값 변수에 리스트에 첫번째 원소를 넣음 for i in range (1, n): # 0번째 원소는 최대값 변수에 넣었으니 1부터 n-1까지 비교를 반복한다. if a[i]>max_v: # 만약 최대값 변수의 원소보다 값이 큰 변수를 리스트에서 발견한다면 max_v=a[i] # 최대값 변수의 값은 리스트의 해당 원소로 변경한다 return max_v # 반복문이 끝나고 최대값 변수를 반환한다. v=[17, 92, 18, 33, 58, 7, 33, 42] print(find_max(v)) # 출력: 92 위는 리스트의 최댓값을 구하는 프로그램이다. 최댓값 구하기 프로그램의 시간복잡도를 생각..