본문 바로가기

백준46

[백준 9251] LCS - 자바 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 풀이 우선 LCS에 대해서 이해를 해야 한다고 생각합니다. LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 즉, bcba는 abcbdab와 bdcaba의 LCS입니다. 이 문제를 처음 접했을때, 여러가지 생각을 해봤지만, .. 2020. 4. 2.
[백준 1149]RGB거리 - 자바 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 문제의 조건을 보면 i번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다고 나와있습니다. 전형적인 DP문제이며, RGB 3가지 색으로 구별하였으므로 3가지 방향으로 나누어 접근하도록 합니다. 즉, 3가지 방향으로 접근하여 N번째 까지의 드는 비용들을 전부 메모이제이션하고, 마지막에 N번째의 최소 값을 구하면 됩니다. R G B 1번 집 .. 2020. 4. 2.
[백준 11726] 2xn 타일링 - 자바 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 1. 풀이 처음에 문제만 보고는 당황하게 됩니다.. 하지만 직접 1부터 세보면서 규칙을 보면 피보나치 수열이 되는 것을 볼 수 있습니다. 1 : 1 2 : 2 3 : 3 4 : 5 5 : 8 6 : 13 7 : 21 8 : 34 9 : 55 ... 주의할 점은 입력값이 1일때도 1을 출력해서, memo의 크기를 입력값+1을 하게되면, 1을 입력했을때 문제가 됩니다. 그러므로, 애초에 memo의 배열 크기를 입력값의 제.. 2020. 4. 1.
[백준 1003]피보나치 함수 - 자바 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. 풀이 피보나치 수열을 재귀를 사용하여 풀때, 0과 1의 호출 횟수를 구하는 문제입니다. 피보나치의 재귀 동작 순서가 쓰여져있어서, 처음엔 피보나치 수열을 재귀적으로 풀어서 정답을 구하려다보니 시간 초과가 발생해서 DP를 사용하여 풀게 되었습니다. 우선, 피보나치의 0과 1의 호출 횟수는 아래와 같은 규칙을 가집니다. n memo[i][0] 0 호출 횟수 memo[i][1] 1 호출 횟수 0 1 0 1 0 1 2 1 1 3 1 2 4 2 3 memo[i][j] = memo[i-1][j] +.. 2020. 4. 1.
[백준 9095]1, 2, 3 더하기 - 자바 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 1. 풀이 DP로 풀려고 노력했지만, 처음엔 규칙을 찾지못했는데, 5를 만드는 1,2,3을 더하는 경우의 수가 13임을 발견하.. 2020. 4. 1.
[백준 1463] 1로 만들기 - 자바 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. 풀이 이 문제는 DP 점화식을 사용하여 풀이하면 된다. DP는 모든 경우의 수를 순회해야 할 때, 중복되는 순회를 빠르게 처리하기 위해 생긴 것이다. 그만큼 메모리가 차지하는 단점이 있긴하다. D[n을 1로 만드는 횟수] = (1) D[n/3을 1로 만드는 횟수] + 1 (2) D[n/2을 1로 만드는 횟수] + 1 (3) D[n-1을 1로 만드는 횟수] + 1 이 중에서 제일 작은 값을 골라서 D[n]에 저장하면 되는 것입니다. 즉 아래와 같은 코드가 됩니다. memo[n] = memo[n-1] + 1;.. 2020. 4. 1.

티스토리툴바