이호진

1로 만들기 n이 주어지고 1씩 빼는것과 2,3,...으로 나누는것이 가능할 때, n을 1로만드는 최소 횟수를 구하는 문제 이 문제도 DP를 이용하여 풀 수 있다. x=int(input()) d=[0]*(x+1) for i in range(2,x+1): d[i]=d[i-1]+1 if i%2==0: d[i]=min(d[i],d[i//2]+1) if i%3==0: d[i]=min(d[i],d[i//3]+1) print(d[x]) 먼저 1을 빼는 값을 d에 저장하고 나눌수 있을 때, 나눈 d의 값에 1을 더한값과 비교하여 더 작은값을 저장한다.

가장 긴 증가하는 부분수열이란 부분수열중에서 증가하는부분이 가장 긴 부분을 뜻한다. 예를들어, 10 20 10 30 20 50이라는 수열이 있을 때 10 20 10 30 20 50 진하게 칠해진 부분의 수열을 뜻한다. n=int(input()) arr=list(map(int,input().split())) d=[1]*n for i in range(1,n): for j in range(0,i): if arr[j]

1,000,000 이하의 숫자 두 개를 입력받아 그 사이의 소수를 구하는 알고리즘입니다. 1. m, n을 입력받는다. map(int(input().split()) 이용 2. array의 크기를 1,000,000으로 만들고 True로 초기화 한다. 3. 1은 소수가 아니다. array[1]=False 4. 에라토스테네스의 채를 이용하여 소수를 구한다. 5. 구한 값을 m부터 n+1까지 모두 출력한다. 예를 들어, m=3 n=16일 때, import math m,n = map(int,input().split()) 3 16 array=[True for i in range(1000001)] array[1]=False for i in range(2,int(math.sqrt(n))+1): if array[i]==T..

투 포인터란 2개의 변수를 이용해 리스트 상의 위치를 기록하는 것이다. 부분 합 리스트 [1, 2, 3, 2, 5] 가 주어질 때, 부분 합이 5인경우는 [2, 3], [3, 2], [5] 세 경우이다. 구하는 방법은 1. s와 e를 이용해서 0번째 자리부터 탐색한다. 2. 부분합이 5보다 작으면 e+1 3. 부분합이 5보다 크거나 같으면 s+1 4. 부분합이 5일 때, count 1 증가 n=5 m=5 data=[1,2,3,2,5] count=0 interval_sum=0 end=0 for s in range(n): while interval_sum

소수 소수란 2보다 크면서 1과 자기자신을 제외한 수로 나누어 떨어지지 않는 수이다. ex) 2, 3, 5, 7, 11, ... 1. 소수를 구하기 위해선 x를 2부터 x-1까지 나누어보고 나누어 떨어지는지 확인한다. 만약 나누어 떨어지면 소수가 아니다. def is_Prime(x): for i in range(2,x): if x%i==0: return False return True -> 이 경우에, 2부터 x-1까지 다 확인을 해야하므로 시간복잡도가 높다. O(X) 2. 1에서 소수를 구한 방법처럼 2부터 x-1까지 모두 확인할 필요가 없다. 3. 숫자 16의 경우에 약수는 1, 2, 4, 8, 16이다. 이 경우에 2x8과 8x2 모두 16이므로 대칭이다. 특정한 자연수 x가 소수인지 확인하기 위해..