반응형 자료구조및알고리즘35 (Python)재귀함수 재귀함수 재귀함수는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 내부적으로 반복하다, 일정한조건을 만족하면 함수를 이탈하여 결과를 도출한다. 문제 풀이에서 DFS를 구현하는 가장 기본적인 방법으로 널리 사용되므로 잘 알아야 하고 쉽게 벽을 느낄수 있다. 재귀의특성 - 재귀는 같은 일을 하는 함수끼리 상태만 달리하여 호출한다. - 무슨 일을 했는지는 중요하지 않다. - 재귀호출이 무한히 발생할수 있다. (점화식) def recursive(): print("이것은 재귀함수입니다.") recursive() recursive() #함수 호출 이렇게 되면 무한히 출력된다. def recursive(count): if count == 0: return print("이것은 재귀함수입니다.") count -= 1 .. 2022. 5. 19. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다. 이 방법은 마치 체로 치듯이 수를 걸러낸다. 코드: def prime_list(n): # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * n m = int(n ** 0.5) # 제곱근 for i in range(2, m + 1): if sieve[i] == True: # i가 소수인 경우 for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정 sieve[j] = False # 소수.. 2022. 5. 16. 다이나믹프로그래밍(DP) 다이나믹 프로그래밍(동적 계획법) 동적 프로그래밍은 하위 문제가 겹치고 최적의 하위 구조 속성이 있는 문제 클래스를 효율적으로 해결하는 데 도움이 되는 컴퓨터 프로그래밍 기술이다. 즉, 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하여 다시 큰 문제를 사용하는 것이다. DP 는 재귀방식과 아주 유사하다. 큰 차이점은 일반적인 재귀를 사용시 동일한 작은 문제들이 여러번 반복돼 비효율적 계산이 된다. 예시로는 피보나치 수열이다 피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 f(n) = f(n-1) +f(n-2) 식이 나온다 중복돼서 쓰이는 함수가 많은게 보이고 시간복잡도 또한 O(n^2) 이다. def fibo(x): # 피보나치 함수 생성 if x==1 or x==2: # retu.. 2022. 5. 16. Greedy-Algorithm (탐욕 알고리즘) Greedy-Algorithm 탐욕 알고리즘은 현재 사용 가능한 최상의 옵션을 선택하여 문제를 해결하는 접근 방식 하향식 접근 방식으로 작동한다. 이 알고리즘은 모든 문제에 대해 최상의 결과를 생성하지 않을 수 있다. 문제에 다음 속성이 있는 경우 사용할 수 있는지 여부를 결정할 수 있다. 1. 그리디 초이스 속성 한 번 선택한 이전 단계를 다시 고려하지 않고 각 단계에서 최선의 선택을 선택하여 문제에 대한 최적의 솔루션을 찾을 수 있다면 탐욕적인 접근 방식을 사용하여 문제를 해결할 수 있습니다. 이 속성을 탐욕 선택 속성이라 한다. 2. 최적의 하부구조 문제에 대한 최적의 전체 솔루션이 하위 문제에 대한 최적의 솔루션에 해당하는 경우 탐욕적인 접근 방식을 사용하여 문제를 해결할 수 있다. 이 속성을 최.. 2022. 5. 16. (Python)Iterable 한 자료형 List, Tuple, Dictionary, Set Python 의 가장 큰 장점인 Iterable Python 에서 Iterable하다 의미는 "반복 가능한" 을 의미, 즉 객체에 적용되는 의미 반복 가능한 데이터 타입은 순서형 및 컬렉션 자료형 반복 가능한 데이터 타입은 하나하나를 개별로 리턴할수 있음 Python 에서 iterable 한 객체로 생성된 객체를 "iterator"로, iterator로 생성된 함수를 "generator" 라 칭함 Python의 대표적인 iterable 자료형은 List, Tuple Dictionary, Set List 숫자 모음을 숫자나 문자열로 표현하기 쉽게 해줌 추가 수정 삭제가 자유로움 문자열처럼 인덱싱과 슬라이싱이 가능함 a = [1,2,3] a[0] = 1 출처:https://wikidocs.net/14 Tup.. 2022. 5. 11. 이전 1 ··· 3 4 5 6 다음 반응형
