문제 : 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 해당 문제는 수열 A 가 주어졌을때, 가장 긴 증가하는 부분 수열, LIS (Longest Increasing Subsequence) 의 길이를 구하는 문제이다. 다이나믹 프로그래밍에서 가장 중요한 것은 규칙을 찾거나, 일반식을 찾는 것이다. 먼저, arr[1] < arr[2] 이므로 dp[2] = dp[1] ..
문제 : https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 해당 문제는 피보나치 수열 중 하나를 호출하는 데에 필요한 피보나치(0) 과 피보나치 (1) 함수의 호출횟수를 카운트하는 문제이다. 이러한 문제는 전에 풀어본 유형인 다이나믹 프로그래밍으로, 5까지만 호출횟수를 세어도 DP 유형임을 파악할 수 있다. 다이나믹 프로그래밍에 관한 포스팅은 이전 포스팅인 "9095번 : 1,2,3 더하기 " 문제에서 자세히 다루었으니 참고하면 된다. https://codingjust.tistory.com/21 import java.io.BufferedRea..
다이나믹 프로그래밍 (DP) 해당 문제의 알고리즘을 확인해보면 '다이나믹 프로그래밍' 이라고 되어 있다. 이는 동적 계획법이라고도 불리며, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 이는 큰 문제를 작은 문제로 쪼개서, 그 답을 저장해두고 재활용하는 방식으로 자주 쓰인다. (기억해가면서 풀기) DP를 쓰는 이유 일반적인 재귀 방식 또한 DP와 매우 유사하다. 하지만 둘의 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다. 예를 들어 피보나치 수열을 살펴보자. 피보나치 수열은 다음과 같다. 1, 1, ..
문제 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 해당 문제는 전에 풀었던 1929번 : 소수 구하기와 매우 유사한 문제이다. ( 풀이 : https://codingjust.tistory.com/19) 해당 문제도 '에라토스테레스의 체' 알고리즘을 사용하여 풀이하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public ..
문제 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 해당 문제는 범위가 주어지면 범위 내의 소수를 찾아내는 문제인데, 아래 코드와 같이 2중 for문으로 코드를 작성하니 시간 초과가 발생하였다. // 시간 초과가 발생한 알고리즘 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.nio.Buffer; import java.util.Sca..
자바를 이용해 백준 문제들을 풀다 보면, Scanner 를 이용해 입력받으면 시간 초과가 나는 경우를 경험할 수 있다. 이는 Scanner보다 더 빠르게 처리해주는 BufferedReader 를 이용해 입력받으면 해결이 가능하고, BufferedReader를 이용해 입력받았는데도 시간 초과가 난다면 내 알고리즘을 다시 체크해봐야 한다. [BufferedReader 선언방법] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedReader 는 해당 ..
인프런 김영한님의 강의를 듣다 보면, 명령어를 실행할 때 마다 화면 아래에서 단축키에 대한 정보가 표시됨을 알 수 있다. 해당 기능은 인텔리제이 내의 플러그인을 설치하면 가능하다. Settings -> Plugin 에서 Key Promoter X 를 검색한다. 설치하고 재시작하면 알림이 나오는데, 아래 사진처럼 오른쪽 아래에 알림창이 나오는 것이 기본 설정이다. 강의에 나오는 것 처럼 화면 중앙에 이쁘게 표시되는 것을 원하면, Settings -> Plugins -> Presentation Assistant 검색 후 설치한다. 해당 플러그인을 설치하게 되면, 이와 같이 화면 하단에 초록 배경으로 이쁘게 볼 수 있다!.
문제 : https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 3중 for문을 이용하여 풀이하면 된다. 다만, for 문을 작성할 때, for (int i=0;i
김영한님의 스프링부트의 입문 강의 중 "순수 JDBC" 에 관한 내용을 듣다 보면, SpringConfig 파일에 DataSource 에 관한 내용을 추가하는 내용이 있다. 강의에서 알려주시는 대로 진행했는데도, localhost:8080 에 접속해보면 도메인 화면은 들어가지지만 members 화면은 WhiteLabel Error 페이지가 뜬다. 오류를 확인해보려 인텔리제이를 들어가보면, 이와 같이 "org.h2.jdbc.JdbcSQLInvalidAuthorizationSpecException: Wrong user name or password" 가 나온다. 이는 스프링부트 2.4 이후 버전부터는 데이터베이스에 커넥션을 추가할 때 username을 반드시 알려주어야 하기 때문에 생기는 오류이다. 이를 해..
