목록알고리즘/파이썬 알고리즘 (7)

IT's 우

파이썬 자료구조와 알고리즘_스택(Stack), 큐(Queue)

스택(stack)은 배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조다. 스택은 배열 인덱스 접근이 제한되며, 후입선출(last in, first out, LIFO) 구조다. 스택의 동작의 시간복잡도는 모두 O(1)이다. 스택의 동작 - push: 스택 맨 끝(맨 위)에 항목을 삽입한다. - pop: 스택 맨 끝 항목을 반환하는 동시에 제거한다. - top/peak: 스택 맨 끝 항목을 조회한다. - empty: 스택이 비어 있는지 확인한다. - size: 스택 크기를 확인한다. 파이썬에서는 리스트의 append()와 pop() 메서드로 스택을 구현할 수 있다. 큐(queue)는 스택과 다르게 항목이 들어온 순서대로 접근 가능하다. 즉, 먼저 들어온 데이터가 먼저 나가는 선입선출(first in, ..
알고리즘/파이썬 알고리즘 2021. 4. 1. 09:32
파이썬 자료구조와 알고리즘_소수

다음 예제에서는 세 가지 다른 방법으로 한 숫자가 소수(prime number)인지 판단한다. 수수란 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수다. 즉, 약수로 1과 자기 자신만을 가지는 수다. 첫 번째 함수는 브루트 포스(brute force), 즉 무차별 대입 방법을 사용한다. 두 번째 함수는 제곱근을 이용한다. 끝으로 마지막 함수는 확률론적 테스트와 페르마의 소정리(Fermat's little theorem)를 사용한다. #finding_prime import math import random def finding_prime(number): """ brute force(마구잡이/ 무차별 대입 방법) """ num = abs(number) if num < 4 : retur..
알고리즘/파이썬 알고리즘 2021. 3. 14. 13:35
파이썬 자료구조와 알고리즘_피보나치 수열

피보나치 수열(Fibonacci sequence)은 첫째 및 둘째 항이 1이며, 그 이후의 모든 항은 바로 앞 두항의 합인 수열이다. 1 1 2 3 5 8 13 21 ~ 다음 코드들에서 피보나치 수열에서 세 가지 다른 방법으로 n번째 숫자를 찾는다. 제네레이터(generator)를 사용하여 피보나치 수열을 구할 수도 있다. 제네레이터는 파이썬의 시퀀스를 생성하는 객체다. 제네레이터를 이용하며, 전체 시퀀스를 한 번에 메모리에 생성하고 정렬할 필요 없이, 잠재적으로 아주 큰 시퀀스를 순회할 수 있다. 제네레이터를 순회할 때마다 마지막으로 호출된 요소를 기억하고 다음 값을 반환한다. 제네레이터 함수는 yield문을 사용한다. 출처: 파이썬 자료구조와 알고리즘, 미아 스타인 지음 최길우 옮김
알고리즘/파이썬 알고리즘 2021. 3. 13. 12:37
파이썬 자료구조와 알고리즘_random 모듈

난수를 생성하는 random 모듈의 예제 코드를 살펴보자. 난수이므로 출력 결과는 실행 때마다 다르다. 출처: 파이썬 자료구조와 알고리즘, 미아 스타인 지음 최길우 옮김
알고리즘/파이썬 알고리즘 2021. 3. 13. 02:22
파이썬 자료구조와 알고리즘_최대공약수

- 두 정수의 최대공약수(greatest common divisor, GCD)를 계산 # finding_gcd def finding_gcd(a,b): while(b != 0): result = b a, b= b, a % b return result def test_finding_gcd(): number1 = 21 number2 = 12 assert(finding_gcd(number1, number2) == 3) print("테스트 통과!") if __name__ == "__main__": test_finding_gcd() 출처: 파이썬 자료구조와 알고리즘, 미아 스타인 지음 최길우 옮김
알고리즘/파이썬 알고리즘 2021. 3. 13. 02:10
파이썬 자료구조와 알고리즘_진법 변환

- 다른 진법의 숫자를 10진수로 변환한다.(2
알고리즘/파이썬 알고리즘 2021. 3. 13. 01:06
파이썬 자료구조와 알고리즘_fraction 모듈

# testing_floats in page 25 소스코드 from fractions import Fraction def rounding_floats(number1, places): """ 반올림한다""" return round(number1, places) def float_to_fractions(number): """ 부동소수점을 분수로 만든다 """ return Fraction(*number.as_integer_ratio()) def get_denominator(number1, number2): """ 분모를 반환한다.""" a = Fraction(number1, number2) return a.denominator def get_numerator(number1, number2): """ 분자를 반..
알고리즘/파이썬 알고리즘 2021. 3. 12. 21:31
이전 Prev 1 Next 다음