본문 바로가기

Algorithm/DP(Dynamic Programing)

 (64)
(C++) - 백준(BOJ) 3745번 : 오름세 https://www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net LIS문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. vector d를 선언합니다. 2. n을 EOF가 아닌동안 입력받습니다. 3. d를 n만큼 resize 합니다. n개의 방을 저장할 수 있게 됩니다. 📔 풀이과정 n개의 수를 입력받을 때 마다 답을 저장할 vector인 d변수에 대해 d.begin부터 lis의 길이인 length까지의 범위에서 입력 받은 수를 key로 하여 lower_bo..
(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..

티스토리툴바