728x90 Python 썸네일형 리스트형 [백준알고리즘] 11054번: 가장 긴 바이토닉 부분 수열 -Python [백준알고리즘] 11054번: 가장 긴 바이토닉 부분 수열 -Python https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 밑에 새로 풀면서 추가 설명을 적어놨다. 첫 풀이가 어려우면 밑의 풀이를 보면 된다. 2019-08-13 첫 번째 풀이 LIS(Longest Increasing Subsequence)의 응용문제 중 하나이다. 문제를 보면 뽑아낸 부분수열이 증가하다가 감소하는 형태를 가질 때의 최대길이를 구하는 문제이다. 쉬운 버전인 11053번의 경우 증가하는.. 더보기 [백준알고리즘] 1520번: 내리막 길 -Python [백준알고리즘] 1520번: 내리막 길 -Python https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다. www.acmicpc.net 20200408 아래 새로 풀었다. 요즘 계속 DP를 다시 보고 있다. 오늘은 내리막 길을 풀어봤는데 금방 풀렸다. 개인적으로 dp 중에서는 쉬운 편이었다고 생각을 한다. 이번에는 최저의 방법을 구하는 것이 아닌 가능한 경우의 횟수를 구하는 문제다. 그러다.. 더보기 [백준알고리즘] 12865번: 평범한 배낭 -Python [백준알고리즘] 12865번: 평범한 배낭 -Python https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 제목처럼 평범한 Dynamic Programming문제이다 처음에는 DFS와 upper bound를 이용한 Branch and Bound를 사용하려 하다가 사실상 Brute Force보다 조금 나은 수준의 코드가 되어버린 것.. 더보기 이전 1 ··· 19 20 21 22 다음