오딩이

출처 : https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 🔍 Solve 다이나믹 프로그래밍으로 풀기 전, 완전 탐색으로 풀었을 때 시간 초과가 났던 문제입니다. 완전 탐색으로 풀었을 때 우선순위가 큰 것부터 선택하고 인접한 곳들을 지우는 방법으로 풀었습니다. isSelect배열을 선언하여 지워지는 곳은 1로, 선택된 곳은 2로 저장하였고, isSelect배열이 0이 아닌 수로 꽉 차면 break를 해주었습니다. 해당 방법은 테스트 케..

출처 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 🔍 Solve 완전 탐색으로 문자열 1과 문자열 2를 비교하는 방법을 생각했었는데, 카테고리가 dp인 만큼 시간 초과가 났습니다. dp배열에서 i=0, j=0일 때 i-1, j-1을 비교해야하기 때문에 dp배열의 크기는 (문자열 1의 길이+1) * (문자열 2의 길이+1)로 설정하였습니다. 문자열의 문자들을 비교하면서 문자가 같지 않을 땐 dp..