[Algorithm] 50. 영지(territory) 선택

인트로 피보나치 수열로 동적 프로그래밍을 이해했다면 그다음 단계로 풀어볼 적당한 문제인 것 같다. 영지(territory)선택 문제 세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다. 전체 땅은 사각형으로 표시된다. 그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(세로의 길이와 가로의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것이다. 전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요. 다음과 같은 땅의 정보가..

• format_list_bulleted it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 25.
• textsms

[Algorithm] 동적 프로그래밍 (DP, 동적 계획법) 이해하기 (+ 예제 코드)

인트로 +컴퓨터공학을 전공하셨거나 코딩 테스트를 준비하시는 분들은 한 번쯤 접해보셨을 동적 프로그램(DP, 동적 계획법)을 쉽게 이해하기 위해 작성한 글입니다. ★ 동적 프로그래밍은 "큰 문제"를 "부분 문제"로 나누고 "부분 문제"의 정답으로 "큰 문제"의 해답을 찾아가는 알고리즘 설계 기법이다. 이렇게 보면 동적 프로그래밍은 분할 정복이 동일하다고 생각할 수 있지만 해를 구하기 위해 쪼갠 "부분 문제"의 특성이 다르다. 분할 정복과 비교했을 때 동적 프로그래밍의 도드라지는 특성은 작게 쪼개진 "부분 문제"가 중복돼서 나타난다는 것이다. 이에 대해선 차차 알아보기로 하고 알기 쉽게 동적 프로그래밍을 이해해 보자. 동적 프로그래밍 (DP, 동적 계획법) 피보나치 수열을 예로 들어 동적 프로그래밍을 설명하..

• format_list_bulleted 동적 프로그래밍(DP)
• · 2021. 8. 25.
• textsms