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

국문과 유목민

[DP] 병사 배치하기

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다. 문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다. 소요시간: 40분 + a 1. 문제 설명 - 병사들의 전투력이 적힌 리스트가 입력으로 들어올 때 내림차순으로 병사들이 정렬되도록 하고자 한다. 가장 전투력을 높게 해서 병사들을 뽑고자 할 때, 병사들을 몇 명을 빼면 되는지 묻는 문제 2. 접근 방식 - 해당 문제는 특성상 정렬을 하면 안되고, 주어진 리스트를 그대로 활용해야 했다. - 초기에는 점화식을 만들기 위해서 노력했으나 결국 그게 답이 아니라는 것은 해답을 보고서야 알았다. - DP 중 유명한 알고리즘인 '가장 긴 증가하는 부분수열 문제'였다. 지금 문제는 감소하는 순서로 찾는 것이었기에 이를 역순..
알고리즘_코딩테스트/이것이 코딩테스트다 2021. 12. 17. 23:42
이전 Prev 1 Next 다음