목록가장 긴 증가하는 부분 수열 (2)

1일1알

백준 18353번 병사 배치하기 C++

https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 가장 긴 증가하는 부분 수열 응용문제 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n;..
알고리즘 2023. 3. 22. 08:04
백준 11568번 민균이의 계략 C++

문제를 한줄로 요약하자면 가장 긴 증가하는 부분 수열을 구하는 것이다. 다이나믹 프로그래밍으로 해결할 수 있는 문제이다. 처음에 수열의 길이를 저장하는 dp테이블을 모두 1로 초기화 시킨다. (자신만 있을 경우 수열의 길이는 1) 원소들을 처음부터 검사하면서 자신의 앞에 있는 모든 원소들을 비교하다가 만약 자신보다 값이 작은 값을 찾으면 자신이 그 수열에 포함된다면 증가하는 수열의 길이가 늘어나는 것이기 때문에 찾은 값의 수열의 길이 중 가장 큰 값을 저장한다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;..
알고리즘 2021. 12. 4. 12:59
이전 Prev 1 Next 다음