1. 문제 [3, 6, 2, 6, 7, 5, 2] 와 같이 숫자들이 주어졌을 때, 다음 질의에 대해 답하는 프로그램을 작성해보세요. 단, 질의마다 하나의 숫자가 주어지며 해당 번째 숫자를 제외한 다른 숫자들에 대해 인접한 숫자간의 차이의 합을 구해야 합니다. 예를 들어 질의로 5가 주어졌다면 5번째 숫자인 7을 제외한 다른 숫자들을 나열하면 [3, 6, 2, 6, 5, 2]가 되므로 인접한 숫자간의 차이의 합은 |3 - 6| + |6 - 2| + |2 - 6| + |6 - 5| + |5 - 2| = 15가 됩니다. 이때 주어지는 숫자는 1초과 N 미만임을 가정해도 좋습니다. -------------------------------------------------------------------------..
1. 피사노 주기 피보나치 수열을 자연수 n으로 나눈 나머지가 일정한 주기를 이룬다는 것을 1960년 IBM의 한 직원이 증명했다 예를 들어 0,1로 시작하는 피보나치 수열을 3으로 나눈 나머지는 위와 같이 0,1,1,2,0,2,2,1이 반복된다는 것을 알 수 있다 2. 연습문제 9471번: 피사노 주기 (acmicpc.net) 9471번: 피사노 주기 첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. www.acmicpc.net 추가로 몇가지 성질이 있다고 제시해주는데 어쨌든 이 문제는 피보나치 수열을 자연수 m으로 나눈 나머지가 주기를 이룬다는 사실을 알고 코딩을 해서 반복되는 수열의 길이를 ..
1. 문제 1520번: 내리막 길 (acmicpc.net) 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 2. 풀이 이 문제에서 핵심은 "어떤 칸을 최초 방문할 때 해당 칸에서 목적지까지 도달할 수 있는 경우의 수에 대한 정보를 기록해 놓고, 다음 방문 시 기록된 값을 참조해서 반복된 연산을 피하는 것이다" dp[y][x]를 (x,y)에서 (n-1,m-1)까지 조건에 맞는, 도달하는 경우의 수라고 정의하자. m,n = map(int,stdin.readline().split()) maps = [list(map(in..
1. 문제 25418번: 정수 a를 k로 만들기 (acmicpc.net) 25418번: 정수 a를 k로 만들기 7(A), 8(연산 1), 9(연산 1), 18(연산 2), 19(연산 1), 38(연산 2), 76(연산 2), 77(연산 1)이 최소 연산이므로 정답은 7이다. www.acmicpc.net 정수 a에 1을 더하거나 2를 곱해서 k를 만들때, 연산 횟수의 최솟값을 구하는 문제 2. 풀이1(BFS) 이 문제의 기본은 BFS로 푸는 것이다 정수 a에서 시작해서, delta 배열은 1,2가 있고 1이 나오면 a + 1에 가서 범위를 벗어난건지, 이미 방문했는지 검사 2가 나오면 2a에 가서 범위를 벗어난건지, 이미 방문했는지 검사 from collections import deque def bfs(..
1. 문제 14501번: 퇴사 (acmicpc.net) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 15486번: 퇴사 2 (acmicpc.net) 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 주어진 일정표에 상담기간과 해당 상담을 완료하면 얻는 이익이 주어진다. N+1일에 퇴사할려고 할때, 그 전에 최대이익을 얻도록 상담을 끝내고 싶다. 가능한 최대이익을 구하는 프로그램을 작성해본다면..? 2. 풀이 예전에 푼 수영..
1. 문제 https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 주어진 수열의 점화식에서 A[N]을 구하는 문제 2. 풀이 처음에 그냥 이게 문제?하면서 점화식 그대로 작성했는데 메모리 초과남.. from sys import stdin n,p,q = map(int,stdin.readline().split()) dp = [0]*(n+1) dp[0] = 1 for i in range(1,n+1): dp[i] = dp[i//p]+dp[i//q] print(dp[n]) n의 최대 범위는 $10^{12}$인데 메모리 제한은 128mb라서 그런 것 같다 근데 dp[n]을 구할려면, dp[n//p]와 d..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
