전체 글

백준 2228번 자바 ☆☆

문제 https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net import java.util.Scanner; public class Main { static int N,M; static int[] arr; static int[] sum; static int[][] dp; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.next..

백준 1937번 자바

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net import java.util.Scanner; public class Main1937_1 { static int n; static int[][] map; static int[][] dp; static int[] ax = {1,-1,0,0}; static int[] ay = {0,0,-1,1}; static int max; public static int dfs(int x, int ..

백준 14002번 자바

문제 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net import java.util.LinkedList; import java.util.List; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in)..

백준 11053번 자바 ☆

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net import java.util.Scanner; public class Main11053 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int A = sc.nextInt(); int[] sequence = new int[..

LCS알고리즘 - 최장 공통 부분수열, 최장 공통 문자열(Longest Common Subsequence, Longest Common Substring)

1. 배경 코딩테스트 준비 중 여러 종류의 알고리즘을 만나다보니 머리로만 기억하는 것은 한계가 있다고 느끼고 지금부터라도 하나씩 차근차근 정리하려한다. 2. 개요 Longest Common Subsequence(최장 공통 부분수열) - 부분수열이라는 단어를 되뇌이면 이해하기 쉽다. - 예를 들어 두 문자열 ABCFH와 ACDBC에서 ABC가 LCS가 된다. - A와 BC는 연속되어있는 문자열은 아니지만 두 문자열에서 모두 공 통으로 존재하는 문자다. Longest Common Substring(최장 공통 문자열) - String.substring을 생각하면 쉽다. - 연속으로 이어진 공통 문자열이다. - 예를 들어 두 문자열 ABCFH와 ACDBC에서 BC가 LCS가 된다. 3. 예시 Longest Co..