[백준 / C++] 2565번: 전깃줄 (LIS 응용)

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 다이나믹 프로그래밍, LIS 접근 방법 전깃줄이 겹치지 않으려면 A 전봇대에서 이어지는 B 전봇대의 번호가 오름차순이어야 한다. 따라서 자르는 전깃줄의 개수를 최소화하려면 LIS를 찾아야 한다. 가장 긴 증가하는 부분 수열만을 남기고 나머지는 다 잘라버려야 한다. 구현 LIS 알고리즘 사용해서 (11053번 포스팅 코드 참고) 가장 긴 수열의 길이를 구하..

• format_list_bulleted PS/백준
• · 2023. 7. 31.
• textsms

[백준 / C++] 11054번: 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 난이도: solved.ac 골드 4 접근 방법 11053번을 풀었다면 아주 쉽게 풀 수 있는 문제다. https://jangkunstory.tistory.com/37 [백준] 11053번: 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를..

• format_list_bulleted PS/백준
• · 2023. 7. 28.
• textsms

[백준 / C++] 14002번: 가장 긴 증가하는 부분 수열 4 (dp)

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 난이도: solved.ac 골드 4 접근 방법 일반적인 dp를 이용한 N^2짜리 LIS 풀이로 가장 긴 부분 수열의 길이를 구하고 추가적인 코드를 통해 O(N)에 경로를 추적할 수 있다. 일단 LIS의 길이를 구하는 for문을 마치고 나면 len[i]에는 A[i]를 부분 수열의 마지막 원소로 썼을 때의 LIS 길이가..

• format_list_bulleted PS/백준
• · 2023. 7. 27.
• textsms

[백준] 11053번: 가장 긴 증가하는 부분 수열

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 난이도: solved.ac 실버 2 LIS(Longest Increasing Subsequence)문제다. 나는 DP를 이용해 풀었다. #define _CRT_SECURE_NO_WARNINGS #include #define MAXLEN 1000 #define max(a,b) ((a)>(b)?(a):(b)) int mai..

• format_list_bulleted PS/백준
• · 2023. 4. 29.
• textsms