# DP
[플래티넘5] 12920번 : 평범한 배낭2
https://www.acmicpc.net/problem/12920중복되는 물건 또한 개별의 물건으로 처리하여 2차원 dp 리스트를 통해 해결하려 했지만 시간초과로 인해 할 수 없었다다른 사람들의 풀이를 참조하였고, 비트마스크 개념을 사용하는 문제임을 알 수
[BOJ]11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
[프로그래머스] LV.3 정수 삼각형 (JS)
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다
[프로그래머스] LV.3 등굣길 (JS)
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학
[프로그래머스] LV.3 N으로 표현 (JS)
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.12 = 5 + 5 + (5 / 5) + (5 / 5)12 = 55 / 5 + 5 / 512 = (55 + 5) / 55를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.이처럼
[골드3] 1005번 : ACM Craft
https://www.acmicpc.net/problem/1005dp를 적용하여 구하는 위상정렬 문제였다q에서 값을 뺄 때, 진입차수-1과 동시에 dpnow(이전 건물까지 걸리는 시간)+di(이번 건물을 짓는 시간)와 dpi 중 더 큰 값을 dpi에 저장해주었
[프로그래머스] 정수 삼각형 (java)
🔗 문제링크 https://programmers.co.kr/learn/courses/30/lessons/43105 👩🏻💻 코드 📝 정리 DP 문제라는 걸 알고 풀어서 그런가 Level 3인 것에 비해 쉽게 느껴졌다. 규칙을 찾는 것 또한 다른 DP 문제에
[BOJ]5904. Moo게임
BOJ 5904 Moo게임 문제 바로가기문제의 저작권은 백준 온라인저지에 있습니다.메모리 초과가 날 수 있기 때문에 모든 수열을 만들어 해결하지 않고 위치만으로 해결해야한다.
9252 LCS 2
난이도: 중문제번호: 9252생성일: 2021년 4월 1일 오후 10:32유형: DP, 문자열출처: https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%
11660 구간 합 구하기 5
11660 난이도: 하 링크: https://www.acmicpc.net/problem/11660 문제번호: 11660 생성일: 2021년 4월 1일 오후 9:12 유형: DP 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y
[BOJ 9251] LCS(Python)
LCSACAYKPCAPCAK두 개의 문자열이 주어지고 가장 긴 공통 부분 수열을 찾는 문제입니다.AC길이 : 0ACA길이 : 1 (A)ACAP 길이 : 1 (A)....ACC길이 : 1 (C)ACCA길이 : 1 (C)ACCAPC길이 : 2 (AC)이런식으로 완전 탐색을
[실버1] 1309번 : 동물원
https://www.acmicpc.net/problem/1309n줄에 사자를 하나도 배치하지 않을 경우의 수, n줄 왼쪽에 사자를 배치할 경우의 수, n줄 오른쪽에 사자를 배치할 경우의 수를 합산하여 구할 수 있었다소스 코드
[실버3] 1699번 : 제곱수의 합
https://www.acmicpc.net/problem/1699처음에 짠 코드는 시간초과가 났었다...다른 사람의 풀이를 참고해 효율적으로 문제를 풀 수 있었다소스 코드
