문제 링크 1. 이전에 풀었던 동전 1과 유사한 문제. 해당 문제의 풀이를 보고 복습하며 풀었다. 2. 동전 1 문제의 해설을 보고 이 해설을 보도록 하자. 차이점은 동전 1에서는 k 원을 만들 수 있는 모든 경우의 수를 구하지만, 동전 2에서는 최소한의 동전을 사용해서 만들 때 사용한 동전의 개수를 구하는 문제이다. 이를 위해서 다음과 같은 점화식을 세운다. dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1) 유의할 점은 다음과 같다. 1. dp 배열을 모두 100001로 초기화 한다. 사용한 동전의 개수가 최악일 경우 100,000개이다. (동전의 가치가 최대 100,000원이기 때문이다.) 따라서 이 최대 + 1인 100001로 초기화한다. 2. dp[0] = 0이다. ..

문제 링크 1. 예전에 풀었던 가장 긴 증가하는 부분 수열 (11053)의 응용문제이다. 해당 문제의 풀이법을 잊었었는데, 다시 복습하며 문제를 풀었다. 복습의 중요성을 깨닫는다. 2. 이번에 알게 된 것인데, 가장 긴 증가하는 부분 수열을 구하는 알고리즘을 부르는 명칭이 존재했다. 이는 LIS 알고리즘으로, Longes Increasing Subsequence 의 줄임말이다. 이번 바이토닉 부분 수열을 구할 때에 이 LIS 알고리즘을 잘 적용하여야 한다. 가장 긴 바이토닉 부분 수열은 증가하다가 감소하는 부분 수열의 길이가 가장 긴 것을 구해야 한다. 이를 다시 말하면, 1. 증가하는 부분 수열의 길이 값도 최대로 2. 감소하는 부분 수열의 길이 값도 최대로 하여야 한다. 즉, 증가하는 부분 수열의 d..

문제 링크 1. 익숙한 DP 문제. 비슷한 유형의 문제를 풀어봐서 그런지 점화식이 딱 보였다. 2. dp[i][j]는 지금까지 가져올 수 있는 사탕의 개수의 최댓값이다. 이는 위, 왼쪽, 왼쪽 위 중 큰 값을 기준으로 현재 위치의 사탕 값을 더 해주면 된다. 다만, 나는 왼쪽 위를 기준으로 잡지 않았다. 이는 최단 경로를 구하는 문제라면 고려해줘야 하겠지만 사탕 개수의 최대를 구하는 문제인데 사탕 개수가 감소할 일이 없기 때문에 그렇다. 3. import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n =..

문제 링크 1. 기본적인 피보나치 수열. 2. $N=3,4,5$ 정도까지 직접 써보면 피보나치 수열을 이룬다는 것을 쉽게 알 수 있다. 개수를 15746으로 나눈 나머지로 저장한다는 문제 조건을 잊으면 안 된다. 사실 처음에는 재귀 함수를 사용해서 풀어봤는데, 스택 오버플로우가 발생하였다. N이 최대 백만이니 재귀는 비효율적이라는 것을 알 수 있다. 3. import java.util.Scanner; public class Main { static int[] dp; public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); dp = new int[n + 1..

문제 링크 1. LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제 2차원 DP 배열을 구성하면 될 것이라 생각했는데, 비효율적으로 구성하다 보니 코드 짜기가 막막했다. 좀 더 획기적인 방법이 필요했다. 어렵다. 지친다. 2. dp 배열의 행은 비교당할 문자열 (CAPCAK ), 열은 비교할 문자열 (ACAYKP ) 이다. dp[i][j] 는 문자열 b의 i번째, 문자열 a의 j번째 위치까지 구해진 LCS의 값이다. ACAYKP CAPCAK dp[3][2] = 1 ACAYKP CAPCAK dp[3][3] = 2 ACAYKP CAPCAK dp[3][6] = 3 j번째 알파벳이 i번째 알파벳과 같으면 1이 증가한다. 어떤 값에서 1이 증가할까? 고민해보면, 그 전까지의 공통부..

문제 링크 1. sloved에 그리디 문제로 분류되어 있길래 탐욕스러운 사고기법을 적용해보려 했지만 떠올리지 못했다. 해설을 찾아보니 그리디 문제로 풀면 못푼단다. 이 문제의 분류를 수학, 백트래킹으로 바꿔야 할 듯하다. 중학교 때 이런 문제와 비슷한 창의 수학 문제를 풀었던 것 같은데.. 흠 2. 수학적 방식은 매우 심플하면서도 획기적이다. 높은 자릿수의 알파벳에 가중치를 부여하는 방식이다. $GCF$ 와 $ACDEB$ 두 가지 단어를 예로 들면, $GCF = 100G+10C+F$ $ACDEB = 10000A+1000C+100D+10E+B$ 이므로 $GCF+ACDEB = 10000A+1010C+100D+100G+10E+B+F$ 이다. 따라서 높은 자릿수인 $A$부터 $9$를 넣으면 단어의 합이 최댓값이..

문제 링크 1. 브루트포스 문제. 순차적으로 완전 탐색을 하면 되는 단순하지만 유용한 알고리즘이다. 오랜만에 접해서 그런가 많이 헤맸다. 사용자 정의 class를 만들어 별의별 짓을 하다가 멘탈 나가서 풀이를 찾아보았다. 단순하게 생각하자! 2. 선택정렬과 유사한 느낌으로 풀면 된다. 키와 몸무게를 각각 비교하여 작은 쪽의 rank 인덱스를 1 증가시킨다. 처음 모든 인원의 순위를 1로 초기화하고 순위가 밀려나는 형식의 아이디어가 중요하다. 3. import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new ..

문제 링크 1. 노트에 좀 끄적이다가 아이디어가 떠올라 코드를 쭉 썼다. 아무 생각 없이 제출했으나 시간 초과.. 나는 list를 이용해서 서류 성적을 기준으로 정렬하고 list를 순회하며 값을 비교하기 위해 이중 for문을 사용하였다. 하지만, 이중 for문을 사용하면 $O(N^{2})$ 인데 지원자의 최대 수가 $100,000$ 이므로 시간 초과가 날 수밖에 없다. 결국 이중 for문을 사용하지 않는 방법을 찾아야 하는데 찾지 못해 풀이를 참고하였다. 2. 그 방법은 생각보다 단순했다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다. 문제에서, 동석차가 없다고 하였으므로 사용자 정의 Class를 만들 필요 없이 배열의 인덱스 값을 석차로 설정하면 된다! 그러면 성적 정렬을 할..