본문 바로가기
  • 개발공부 및 일상적인 내용을 작성하는 블로그 입니다.

코딩 테스트/동적 프로그래밍3

백준 11060 - 점프 점프 (자바 - DP) https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net * 문제 요약 재환이가 1 x N 크기의 미로에 갇혀있다. 미로는 1 x 1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여있다. i번째 칸에 쓰여있는 수를 Ai 라고 했을 때, 재환이는 Ai 이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여있는 수가 3 이면 재환이는 4,5,6번 칸 중 하나로 점프할 수 있다. 재환이는 지금 미로의 .. 2023. 8. 18.
백준 11053 - 가장 긴 증가하는 부분 수열(자바 - 동적 프로그래밍) 평범한 배낭 문제 이후 또 다시 마주친 동적 프로그래밍 응용 문제 위의 말에서 언급한 평범한 배낭 문제와 같이 또 한번 동적 프로그래밍의 역량 부족을 느낀 문제이다. 실버 2 라는 문제 난이도를 보고 그래도 쉽지 않을까 생각했으나 동적 프로그래밍 방식의 코딩에 대한 역량 부족은 문제의 난이도와는 별개였다. 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 입력으로 수열.. 2021. 12. 26.
백준 12865 - 평범한 배낭(자바 - 동적 프로그래밍) DP 에 대해 문제 풀이 역량이 스스로 너무 부족함을 절절히 느낀 문제 사용하는 방법이 비교적 명확한 다른 알고리즘들에 비해, 점화식을 세우는 방식이 워낙 각양각색 인지라 아직도 전형적인 동적 프로그래밍 풀이 문제를 제외하면(피보나치 수열과 비슷한 문제들) 다른 문제를 거의 풀지 못하는 내 자신의 부족한 역량을 뼈 속 깊이 느낄수 있었던 문제였다. 처음 이 문제를 마주했을 땐, 그리디 알고리즘을 공부할 때 배웠던 문제와 흡사했기 때문에 물건을 가중치 대비 무게가 낮은 순으로 정렬한 다음, 입력받은 최대 무게 k 만큼 가방이 찰 때까지 물건을 채워 넣다가 무게가 꽉 차면 지금까지 가방해 들어간 물건들의 가중치 합을 출력, 만약 가방에 담을 수 있는 무게 보다 이번에 들어갈 차례인 물건의 무게가 무겁다면 물.. 2021. 12. 26.

티스토리툴바