난이도: Lv.3유형: DP해결 여부: 통과아이디어삼각형 내려오면서 가장 큰 값을 구하는 문제. 내려오면서 DP로 기록하는식으로 구하면 된다.오답 이유 혹은 알게 된것로직틀리진 않았는데, 2차원 배열인거 무시하고 값 처음꺼 하나라고 index를 하나밖에 안써주거나 배열 초기화 할때 그냥 빈 배열 선언해놓고, list out of index 나게 하는거. append로 처리할 수 있는거는 처음부터 append 쓰는게 나을듯lamda 식 쓰면 앞으로도 임시값 처리할때 유용할 것 같다. def solution(triangle): height = len(triangle) arr = [int(triangle[0][0])] temp=[] for i in range(1,height): ..
Algorithm/DP
난이도: Lv.3유형: DP해결 여부: 에러 후 통과아이디어평범한 길찾기 DP 문제오답 이유 혹은 알게 된것for문에서 range 안쓰고 그냥 in 써서 틀림...초깃값 설정 문제와 문제에서 말한 좌표가 1씩 더해진 것 보정이어야 하는데 그걸 안해서 틀렸다. 근데 또 테케에서는 맞아서 왜틀린지 몰랐었다.def solution(m, n, puddles): arr=[[0]*m for _ in range(n)] for puddle in puddles: arr[puddle[1]-1][puddle[0]-1]=-1 arr[0][0]=1 for i in range(0,n): for j in range(0,m): if (i==0 and j==0) or ..
난이도: Lv.3유형: DP해결 여부: 오답 아이디어주어진 숫자를 최소로 써서 사칙연산만으로 목표 숫자에 도달하는 개수 맞추기 오답 이유 혹은 알게 된것문제좀 잘 읽자. DP 인데 숫자의 개수가 아닌 사칙연산의 개수로 착각했던 점, 최대 8까지라는 제한이 없다는 점을 빼먹어서 더 효율적인 방법이 있을거라 생각해 애먹었다.DP 지만 bruteforce 적인 성격도 띄는 문제였다. 처음에 혹시 index 숫자에 value로 그 값 넣는 식으로 안되나 싶어서 시간이 걸렸다. set()의 사용이 미흡해 좀 걸렸다. set() 은 그냥 이렇게 선언해서 for문 돌리면 된다.update로 한번에 여러개 하려고 했는데 그게 아니었다. update로 set 여러개 add하고 싶으면 묶어주어야 해서 걍 add 여러번 쓰..
난이도: Lv. 3유형: DP, 수학, 부분합해결 여부: 오답아이디어홀수는 들어올 수 없다. 애초에 0으로 잡아야 한다.짝수가 들어올때 이전에 있던 모양에서 가로 2줄씩 3가지 경우가 붙는다고 봐야 한다.. 하지만 여기에 특수한 형태가 있다. 오답 이유 혹은 알게 된것DP로 접근하는 것 까지는 맞았으나, 이후 점화식에서 틀렸다. f(n)은 항상 f(n-2) 에서 도출되며 3*f(n-2) +2 로 잡았는데 f(n-4) 에서도 도출되는 경우를 생각해야 했다. 만약 하나만 세로로 하고 그 옆을 3줄짜리 가로로 주르륵 채운다면 그건 f(n-2) 에서는 얻을 수 없는 형태가 된다. 그래서 f(n) = 3f(n-2) -> f(n-2) 에서 3칸 붙이기 뿐만 아니라 2f(n-4), 2*f(n-6) ...2f(0) ..
https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net C++로 작성한 백준 문제 9657번 돌 게임 3에 대한 문제 풀이다. 실버 3 문제로 동적계획법이 문제를 푸는데 필요한 주요 지식이다. 문제 설명 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진..
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 2차원 배열을 사용하는 dp로 접근했다. 가능한 돈의 경우의 수를 동전별로 따로 접근한다. 행에는 동전, 열에는 목표하는 원을 만들고, 그에 따라 가능한 경우의 수를 할당하였다. 배열의 열을 i라고 하고, 현재 사용하는 동전 행을 j라고 하자. 그리고 현재 n원 짜리 동전으로 계산하고 있다면 다음과 같은 점화식이 나온다. dp [i][j]=dp [i-1][j]+dp [i][j-n] 현재 dp에..
https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 문제를 풀기 위해서는 주어진 2개의 문자열 중 하나를 기준으로 잡아 생각해야 한다. 여기서는 그 문자열을 기준문자열, 그렇지 않은 문자열을 비교문자열이라고 하겠다. ACAYKP가 여기서는 기준문자열, CAPCAK가 비교문자열이다. 기준문자열의 길이만큼 dp 배열을 만든다. 즉 배열 칸이 의미하는 것은 각 번째의 문자를 말한다. 문자열 A C A Y..
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 이 문제를 보고 가장 먼저 생각난 것은 바이토닉 수열의 중앙점이다 S1 ... SN-1 > SN에서 Sk를 말하는 것이다. Sk를 어디로 S1~SN 중 어디로 할지 정하고, S1~SK에서 나오는 증가하는 부분수열의 개수+ SK~SN에서 나오는 감소하는 부분수열의 개수를 K 값에 따라 비교해 최댓값을 출력하면 된다. 2023.06.11 - [algorithm/dp] - [백준] 11053번:..
