본문 바로가기

Algorithm/DP(Dynamic Programing)

 (72)
(C++) - 백준(BOJ) 14494번 : 다이나믹이 뭐에요? https://www.acmicpc.net/problem/14494 14494번: 다이나믹이 뭐예요? (1, 1)에서 (n, m)에 도달하는 경우의 수를 구하여라. 단, 경우의 수가 엄청 커질 수 있으므로 경우의 수를 1,000,000,007(=109+7)로 나눈 나머지를 출력한다. www.acmicpc.net 기본 dp문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. i행, j열에 도달할 경우의 수를 저장하기 위한 이차원 배열 d와 n, m을 선언합니다. 2. d의 모든 원소들을 -1로 초기화해줍니다. 3. n, m을 입력해줍니다. 📔 풀이과정 1. dp함수를 수행합니다. 2. n행 m열에서 출발해 역(1행 1열)로 거슬러 올라가며 dp함수를 호출합니다. 3. 1행 1열에 알맞게 도착했다면 1을, 열..
(C++) - 백준(BOJ) 15486번 : 퇴사 2 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net dp 문제였습니다. 📕 풀이방법 수행 시간이 n이 150만이므로 O(n)에 수행해야 합니다. 제한사항이 영향을 끼치지 않기 때문에 본질적으로 퇴사문제와 풀이 방법이 같습니다. 제 풀이는 해당 문제에 대한 설명을 포스팅 한 글로 대체합니다. https://codecollector.tistory.com/1113 (C++) - 백준(BOJ) 14501번 : 퇴사 https..
(C++) - 백준(BOJ) 1949번 : 우수 마을 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net tree를 만들고 dfs를 수행하며 top down dp로 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. 마을마다 주민수를 입력받아 일차원 배열에 저장합니다. 2. 인접리스트로 무방향 그래프를 만들어 줍니다. 이를 graph라는 vector형 변수에 저장합니다. 3. 루트노드에서 출발하여 문제에서 나온 규칙을 계속해서 지켜가며 트리의 아래로 내려간다면 결국 답이 나온다는 줄기..
(C++) - 백준(BOJ) 14501번 : 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dp문제였습니다. 📕 풀이방법 1. 두 가지 선택 방법이 있습니다. 현재 상담을 선택하는 경우와 현재 상담을 선택하지 않는 경우입니다. 현재 상담을 선택하는 경우 그만큼의 이익이 있지만 상담기간동안 다른 상담을 못한다는 기회비용이 존재합니다. 따라서 선택하거나 선택하지 않을 경우에 대해 저울질해서 이익의 최댓값을 찾아야 합니다. 2. 현재 기간 + 현재 상담하기로 결정했을 때 걸리는 상담시간이 퇴사일보다 이하라면 현재의 상담을 하도록 선택할 수 있습니다. 점화식을 세워보면 다음과 같습니다. 먼저 d배열은 t일차에 얻을 수 있는 최대 ..
(C++) - 프로그래머스(2017 카카오코드 예선) : 보행자 천국 https://programmers.co.kr/learn/courses/30/lessons/1832 코딩테스트 연습 - 보행자 천국 3 3 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 6 3 6 [[0, 2, 0, 0, 0, 2], [0, 0, 2, 0, 1, 0], [1, 0, 0, 2, 2, 0]] 2 programmers.co.kr dp문제였습니다. 풀이방법 1. 0,0에서 출발해서 현재좌표 (i, j)에 따라 다음 행선지를 정합니다. 2. 현재 표지판이 0이라면 우측 또는 아래로 갈 수 있습니다. 현재 표지판이 1이라면 더 이상 갈 수 없으므로 0을 반환합니다. 현재 표지판이 2고 이전 방향이 오른쪽(dir == 1)이라면 오른쪽으로만 갈 수 있고 아래쪽이라면(dir == 2) 아..
(C++) - 백준(BOJ) 14728번 : 벼락치기 https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net dp문제였습니다. 풀이방법 1. d[i][j] = i시간동안 n번 챕터를 풀었을 때 얻을 수 있는 점수의 최댓값입니다. 2. 점화식으로 나타내면 d[i][j] = 점수max(현재 챕터를 골랐을 때, 현재 챕터를 고르지 않았을 때) 입니다. 현재 챕터를 고르게 되면 현재 점수를 고른뒤 공부하는데 걸리는 시간을 빼주게 됩니다. 남은시간이 음수가 된다면 해당..
(C++) - 백준(BOJ) 5582번 : 공통 부분 문자열 https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net dp문제였습니다. 풀이방법 d[i][j] = i부분과 j부분의 문자가 같다면 그 이전의 최대길이 + 1 로 정의합니다. Code #include using namespace std; string s, t; int ans, d[4001][4001]; int main(){ cin >> s >> t; for(int i = 0; i < s.size(); i++){ for(int j = 0; j..
(C++) - 백준(BOJ) 1915번 : 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp문제였습니다. 풀이방법 2 X 2짜리 정사각형을 생각합니다. i행 j열이 1이라면 이전에 가장 큰 정사각형의 한 변의 길이가 저장된 (i-1,j-1), (i-1,j), (i,j-1) 위치의 값들중 최소인값 + 1을 저장합니다. 점화식으로 나타낸다면 min({square[i-1][j-1],square[i-1][j],square[i][j-1]}) + 1 Code #include #define INF 0x3f3f3f3f using namespace std; int n,..

티스토리툴바