본문 바로가기
728x90

백준116

[JAVA]백준 9252번: LCS 2 www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 설명 두 문자열의 최장 공통부분 수열의 길이를 출력하고 최장 공통부분 문자열을 출력한다. 2. 풀이 LCS(최장 공통부분 수열)의 길이를 구하고 역추적하여 최장 공통부분 문자열을 출력하는 문제이다. 혹시 LCS의 길이를 구하는 것부터 막힌다면 아래 문제를 먼저 풀어보는 걸 추천한다. www.acmicpc.net/problem/9251 9251번: LCS.. 2021. 2. 7.
[JAVA]백준 14003번: 가장 긴 증가하는 부분 수열 5 www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1. 문제 설명 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 구하고 가장 긴 증가하는 부분 수열을 출력하는 문제이다. 2. 풀이 가장 긴 증가하는 부분 수열을 푸는 방법에는 여러 가지가 있는데 DP를 이용한 방법과 이분 탐색을 이용한 방법이 있다. DP를 이용하는 방법의 경우 O(N^2)의 시간 복잡도가 걸리고 이분 탐색의 경우 O(NlogN)의 시간 복잡도를 가진.. 2021. 2. 5.
[JAVA]백준 12852번: 1로 만들기 2 www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1. 문제 설명 정수 X에 사용할 수 있는 연산이 3가지가 있다. X/2, X/3, X-1 위의 세가지 연산을 사용하여 주어진 정수 N을 1로 만들려고 할 때 연산을 사용하는 횟수의 최솟값과 1로 만드는 방법을 출력하는 문제이다. 2. 풀이 DP를 이용해서 최솟값을 구하고 그 순간들의 선택을 배열로 저장하여 역추적할 수 있다. dp 배열에는 현재 정수 N을 1로 만들 수 있는 최솟값을 저장하고 trace 배열에는 연산을 사용하였을 때 N 전의 값이 무엇인지 저장한다. X/3 연산을 사용하여 연산 횟수의 최솟값을 구하.. 2021. 2. 5.
[JAVA]백준 2096번: 내려가기 www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. 문제 설명 N 줄에 0 이상 9 이하의 숫자가 세 개씩 적혀있을 때 첫 줄에서 마지막 줄까지 내려가면서 얻을 수 있는 최대 점수, 최소 점수를 출력하는 문제이다. 내려가는 방법은 3가지가 있는데 아래 그림과 같다. 2. 풀이 메모리 제한이 있으나 신경 쓰지 않아도 풀 수 있는 문제이다. [N][3] 크기의 max와 min 배열을 만든 후 가능한 값들을 하나씩 더해가면서 max와 min 배열을 채워나가면 되는 간단한 문제.. 2021. 2. 1.
728x90

티스토리툴바