REC

문제 설명https://www.acmicpc.net/problem/9251LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.예제 입력 1ACAYKPCAPCAK예제 출력 14풀이 과정일반적으로 LCS (Longest Common Subsequence) 알고리즘은 두 문자열 A, B가 입력으로 주어질 때 양쪽 문자열 모두에 등장하..

.문제 설명https://www.acmicpc.net/problem/1932 7 3 8 8 1 0 2 7 4 44 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.입력첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄..

문제 설명https://www.acmicpc.net/problem/9461아래 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)출력각 테스트 케이스마다 P(N..

문제 설명https://www.acmicpc.net/problem/117262×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.예제 입력 12예제 출력 12예제 입력 29예제 출력 255풀이 과정클래스 3 미해결 문제로 있어서 풀었는데 너무 쉬워서 머쓱했던 문제…규칙을 찾기 위해 n = 1부터 4까지 해보다가 현재의 모양이 과거의 모양을 이룬 것에 + 알파의 모양 이라는 것을 깨달았습니다.1) 과거의 결과를 중복해서 사용함 2) 작은 문제의 최..

문제 설명 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com크기가 N인 파스칼의 삼각형을 만들어야 한다.파스칼의 삼각형이란 아래와 같은 규칙을 따른다.첫 번째 줄은 항상 숫자 1이다.두 번째 줄부터 각 숫자들은 자신의 왼쪽과 오른쪽 위의 숫자의 합으로 구성된다.N이 4일 경우,N을 입력 받아 크기 N인 파스칼의 삼각형을 출력하는 프로그램을 작성하시오.[제약 사항]파스칼의 삼각형의 크기 N은 1 이상 10 이하의 정수이다. (1 ≤ N ≤ 10)[입력]가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다. 각 테스트 케이스에는 N이 주어진다.[출력]각 줄은 '#t'로 시작하고, ..

문제 설명https://www.acmicpc.net/problem/11053수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력 - 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)출력 - 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 예제 입력 1610 20 10 30 20 50예제 출력 14예제 입력 241 10 2 3예제 출력 23풀이 과정# 입력N = ..

문제 설명https://www.acmicpc.net/problem/2293요약) n가지 종류의 동전으로 k원을 만드는 경우의 수를 출력합니다. 동전의 중복 사용이 가능합니다.예제 입력3 10125예제 출력105,5 / 1,1,1,1,1,1,1,1,1,1 / 1,2,2,5 / 1,1,1,1,1,5 / 2,2,2,2,2 / 1,1,2,2,2,2 / 1,1,1,1,2,2,2 / 1,1,1,1,1,1,2,2 / 1,1,1,1,1,1,1,1,2 / 1,1,1,2,5 로 총 경우의 수가 10가지입니다.풀이 과정dp[i]는 i를 만들 수 있는 경우의 수 입니다.1) 1을 사용해서 10을 만들 수 있는 경우의 수 -> 1만 사용 가능2) 2를 포함해서 10을 만들 수 있는 경우의 수 -> 1과 2 사용 가능3) 5를 ..

문제 설명https://www.acmicpc.net/problem/1495요약) 곡의 개수 N과 시작 볼륨 S, 볼륨의 최댓값 M, 그리고 더하거나 줄여서 볼륨을 조정할 수 있는 볼륨의 차이 V가 주어졌을 때, 마지막 곡을 연주할 때 최대 볼륨을 가지도록 하는 프로그램을 작성해야 합니다. 입력 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이 V가 N개의 리스트로 주어진다. (1 ≤ V[i] ≤ M) V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 ..

문제 설명https://www.acmicpc.net/problem/1904요약) '00'과 '1'을 사용해서 길이가 N인 2진 수열을 만들어야 합니다. 만들 수 있는 길이가 N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력하면 됩니다. 입력 N은 1 이상, 1,000,000 이하로 주어집니다.예제 입력 14예제 출력 15-> 00과 1을 이어붙여 만들 수 있는 2진 수열 중에 크기가 4인 것은 1001, 1100, 0011, 0000, 1111 로 총 5개입니다.풀이 과정DP는 하나의 문제를 여러 개의 중복되는 문제로 나누는 Overlapping subproblems와, 작은 문제의 답들을 재사용하여 큰 문제의 정답을 구할 수 있다는 Optimal substructure의 조건을 만족해야 ..

문제 설명 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이 과정def solution(triangle): for i in range(1, len(triangle)): for j in range(len(triangle[i])): if i > 1 and j != 0 and j != len(triangle[i-1]): triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j]) elif j == 0: triangle[i][j] += triangle[..