본문 바로가기

Algorithm/DP(Dynamic Programing)

 (65)
(C++) - 백준(BOJ) 9184번 : 신나는 함수 실행 www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 메모이제이션으로 불필요한 함수 호출을 막는 dp문제였습니다. 풀이방법 1. w라는 함수를 실행하기 전에 d[a+50][b+50][c+50]값이 저장되어 있는지 확인하는 ret 참조변수를 선언 후 저장합니다. a,b,c값이 음수를 포함하므로 음수 인덱스에 접근하지 않도록 오른쪽으로 50만큼 당겨주어 저장했기 때문에 읽을 때 +50한만큼 인덱스를 가져옵니다. 2. w함수를 수행한 결과를 포맷에 맞게 출력합니다. Cod..
(C++) - 프로그래머스(연습문제) : 땅따먹기 programmers.co.kr/learn/courses/30/lessons/12913?language=cpp 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr bottom dp문제였습니다. 풀이방법 i+1의 j번째 열을 선택할 때의 점수 = max(i번째 행의 j번째열을 제외한 나머지 열들의 점수들 중 최대) + 현재 i+1,j의 발판 점수 land.size()-1번째 행의 모든 열들 중 최대가 최종 점수입니다. Code #include using namespace std; int solu..
(C++) - 프로그래머스(연습문제) : 피보나치 수 programmers.co.kr/learn/courses/30/lessons/12945 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.co.kr 간단한 dp 예제였습니다. 풀이방법 점화식에 따라 배열을 만들어 값을 저장해주시면 됩니다. 또한 modula연산시 결합법칙이 가능합니다. Code #include using namespace std; i..
(C++) - 백준(BOJ) 7579번 : 앱 답 www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net top down dp로 푼 문제였습니다. 풀이방법 1. 두 가지의 상태로 나누어집니다. 1-1. 현재 앱을 놔두는 경우에는 현재 남는 메모리는 그대로입니다. 1-2. 비활성화하는 경우. 현재 남는 메모리 = 현재 남는 메모리 - 현재 앱을 다시 실행할 경우의 cost입니다. 2. dp 점화식을 세웁니다. d 배열을 선언합니다. i번째 어플의 남은메모리 j로 확보할 수 있는 메모리양으로 정의될 수 있습니다. i번째 앱에..
(C++) - 프로그래머스(연습문제) : 가장 큰 정사각형 찾기 dpprogrammers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr dp문제였습니다. 풀이방법 1. 배열 d를 정의합니다. : (i,j) 위치에서 정사각형이 되는 최대 한 변의 길이 다음과 같이 1,1의 위치에서의 정사각형을 만들 수 있는 최대 한 변 길이는 다음과 같은 세 방향으로부터의 값 중 최소가 됩니다. 2. 점화식을 세웁니다 : 현재 i,j위치가 1이라면 정사각형의 한 변의 길이를 넓혀 볼 수 있습니다. 넓힐때는 다음과 같이 정사각형의 특성상 영향을 받는 노란색의 나머지 세 위치로부터 값들의 최소를 뽑은 뒤 + 1을 해주..
(C++) - 백준(BOJ) 12852번 : 1로 만들기 2 답 www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net bottom up dp로 풀었습니다. 풀이방법 1. 1로 시작하여 n을 만드는 것으로 생각했습니다. 따라서 문제의 해당 조건에서 반대로 다음 수를 만들게 됩니다. 즉, 1을 빼는 것은 1을 더하는 것, 나누기 2하는 것은 2를 곱하는 것, 나누기 3하는 것은 3을 곱하는 것이 되게 됩니다. 이 때 3가지의 경우로 수를 만들 수 있습니다. 1) 1을 더하는 것 i + 1이라는 숫자를 만드는 방법의 수 = i라는 수를 만드는 방법 개수 + 1 2) 2를 곱하는 것 i * 2 이라는 숫자를 만드는 방법의 수 = i라는 수..
(C++) - 프로그래머스(고득점 kit - 동적계획법(DP)) : 등굣길 programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr top down dp를 이용해 풀었습니다. 풀이방법 동그라미 표시된 지점으로 가는 방법은 1, 2번 방법 뿐입니다. 따라서, 현재 i,j지점으로 올 수 있는 경우의 수 = (i-1,j로 올 수 있는 경우의 수) + (i,j-1로 올 수 있는 경우의수)가 됩니다. 이를 점화식으로 옮겨볼 수 있습니다. 점화식으로 옮긴다면 다음과 같습니다. d[i][j] = d[i-1]..
(C++) - 프로그래머스(고득점 kit - 동적계획법(DP)) : 정수 삼각형 답 programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 간단한 dp문제였습니다. 풀이방법 1. d배열을 정의합니다 현재 i층의 j번째 원소가 최적의 방법으로 선택했을 때의 최대값 : max(i-1번째 층 j-1원소, i-1 번째 층 j원소) + 삼각형 i층 j번째 원소의 값 2. 마지막 층의 d의 원소들 중 최대값을 반환합니다. Code #include using namespace std; int solution(vector triangle) { int size = triangle.size(); int a..

티스토리툴바