Algorithm

LIS - Longest Increasing Subsequence LIS는 '최장 증가 부분 수열'이란 뜻으로 어떠한 수열 내의 부분 수열들 중, 이전의 원소보다 다음 원소가 큰 원소들로만 이루어진 수열을 '증가 부분 수열' 이라고 하고, 이러한 증가 부분 수열들 중 가장 길이가 긴(원소의 개수가 많은) 수열을 최장 증가 부분 수열이라고 한다. (참고 - LCS란?) LCS는 Longest Common Subsequence 혹은 Longest Common Substring으로, S가 무엇을 뜻하냐에 따라 의미가 달라진다. Longest Common Subsequence 는 최장 공통 부분수열, Longest Common Substring는 최장 공통 문자열을 뜻하며, 둘의 차이는 아래 그림을 보면 쉽게 ..

가장 긴 증가하는 부분 수열 2 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; import java.util.stream.Collectors; /** * Created by ShinD on 2022-02-25. */ public class..

맨날 이분탐색 문제를 풀 때마다 while문의 탈출 조건으로 start > 1; if (arr[mid] > target) //중간값이 원하는 값보다 클 경우, 중간값이 작아져야 하므로 end를 줄인다 end = mid - 1; else //만약 중간값과 같다면? -> 더 우측 범위를 탐색하기 위해 start를 늘린다. start = mid + 1; } return end+1;//or start..

LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br ..

전깃줄 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.List; import java.util.concu..

가장 긴 증가하는 부분 수열 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.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Iterator; import java.uti..

쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.stream.IntStream; public class Main { private static BigInteger[][] dp = new BigInteger[101][10];//0~9 static { dp[1][0]= BigInteger.ZERO;..

정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 import annotation.boj.BOJ; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; @BOJ public class 백준1932 { private static int[][] dp; private static int[][] triangle; public static void mai..