본문 바로가기

분류 전체보기60

파이썬 N까지의 소수 개수 구하기 파이썬에서 1 ~ N까지의 소수 개수를 구할때는 아래와 같이 작성할 수 있다. n = int(input()) result = [] for i in range(2, n + 1): temp = [] for j in range(1, i + 1): if i % j == 0: temp.append(j) if len(temp) == 2: result.append(i) print(len(result)) 하지만 위 코드는 각 숫자마다 모든 약수를 구하고, 그 약수의 개수를 확인하는 부분이 시간 복잡도를 크게 증가시킨다. 해당 문제를 해결하기 위해서는 에라토스테네스의 체를 이용하면 된다. 에라토스테네스의 체는 임의의 수 n 에 대해서 그 이하의 소수를 모두 찾는 간단하면서 빠른 방법이다. 먼저 임의의 수를 100이라고 ..
파이썬 두 수의 최소공배수 최소공배수는 두 수에 서로 공통으로 존재하는 배수 중 가장 작은 수를 뜻한다. 파이썬 코드로 구현해보면 a, b = map(int, input().split()) for i in range(1, a * b + 1): if i % a == 0 and i % b == 0: print(i) break 위와 같이 간단하게 구할 수 있다. 하지만 해당 코드는 숫자가 커질수록 코드의 효율이 떨어진다. 최소공배수를 빠르게 찾기 위해선 유클리드 호제법을 사용할 수 있다. 유클리드 호제법이란 간단히 말해 두 수의 최대 공약수를 구하는 방법이다. 자세히 말하면 두 정수 (a > b > 0)에 대하여 a = bq + r (0
Python 클래스와 객체 클래스는 같은 객체들을 만들 수 있는 틀이고 객체는 만들어진 결과물이다. ● 클래스 선언 class 클래스명: 코드 파이썬에서 클래스의 선언은 위와 같이 한다. ● 생성자 함수 class identity: def __init__(self, name, sn, address): self.name = name self.sn = sn self.address = address 위 클래스는 이름, 주민번호, 주소를 갖은 객체를 생성할 수 있는 identity 클래스이다. __init__ 함수는 생성자 함수이며 객체가 생성시 1회 호출되는 함수이다. 함수의 인자값인 self는 항상 첫번째에 넣어주며 해당 객체를 의미한다. 그 이후에 오는 것은 멤버 변수라고 한다. 객체 생성시에 값을 넘겨받으며 self를 통해 해당 ..
Python 튜플 튜플(tuple)은 클래스와 같이 새로운 형태를 정의할때 사용한다. 크게 복잡하지 않다면 class를 사용하지 않고 tuple을 사용하는 경우가 있다. ● 튜플 선언 def onetwo(): return 1, 2 print(onetwo()) 출력 결과 (1, 2) 위의 코드에서 (1, 2) 에 해당하는 것이 tuple이다. 튜플은 리스트와 비슷하지만 크게 2가지 차이점이 있다. 첫번째는 튜플은 값을 수정할 수 없다는 것이다. 두번째는 튜플은 값을 추가하거나 기존 값을 제거할 수 없다는 것이다. 튜플은 immutable하다. ● 패킹과 언패킹 튜플이 immutable하기 때문에 활용도가 적을 것 같지만, 사실 튜플의 주 역할은 패킹과 언패킹이다. def onetwo(): return 1, 2 a, b = ..
Python 정렬 ● 리스트 정렬 파이썬에서 리스트를 정렬할 때는 sort(), sorted() 등 내장 함수를 이용한다. ● 숫자 리스트 정렬 ● sort() arr = [2, 4, 1, 5, 3] arr.sort() print(arr) 출력 결과 : [1, 2, 3, 4, 5] sort()의 default는 오름차순이다. 내림차순으로 정렬하고 싶다면 sort()내부에 reverse=True 코드를 추가하면 된다. arr = [2, 4, 1, 5, 3] arr.sort(reverse=True) print(arr) 출력 결과 : [5, 4, 3, 2, 1] ● sorted() sorted 함수는 sort함수와 다르게 정렬된 리스트를 반환하는 함수이기 때문에 반환한 리스트를 변수에 할당해줘야 한다. arr = [2, 4, ..
Python 재귀함수 만약 N개의 줄에 걸쳐서 hello world를 출력하는 코드를 함수를 이용하여 작성한다면 다양한 방법이 있다. N = int(input()) def func(): for i in range(N): print("hello world") func() 위와 같이 한번의 함수 호출에서 반복문을 사용하여 출력하게 할 수 있고 N = int(input()) def func(N): if N == 0: return func(N- 1) print("hello world") func(N) 위와 같이 함수 내부에서 함수를 다시 호출하여 한번의 함수 호출마다 한번씩 출력되게 작성할 수 있다. 위와 같은 구조(호출한 함수 내부에서 호출한 함수를 다시 호출)로 작성된 함수를 재귀함수라고 한다. 재귀함수를 사용할때는 if N =..

티스토리툴바