알고리즘 with 파이썬

밍·2022년 6월 4일

공부

목록 보기

4/4

알고리즘의 조건

입력(0개 이상의 입력)
출력(1개 이상의 출력)
명확성
유한성(무한 루프 x)
유효성(실행 가능)

◾ 유클리드 알고리즘

: 두 수의 최대 공약수를 구하는 방법

def gcd(a,b):
    while b!= 0:
        r = a%b
        a = b
        b =r
    return a

예시)
a = 60, b = 28
a > b 이므로
a % b = 4
a = 28, b = 4
28 % 4 = a % b = 0
a = 4, b =0
return a = 4 = 최대 공약수

◾ 약수와 최대 공약수

생능출판 파이썬 알고리즘 연습문제 풀이

연습문제 2번

#연습문제 
#2.약수와 최대 공약수

def gcd(a,b):
    while b !=0:
        r = a%b
        a=b
        b=r
    return a

def g(a):
    c= list()
    for i in range(1,a+1):
        if a%i==0 :
          c.append(i)
    return c

a=60
print("{}의 약수 = {}".format(a, g(a)))

b=28
print("{}의 약수 = {}".format(b, g(b)))

print("{}과 {}의 최대 공약수 = {}".format(a,b, gcd(a,b)))

len과 range

리스트 n의 길이 len(n)
range()는 이터러블 객체를 반환하는 함수이다.
이터러블 객체란 list, str, tuple이 있다.

◾ 파이썬에서의 스택과 큐

스택_후입선출 LIFO

: 리스트 구조 (삽입) append, (삭제) pop() 또는pop(-1)

큐_선입선출 FIFO

: 큐 모듈 queue을 제공하는 파이썬.
(삽입) put, (삭제) get

import queue
Q =queue.Queue(maxsize = 20)
S = queue.LifoQueue(maxsize = 20)

Q.put(2) 
# 큐에 enqueue
S.put(2) 
# 스택에 push

val_q = Q.get(0)
# 큐에 dequeue
val_s = S.get(0) 
# 스택에 pop

◾ 파이썬에서의 집합

집한(set)은 우선순위가 없고 중복을 허용하지 않는다.
S = {a,b,c,d,...}
합집합 : union
교집합 : intersection
차집합 : S1 - S2

s1 = {1,2,3,4,5}
s2 = {2,3,4,6}

print(s1.union(s2))
# {1,2,3,4,5,6}
print(s1.intersection(s2)) 
# {2,3,4}
print(s1 - s2) 
# {1,5}

◾ 파이썬에서의 맵

map 또는 dictionary : 탐색을 위한 자료구조
키-값의 쌍을 가지는 엔트리의 집합이다.
color = {'red':(20,1,2), 'green':(1,2,3,4)}

map = {'만두':('비비고', '마포만두'), '고기':('소고기', '돼지고기', '닭고기')}

map['만두'] = '김밥천국'
map.update({'라면':('신라면', '진라면')})
print(map)
print('과자' in map)

"""
출력 :
{'만두':'김밥천국', '고기':('소고기', '돼지고기', '닭고기'), '라면':('신라면', '진라면)}
False
"""

◾ 사용자가 입력하는 리스트

#연습문제 
#18.사용자가 입력하는 리스트


n = input("노드의 개수 : ")

l = list(n)
a= []

for i in range(1,int(n)+1) :
    i +=1
    print("노드 #{} 데이터 : ".format(n), end="" )
    a.append(int(input()))

print("리스트의 내용 : {}".format(a))