다이나믹 프로그래밍 썸네일형 리스트형 백준 9251번 - LCS (Longest Common Subsequence) * 문제 링크 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 내용 요약 문자열이 2개 주어지면 (최대 길이 1000자), 공통된 부분 수열 중 가장 긴 거 길이를 출력해라. (Longest Common Subsequence = 최장 공통 부분 수열) 접근법 매우 유명한 다이나믹 프로그래밍 문제 2 정도로 보면 된다. 항상 그렇듯이, 무엇을 어떻게 메모할지를 정하는 것이 중요하다. 첫번째 힌트로.. 더보기 백준 2565번 - 전깃줄 * 문제 링크 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 내용 요약 전봇대에 높이에 따라 1번부터 500번까지 있는데, 전깃줄은 두 전봇대 각각의 번호 한 쌍을 연결한다. 근데 이게 교차되면 합선되니까 교차가 안되게 제거할 전깃줄의 최소 개수를 구해라 접근법 단계별로 풀어보기에도 나와있지만, 이 문제 또한 LIS의 응용 문제다. LIS에 관한 설명은 아래의 링크를 참고하자. https://syerco0.com/22 백준 11053번 - 가장.. 더보기 백준 11054번 - 가장 긴 바이토닉 부분 수열 * 문제 링크 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 내용 요약 어떤 수 S_k 를 기준으로 S_1 부터 S_k 까지 증가, S_k 부터 S_n 까지 감소하는 형태면 바이토닉 부분 수열이라고 부른다. 수열이 주어지면 가장 긴 바이토닉 부분 수열의 길이를 구하여라. 접근법 일단은 이 문제를 풀기 전에 LIS 문제부터 풀고 오는 것을 추천한다. https://syerco0.com/22 백준 11053번 - 가장 긴 증가하는 부분 수열 (LIS) * 문제.. 더보기 백준 15678번 - 연세워터파크 * 문제 링크 https://www.acmicpc.net/problem/15678 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net 문제 내용 요약 매년 여름 연세대 (특히 도서관, 서문) 에서는 깜짝 워터파크가 개장하는데, 잘 즐기라고 징검다리를 놓아두고 게임을 만들었는데, 부적절한 점수작을 하는 놈들이 있어서 다음과 같은 규칙을 정했다. 징검다리 N (2 ≤ N ≤ 100,000) 개가 있고, 각각 1 ~ N의 번호가 붙어있다. 이 중에 하나는 시작점으로 올라타야한다. 징.. 더보기 백준 5977번 - Mowing the Lawn * 문제 링크 https://www.acmicpc.net/problem/5977 5977번: Mowing the Lawn FJ has 5 cows whose efficiencies are 1, 2, 3, 4, and 5, in that order. He wants to choose some of the cows such that their total efficiency is maximized, but he cannot choose more than 2 consecutive cows. FJ chooses all cows but the third. The total effici www.acmicpc.net 문제 내용 요약 엄청 예쁜 잔디밭 대회에서 농부 John씨가 우승하고 싶은데, 작년 대회 이후 흥청망청.. 더보기 이전 1 다음
