728x90 반응형 다이나믹 프로그래밍24 2022.06.05 [프로그래머스] (python 파이썬) 3Xn 타일링 https://programmers.co.kr/learn/courses/30/lessons/12902 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 풀이 이 문제는 우선 규칙을 찾아야한다. 먼저 n이 홀수면 전체 칸이 홀수가 되기 때문에 2X1의 타일로 채울 수 없기 때문에 0을 리턴해준다. n=2일 때, 3 n=4일 때, 11 n=6일 때, 41 손으로 그려보다 보면 이런식으로 증가하는것을 확인할 수 있다. 여기서 점화식을 찾아야하는데 위의 그림에서 보면 n이 8일 때, 이전 짝수의 *3, 그 이전의 값들*2 +2란 규칙이 있다. 왜냐하면 2씩 증가할때마다 2칸씩 나누면 한칸에 놓을 수 있는 경우의 수=3 그래서 이전의 값에서 *3을 해야하고 그 이전의 값은 상하 반전을 할 경우.. 2022. 6. 5. 2022.03.22 [백준] (python 파이썬) 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 문제를 해결하기 위해 우선 arr배열에 문제에서 주어진 배열을 넣었다. 그리고 dp배열을 (n+1)X(m+1)크기로 만들었다. 이유는 이전 값을 비교해야하기 때문이다. 만약 arr[i][j]가 0이면 정사각형을 만들 수 없으므로 넘어가고 1이면 dp[i+1][j],dp[i][j+1],dp[i][j]을 비교하여 가장 작은 값의 +1 값을 dp[i+1][j+1]에 넣어준다. dp[i+1][j+1]에는 arr[i][j]를 정사각형의 우측하단 꼭짓점으로하여 만들수 있는.. 2022. 3. 22. 2022.03.18 [백준] (python 파이썬) 팰린드롬? https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 우선 이 문제를 풀기 위해선 팰린드롬이 무엇인지 알아야 한다. 팰린드롬은 앞에서 부터 읽거나 뒤에서 부터 읽어도 같은 문장을 말한다. 예를 들면 aba, 131과 같은 문장이다. 이 문제를 다이나믹 프로그래밍으로 풀기 위해 2차원 배열을 사용했다. dp[시작인덱스][종료인덱스]로 해서 해당 시작인덱스에서 종료인덱스까지의 문장이 팰린드롬이면 True 아니면 False로 선언했다. 그리고 2중 for문을 이용해서 각 문장이 팰린드롬인.. 2022. 3. 18. 2022.03.18 [백준] (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 풀이 이 문제는 0-1 배낭문제(0-1Knapsack Problem)이다. 왜냐하면 물건을 나누지 못하고 가진 물건으로 가방에 넣어 최대 가치를 만들어야 하기 때문이다. dp배열을 (n+1)(k+1)배열의 크기로 만든다. 이유는 조건에 따라 이전의 값과 비교해야 해서 n,k보다 1씩 큰 배열을 만들었다. 각 물건별 각 무게로 for.. 2022. 3. 18. 이전 1 2 3 4 ··· 6 다음 728x90 반응형
