동적계획법27 [Programmers] 멀리 뛰기 https://school.programmers.co.kr/learn/courses/30/lessons/12914 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 한 번에 뛸 수 있는 칸의 수가 1 또는 2이므로, $n$ 번째 칸에 도달하기 위해서는 $(n-2)$ 번째 칸에서 2 칸을 뛰거나 $(n-1)$ 번째 칸에서 1 칸을 뛰어야한다. 따라서 $n$ 번째 칸에 도달하기 위한 경우의 수를 $f(n)$이라고 하면 $f(n)$은 아래와 같은 점화식(recursive formula)을 만족하며 처음 두 개의 항을 1, 2로 하는 피보나치 .. 2023. 8. 30. [Baekjoon] 11660번: 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 해결 과정 착안 이차원 배열 내에서 $x_1$행 $y_1$열을 좌상단, $x_2$행 $y_2$열을 우하단($x_2 \geq x_1, \space y_2 \geq y_1$)으로 하는 사각형 내의 숫자들의 누적 합을 계산하기 위해, 주어진 이차원 배열과 크기가 같은 배열을 선언하여 동적계획법(dynamic programming)에 활용한다. 이때, 메모.. 2023. 8. 24. [Baekjoon] 16493번: 최대 페이지 수 https://www.acmicpc.net/problem/16493 16493번: 최대 페이지 수 첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이 www.acmicpc.net 문제 해결 과정 착안 이전 포스트에서와 동일한 원리로, 동적계획법(dynamic programming)에 기반하여 문제를 해결하였다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include #include using namespace std; struct Chapter { int Days; int Pages; }; Chapte.. 2023. 8. 8. [Baekjoon] 12865번: 평범한 배낭 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 문제 해결 과정 착안 배낭에 넣고자 하는 물건의 무게의 총합이 $k \space (1 \leq k \leq K)$일 때, 같은 무게로 만들 수 있는 가치의 총합 중 가장 큰 값을 배열에 저장하기 위해 동적계획법을 사용하여 문제를 해결하고자 하였다. $i$번째 물건의 무게를 $w_i$, 가치를 $v_i$라고 하면, $1, 2,\cdo.. 2023. 8. 1. [Baekjoon] 2293번: 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 과정 착안 주어지는 $n$개의 동전의 가치를 편의상 각각 $c_i \space (1 \leq i \leq n)$라고 하면, 종류가 다른 동전이 하나하나 주어질 때마다 아래와 같은 원리에 의해 단계별로 사용하는 동전의 수를 늘려가면서 가치의 총 합이 $k$ 이하의 자연수가 되도록 만드는 경우의 수를 귀납적으로 구할 수 있다. [전제조건] 1) 동전들을 사용하여 만들 수 있는 가치의 총 합은.. 2023. 7. 24. [Programmers] 정수 삼각형 https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 동적계획법(dynamic programming)을 통해 가장 아래 층의 숫자들부터 인접한 두 개씩 비교하여 위의 숫자로 더해나가는 방식으로 문제를 해결하고자 하였다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include #include using namespace std; int solution(vector triangle) { for.. 2023. 7. 21. 이전 1 2 3 4 5 다음
