루껍

피보나치 수 - 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열 ※ 편의상 0번째 항을 0으로 두기도 함. 예시) 1) 반복문을 통한 팩토리얼의 구현 # 반복문을 통한 피보나치 수 구현 # 입력부 n = int(input()) # 0번째, 1번째 피보나치 수를 포함하는 배열 생성 answer_arr = [0, 1] # 반복문을 통해 n을 입력받았을 때, 기존 배열에 n번째 피보나치 수까지 추가 for i in range(n-1): answer_arr.append(answer_arr[1+i] + answer_arr[i]) # 입력받은 n번째 피보나치 수 출력 print(answer_arr[n]) 2) 재귀함수를 통한 팩토리얼의 구현 # 재귀함수를 통한 피보나치 수 구현 def F..

팩토리얼(계승) - 그 수보다 작거나 같은 모든 양의 정수의 곱 예시) 3! = 3 × 2 × 1 4! = 4 × 3 × 2 ×1 1! = 1 ※ 0! = 1 재귀함수 - 함수의 정의 단계에서 자신(함수)을 참조하는 함수 1) 반복문을 통한 팩토리얼의 구현 # 반복문을 통한 팩토리얼 구현 N = int(input()) result = 1 for i in range(N, 0, -1): result = result*i print("{0}! = {1}".format(N, result)) 2) 재귀함수를 통한 팩토리얼의 구현 # 재귀함수를 통한 팩토리얼의 구현 def factorial(x): if x == 0: return 1 else: answer = x*factorial(x-1) # 함수호출부(아래 모식도 ..

소수(prime number) : 1보다 큰 자연수 중, 1과 자신만을 약수로 갖는 수  방법 1)-해당 수가 소수인지 아닌지를 판별하는 함수 선언을 통해 소수로 구성된 배열 생성 # 코드실행 시간을 측정하기 위해서 time이라는 외부라이브러리를 불러옴import time# start라는 변수에 코드실행 시작 시각 값 저장start = time.time()# 입력 받은 값이 소수인지 판별하는 함수 선언def prime(x): # tf라는 변수 선언 tf = 0 # 반복문을 통해 입력받은 값을 나눠봄, 단 한번이라도 조건문을 만족할 경우, # 입력받은 수(x)는 소수가 아니므로, 이를 나타내기 위해 tf라는 변수에 1을 지정 for i in range(2, x): ..

이번 포스팅은 앞선 백준 9020번, 골드바흐 파티션 출력 알고리즘의 개선방법에 대해 다뤄보겠습니다. 처음 코드와 한계 및 개선 방향은 아래의 링크에서 확인하실 수 있습니다. [Python] 백준 9020번 '골드바흐의 추측' 알고리즘 -1문제 골드바흐의 추측 - '2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다' 4 이상의 짝수를 입력받고, 그 짝수를 두 소수의 합으로 출력하는 알고리즘을 구현하시오. 만약 골드바흐 파티look-up-onceaday.tistory.com 처음 코드에서는 모든 예제 값들에 대해서 출력은 정상적으로 되지만, '실행 시간' 문제에 따른 백준에서의 '시간 초과'가 문제였습니다. 이를 해결하기 위해서 먼저 두 가지 방법을 시도해보았습니다. 1) 자료구조의 변형   데이터..

문제 골드바흐의 추측  -  '2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다'4 이상의 짝수를 입력받고, 그 짝수를 두 소수의 합으로 출력하는 알고리즘을 구현하시오. 만약 골드바흐 파티션(하나의 짝수를 두 소수의 합으로 나타내는 표현)이 여러개인 경우, 두 소수의 차이가 가장 작은 파티션을 출력하시오 초기 idea 문제에서 4이상 10000 이하의 짝수를 입력받으므로, 10000 이하의 소수로 구성된 리스트를 생성한다. 이를 위해 소수인지 아닌지를 판별할 수 있는 함수를 선언한다. 앞서 생성한 소수 리스트내에서 이중 반복문을 활용하여 입력받은 짝수에 대한 파티션을 반환하는 함수를 선언한다. 만약 파티션이 여러개인 경우, 문제의 조건에 따라 두 소수의 차이가 가장 작은 파티션을 반환한다. 한계 ..

문제  N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오. 초기 idea '수학적 관계식을 통한 프로그램 구현' 문제가 주어진 수열의 합을 구하는 것이 아니라, 합과 수열을 구성하는 수의 개수를 통해 수열을 출력하는 것이었다.먼저, 수학문제를 풀듯이 수열의 합(N)과 수의 개수(L) 그리고 각 수의 수학적 관계를 알아보았다. 길이가 L로 고정된 경우, 어렵지 않게 수학적 관계를 알 수 있었고, 이를 프로그램화하는 것은 어렵지 않았다. 하지만 문제는 길이가 적어도 L인 가장 짧은 리스트, 즉, 길이가 L보다 클 수도 있다는 점이었다.기존의 방법(수학적 관계를 통한 알고리즘 구현)을 살리면서, 이를 프로그램화 하는데 꽤 많은 시..

우연히 스도쿠 풀이 알고리즘에 대해 접하게 되었습니다. 저는 전공자도 아니고, 코딩이라고는 관측 데이터를 가시화하거나 수치계산의 맛보기만 봤었던지라..얕은 지식으로 프로그램을 구현했음을 미리 알려드립니다. 제가 스도쿠 풀이 알고리즘에 대해서 서치를 하는 과정에서 가장 많이 볼 수 있었던 키워드는 'back tracking' 이었습니다.아마 이 포스팅을 보시는 분들도 대부분 같을 것이라 생각합니다. back tracking method에 대해서 깊게 알아본 것은 아니지만, 설명 중에 언급되는 생소한 단어들에.. '한번 내가 알고 있는 지식과 기술로 한번 구현해보자! 라는 생각으로 시작했습니다. 처음에 생각했던 방법은 python의 sympy 라이브러리를 활용하여, 스도쿠 빈칸에 미지수를 할당한 뒤, 연립방..