행 ($i$): $i$번째 물건까지 고려했을 때열 ($w$): 배낭의 현재 용량이 $w$일 때값 $DPi$: $i$번째 물건까지 고려하고 배낭 용량이 $w$일 때 가질 수 있는 최대 가치💎 루비를 선택하는 경우(dp\[루비])💎 다이아를 선택하는 경우(dp\[다이아

이전에 풀었던 문제 : 이 문제는 증가하는 부분 수열 중에서 ‘합이 가장 큰 경우’를 찾는 DP 문제이다. LIS(가장 긴 증가 부분 수열)와 비슷하지만, 길이가 아닌 “부분 수열 값들의 총합”을 기준으로 한다는 점이 핵심이다. 🧩 문제 수열이 주어졌을 때,

길이가 N인 수열이 주어진다.“증가하는 부분 수열(increasing subsequence)” 중가장 길이가 긴 것의 길이를 구하는 문제.부분 수열이기 때문에 연속일 필요는 없다.└ 다만 순서는 유지해야 함.처음엔 “수열을 앞에서부터 보면서, 각 위치에서 끝나는 LIS

길이 N인 수열이 주어진다.연속된 몇 개의 수를 선택해서 만들 수 있는 합 중 최대값을 구하는 문제.수는 양수, 음수 모두 나올 수 있다.“수열에서 연속된 구간 하나를 골랐을 때, 그 합이 최대가 되는 값을 구하라”처음 내가 세운 전략은 이랬다.“음수는 구간 합을 감소

각 집은 빨강(R), 초록(G), 파랑(B) 중 하나로 칠할 수 있고,연속된 집은 같은 색을 칠할 수 없다.모든 집을 칠하는 데 드는 최소 비용을 구하는 문제.조건1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i

https://www.acmicpc.net/problem/1932입력으로 주어지는 삼각형은 아래와 같다.이걸 2차원 리스트로 저장해 두자.예: tri\[i]\[j] = i번째 줄, j번째 숫자(인덱스는 0부터로 할지, 1부터로 할지는 너가 편한 대로!)단순히

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제(단, 방법의 수를 10007로 나눈 나머지를 출력한다)입력으로 주어지는 n은 최대 1000까지 가능하다.즉, 단순 재귀로 풀면 시간 초과가 나기 때문에 DP(동적 계획법) 으로 접근해야 한

이 문제는 언뜻 보면 복잡한 나선 모양 때문에 어려워 보이지만, 숨겨진 규칙(점화식)만 찾아내면 Dynamic Programming(DP)을 활용해 간단하게 풀 수 있었다.문제에서 제시된 수열 $P(N)$의 초기 값들을 나열해 봅시다.이 수열의 값을 자세히 관찰하여 현

Single Responsibility Principle한 클래스는 하나의 책임만 가진다.한 파일에 view, DB접근, 쿼리까지 모두 들어가있으면 유지보수가 어렵고 코드도 복잡해진다.Open / Closed Principle확장에는 열려있고, 변경에는 닫혀있어야 한다

업로드중..계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. (단, 시작점은 계단에 포함되지 않는다.)마지막 계단은 반드시 밟아야 한다.처음에 생각해낸 점화식은 다음과 같다.이 경우, 연속으로 3개를 밟았는지 여부

정수 n이 주어졌을 때,1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제이다.단, 덧셈 순서가 다르면 다른 경우로 센다.예를 들어,4를 만드는 방법은 다음 7가지이다.이 문제는 동적 계획법(DP)으로 해결할 수 있다.n을 만들 수 있는 경우의 수를 dp\[n]이

정수 X가 주어졌을 때, 다음 세 가지 연산을 적절히 사용하여 1을 만드는 연산 횟수의 최솟값을 구하는 문제이다.3으로 나누기: X가 3으로 나누어 떨어질 때 (X → X / 3)2로 나누기: X가 2로 나누어 떨어질 때 (X → X / 2)1 빼기: (X → X -

https://www.acmicpc.net/problem/11723정수 1부터 20까지의 숫자로 이루어진 집합 S에 대해 아래 연산을 수행하는 프로그램을 작성하는 문제입니다.remove()는 해당 원소가 집합에 없을 때 에러(KeyError) 를 발생시킵니다.

https://www.acmicpc.net/problem/10799괄호로 표현된 쇠막대기와 레이저가 주어진다.(는 쇠막대기 시작)는 쇠막대기 끝단, ()는 레이저로 간주레이저가 쇠막대기를 자르면 그 개수만큼 조각이 생긴다.laser 리스트에 모든 레이저의 위치

https://www.acmicpc.net/problem/5430문자열로 주어지는 명령어 p를 배열에 적용하는 문제이다.명령어는 다음과 같다:R: 배열을 뒤집는다.D: 배열의 첫 번째 원소를 버린다. (배열이 비어 있으면 "error" 출력)입력으로는 여러 테

문제 링크 🔗양방향으로 회전이 가능한 큐가 주어진다.처음에는 1부터 N까지의 숫자가 순서대로 들어 있으며, 우리가 꺼내야 할 숫자들이 M개 주어진다.큐에서 원하는 숫자를 꺼내는 방법은 세 가지:첫 번째 원소를 바로 뽑는다 (이 연산은 비용이 없음)왼쪽으로 한 칸 이동

https://www.acmicpc.net/problem/1874current = 1부터 시작해, 수열의 현재 숫자보다 작거나 같을 때까지 계속 push.push할 때마다 + 저장.목표 숫자와 같아지면 pop하고 - 저장.스택의 top이 수열 숫자보다 크면 불

https://www.acmicpc.net/problem/1919두 개의 문자열이 주어졌을 때, 두 문자열을 애너그램(anagram)으로 만들기 위해 제거해야 할 문자의 총 개수를 구하는 문제입니다.예시입력:출력:두 문자열을 "bb"로 만들 수 있으므로 총 8

https://www.acmicpc.net/problem/5397키보드로 비밀번호를 입력하는데, 다음과 같은 특수 키가 존재한다:< : 커서를 왼쪽으로 한 칸 이동 (커서가 가장 앞이면 무시)\> : 커서를 오른쪽으로 한 칸 이동 (커서가 가장 뒤면 무시

보통 리스트(list) 를 사용해서 쉽게 구현할 수 있다.