링크 : https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 소요시간: 실패 설계하기(접근방법) 1. 테스트 케이스와 리스트를 입력받는다 2. 알고리즘 해석 일반적으로 계속 대각선을 더해 나간다 리스트를 dp1, dp2 로 선언한다 1) 고려해야 할 사항 中 복잡한 것은 다음 대각선의 수를 포기하고, 다다음 대각선의 수를 더하는 경우, 선택을 하지 않고 넘어가는 경우의 수가 있다. 200 20 40 120 10 60 -> 200 +..
링크 : https://www.acmicpc.net/problem/22857 22857번: 가장 긴 짝수 연속한 부분 수열 (small) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 문제 소요시간: 45분 10초, 다른 분의 풀이 참고로 재도전 설계하기(접근방법) 내 풀이 (pypy3에서만 통과) 1. n, k, s(리스트를 입력받는다) 2.알고리즘 해석 1) 입력받은 리스트를 짝수는 +1, 홀수는 -1로 바꾸어 준다 2) 처음 원소부터 반복문으로 검사한다 검사내용 : 만약 원소가 짝수라면[+1] cnt(짝수개수)에 1을 더해준다 만약 원소가 홀수라면[-1] check(삭제 가능한 홀수 개수) 에서..
링크 : https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 문제 소요시간: 15분 30초 설계하기(접근방법) 1. n과 arr를 입력받는다 2. 알고리즘 해석 1) 현재 dp값을 저장하는 법 i = 0일 때, 현재 값 저장 i > 1일 때, 이전의 dp와 비교한다. 증가하는 수열이기 위해서는 현재 arr[i](ex:60)의 값이 이전 arr(ex:1, 2, 50)값보다 커야 한다. ->..
링크 : https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 소요시간: 17분 5초 설계하기(접근방법) 1. n을 입력받는다 2. 알고리즘 해석 1) 중간에 음수가 나와도, 연속된 수의 합이 0 이하로 떨어지지 않는 이상, 계속 더해나가는 것이 이득이다 ex) 1,2,3,-2,3,5 -> 1 3 6 4 7 12 2) 하지만 0이하로 떨어지는 경우 그 자리에서 덧셈을 멈춰야 한다 i: ex) 1 2 3 -8 1 2 -> 1 3 6 -2 -1 1 i이 경우..
링크 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 소요시간: 실패 설계하기(접근방법) 1. 수열 크기와 수열을 입력받는다 2. 알고리즘 해석 이전의 값들과 비교하여, 자신보다 작은 수(중복되지 않은)들의 집합 + 자신의 수를 더한 것이 가장 긴 부분 증가수열이다 ex) 30 -> 10,20 + 30 -> 3 ex) 50 -> 10,20,30 + 50 ->..
링크 : https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 문제 소요시간: 6분 30초 설계하기(접근방법) 1. n과 m을 입력받는다 2. 동적 계획법으로 풀어보자 dp를 n+1개 만큼 생성한 후 팩토리얼을 생성하기 위해서 dp[n] = dp[n-1] * n 을 반복해준다 3. 조합식 형식에 맞추어 출력해준다 코드(출력) n, m = map(int, input().split()) dp = [0] * (n + 1) dp[0] = 1 dp[1] = 1 for i in range(2, n + 1): dp[i] = i * dp[i - 1] comb = dp[n] // ..
링크 : https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 소요시간: 15분 20초 설계하기(접근방법) 1. n을 입력받는다 2.알고리즘 해석 칸을 채우는 경우는 다음의 경우의 수로 나뉜다. 1) 1* 2 세로 직사각형을 세우는 경우 : 한 칸 2) 2*1 가로 직사각형을 세우는 경우 : 두 칸 , 항상 두 직사각형이 같이 가야 한다. 3) 2*2 정사각형을 세우는 경우 : 두 칸 경우의 수 dp[1] = 1 세로 1개 dp[2] = 3 가로 두개, 세로 두 개, 정사각..
링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 소요시간: 실패 설계하기(접근방법) 1. 계단 수, 계단 입력받기, dp선언하기 2. 알고리즘 해석 1) 마지막 계단을 기준으로 i) 전 계단을 밟고 온 경우 -> 이 경우는 전전 계단을 밟고 왔을 경우의 수가 없으니 dp[n] = s[n] + s[n-1] + dp[n-3] 과 같다. s[n-1] + dp[n-3]는 서로 두칸 떨어져있으니 3칸 연속되는 경우는 고려하지 않아도 된다. ii) 전전..
