코딩테스트

문제 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 코드 My answer import random from itertools import permutations n=int(input()) answer,tanswer=0,0 tmp=list(map(int,input().split())) for i in permutations(tmp,n): for j in range(len(i)): if(j!=len(i)-1): tanswer+=abs(i[j]-i[j+1]) answer=max(tanswer,answer) tanswer=0 p..

문제 [Python] 백준 #9465- 스티커 문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 changsroad.tistory.com 재풀이하여 올렸습니다.~ 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 코드 My answer(시간초과) import sys t=int(sys.stdin.readline()) for i in ran..

문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 코드 My answer from sys import stdin n = int(stdin.readline()) dp=[[0,0] for i in range(n+1)] dp[1]=[0,1] for i in range(2,n+1): dp[i][0]=dp[i-1][0]+dp[i-1][1] dp[i][1]=dp[i-1][0] print(sum(dp[n])) Another answer a=b=1 for _ in range(int(input())-2): a,..

문제 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 코드 My answer from sys import stdin n = int(stdin.readline()) tmp=[i for i in range(1,10)] dp= [[0] * 10 for _ in range(n + 1)] dp[0]=[1,1,1,1,1,1,1,1,1,1] for i in range(1,n+1): for j in range(0,10): if(j==0): dp[i][j]=dp[i-1][j] else: dp..

문제 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 코드 Another answer from sys import stdin n = int(stdin.readline()) stairs = [[0] * 10 for _ in range(n + 1)] stairs[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] for i in range(2, n + 1): # 계단 수가 0으로 끝나는 경우 stairs[i][0] = stairs[i - 1][1] # 계단 수가 9로 끝나는 경우 stairs[i][9] = stairs[i - 1][8] # 계단 수가 1~8로 끝나는 경우 for j in range(1, 9): sta..

동적프로그래밍을 단순하게 설명하면 큰 문제를 작은문제로 나누어 푸는 방법이다. 단 작은문제들이 계속 반복되어야 한다. 바뀌면 안된다. 동적프로그래밍에서는 메모이제이션(Memoiztion)이라는 방법을 쓰는데 이름에서도 유추할 수 있듯이 메모를 하듯 작은문제들의 답을 기억하여 사용하는 것이다. 동적프로그래밍의 가장 쉬운 예시 피보나치 수를 예로 들어보자. 피보나치 수의 공식은 아래와 같다. 위 처럼 F2를 구하기 위해서는 F1,F0이 필요하고, F3을 구하기 위해서는 F2, F1이 필요하다. 위의 저 공식처럼 계속해서 반복이 일어나며 공식을 찾기만하면 구할 때 마다 정답이 같다. 이렇듯 점화식같이 이전항과 다음항과의 관계를 알아내서 값을 기억하면서 다음 값을 찾아내는 것이 동적프로그래밍이다. 동적프로그래밍..