본문 바로가기

Python/Do it Python6

Python 재귀 알고리즘 재귀(recursion)는 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 이용하여 정의되는 경우를 의미합니다. 재귀를 효과적으로 사용하면 프로그램을 간결하고 효율성 좋게 작성할 수 있습니다. 재귀를 사용하는 대표적인 예로 양의 정수 곱을 구하는 팩토리얼(factorial) 문제가 있습니다. 팩토리얼은 양의 정수를 순서대로 곱한다는 의미로 순차 곱셈이라고도 합니다. 팩토리얼 n! 의 정의(n은 양의 정수)는 1) 0!=1 2) n>0이면 n!=nx(n-1)! #factorial.py factoial함수는 매개변수 n에 전달받은 값이 0보다 크면 n*factorial(n-1)의 값을 반환하고, 그렇지 않으면 1을 반환합니다. 파이썬에서는 팩토리얼 값을 구하는 표준 라이브러리로 math모듈에서 fa.. 2021. 8. 10.
Python Stack,Queue 스택(stack)은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 LIFO 방식입니다. 데이터를 넣는 작업을 푸시(push), 데이터를 꺼내는 작업을 팝(pop), 푸시와 팝이 이뤄지는 윗부분을 꼭대기(top)이라 하며 아랫부분을 바닥(bottom)이라고 합니다. 스택 배열은 stk, 푸시한 데이터를 저장하는 스택 본체인 list형 배열입니다. 인덱스가 0인 원소를 스택의 바닥이라고 하고, 가장 먼저 푸시하여 데이터를 저장하는 곳은 stk[0]입니다. 스택 크기는 capacity, 스택의 최대 크기를 나타내는 int형 정수이고 이 값은 배열 stk의 원소 수인 len(stk)와 일치합니다. 스택 포인터는 ptr, 스택에 쌓여 있는 데이터의 개수를 나타내는 정숫값을.. 2021. 8. 8.
Python 검색 알고리즘 선형 검색이란(Linear search) 직선 모양으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘입니다. 배열 맨 앞부터 순서대로 원소를 스캔하는 원소의 값이 정해지지 않은 배열에서 검색할 때 사용하는 유일한 방법이다. #ssearch_while.py for i in range(len(a)): 이진 검색(binary search)은 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘입니다. 이진 검색 범위는 맨 앞, 맨 끝, 중앙의 인덱스를 각각 pl, pr, pc라고 한다면 값은 0, n-1, (n-1)//2로 초기화시킵니다. 하나씩 이동하여 검색하는 선형 검색과 달리 주.. 2021. 8. 7.
Python 알고리즘 자료구조와 배열(하) max로 정의된 max.py() 함수를 사용할 수 있도록 import를 통해 가져오고, 난수를 뽑기 위해서 random 도 함께 import 하였습니다. from [가져올 모듈=파일 이름]에서 max_of() 함수를 import 하겠다는 의미이고, x라는 빈 리스트를 입력할 개수만큼 공간 None으로 만듭니다. 그 후 random.randint(low,high)를 통해 최솟값과 최댓값 사이의 값 중 1개를 뽑게 한 후, for 문을 통해 입력할 개수만큼 작동시키면 가져온 max_of() 함수를 사용해 원하는 값을 뽑아낼 수 있습니다. 배열 원소를 역순으로 정렬하는 알고리즘을 생각해봅시다. 예로 배열 a의 원소가 7개이고 [2,5,1,3,9,6,7]로 저장되어 있다면 이것.. 2021. 7. 21.
Python 알고리즘 자료구조와 배열(상) 자료구조의 개념은 논리적인 관계로 이루어진 데이터 구성을 말합니다. 즉 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계를 얘기합니다. 자료구조를 알아야 하는 이유는 컴퓨터에서 처리해야 할 많은 데이터를 모아 효율적으로 관리하고 구조화하는 데 있다. 하나의 값을 저장하는 변수가 아니라 묶음 단위로 값을 저장하는 자료구조 중 배열(array)이 있습니다. 배열에는 객체가 저장되고, 배열에 저장된 객체 하나하나를 원소(element)라고 합니다. 또한 각 원소는 0,1,2,… 순으로 인덱스(index)를 부여받습니다. 배열을 사용하면 좋은 점은 대표적으로 아래와 같이 2가지가 있다. 1. 배열을 생성할 때 원소 개수를 자유롭게 지정할 수 있다. 2. 인덱스를 이용하여 원소에 접근할 수 있어 편하다.. 2021. 7. 18.
Python 알고리즘 기초 알고리즘이란? 알고리즘은 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것을 의미한 것, 계산을 실행하기 위한 단계적 절차를 의미한다. 즉 문제 해결에 필요한 계산 절차 또는 처리과정의 순서를 뜻하며 프로그램 명령어의 집합을 의미하기도 한다. 현재 DO IT 자료구조와 함께 배우는 알고리즘 입문, 저자 BohYoh Shibata의 책으로 공부를 하고 있고, 터득한 지식을 정리해서 올릴 것이다. 파이썬이 아직 생소한 부분이 많아 쉬운 부분 또한 함께 정리하려 한다. 1) while 문을 이용한 합계 구하기 while i 0: break cf) // -> 몫 연산자, %-> 나눗셈 연산자 아래는 a와 b를 오름차순으로 정렬하는.. 2021. 7. 15.

티스토리툴바