차근차근

0. 제목 백준 1495 기타리스트 BOJ 1495 기타리스트 파이썬 1495 기타리스트 Python 1495 기타리스트 1. 문제 www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 2. 풀이 0부터 m까지의 볼륨이 가능하고 각 볼륨에서 출력이 가능하면 True, 불가능하면 False로 설정한다. dp[i][j + 1] : i 번째 노래일 때 j 크기의 볼륨으로 연주 가능한지 여부 노래를 순서대로 확인하며, 매 번 모든 크..

0. 제목 백준 9251 LCS BOJ 9251 LCS 파이썬 9251 LCS Python 9251 LCS 1. 문제 www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 2. 풀이 두 문자열의 길이를 조금씩 늘려 가며 확인하여 공통 부분 수열의 최대 길이를 계산한다. 두 문자열을 X, Y라고 할 때 X[i-1] = Y[i-1] 이면 dp[i] = dp[i-1][j-1] + 1, X[i-1] != Y[i-1] 이면 dp..

0. 제목 백준 11053 가장 긴 증가하는 부분 수열 BOJ 11053 가장 긴 증가하는 부분 수열 파이썬 11053 가장 긴 증가하는 부분 수열 Python 11053 가장 긴 증가하는 부분 수열 1. 문제 www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 2. 풀이 dp[i] : i 번째 원소까지의 가장 긴 증가하는 부분 수열의 길이 가장 먼저 dp의 원소들을 1로 초기화 시켜..

0. 제목 백준 12865 평범한 배낭 BOJ 12865 평범한 배낭 파이썬 12865 평범한 배낭 Python 12865 평범한 배낭 1. 문제 www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 풀이 dp[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치 각 물품의 번호 i에 따라서 dp[i][j]를 갱신한다. 1부터 k까지 증가하는 변수 j가 입력된 무게보다..

0. 제목 백준 1904 01타일 BOJ 1904 01타일 파이썬 1904 01타일 Python 1904 01타일 1. 문제 www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 2. 풀이 dp[1] -> 0 -> 1개 dp[2] -> 00, 11 -> 2개 dp[3] -> 001, 100, 111 -> 3개 -> dp[2]에서 가장 뒤에 1추가 + dp[1]에서 가장 뒤에 00 추가 dp[4] -> dp[3]에서 가장 뒤에 1추가 + dp[2]에서 가장 뒤에 00..