solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 해석 문제 풀이 입력 범위가 1000 이기 때문에, lis 알고리즘이 아니라 2차원 dp를 사용해 가장 긴 증가하는 수열을 앞에서, 뒤집어서 두 번 구해주었다. 뒤집어서 구해준 값들을 다시 뒤집어 순서를 맞춰주고, 두 dp값들의 합이 최대가 되도록 하는 값 + 1이 답이 된다. 문제 코드 def solve(n, arr): # 앞에서 부터 가장 긴..
solved.ac Class 4레벨에 속한 문제이다. 문제 주소: https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 해석 스티커를 떼어내 최대의 점수를 얻어야 한다. 이때 스티커를 떼면 상하좌우에 존재하는 스티커가 함께 떼어지고, 함께 떼어진 스티커는 점수를 획득하지 못한다. 얻을 수 있는 최대의 점수를 구하는 문제이다. 문제 풀이 dp를 이용해서 해결해 주었다. j열의 새로운 스티커를 선택할 때 j - 1열의 반대 행의 점수 j..
처음으로 쇼미더코드 문제를 풀어보았다. 코딩 테스트 결과에 따라 배지를 부여받을 수 있다고 한다. 사실 아직도 코딩테스트는 익숙지 않은 것 같다.. 문제도 꼼꼼히 읽어봐야겠다.. A. 누적합을 이용한 문제이다. 문제를 잘못읽어 1 또는 2의 가장 긴 길이를 반환하도록 구현해서 틀렸다. https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 백준의 해당 문제와 매우 유사하다. 1인 경우 + 1, 2인 경우 -1로 계산하고, 음수가 되는 경우 시작점을 초기화하여 0..
