전체 글

문제 링크 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를 만들 필요 없이 배열의 인덱스 값을 석차로 설정하면 된다! 그러면 성적 정렬을 할..

문제 링크 1. 다익스트라 알고리즘. 처음 접해보는 알고리즘이다. 유튜브 영상과 해답을 보며 공부하였다. 자료구조 시험칠 때 친구랑 얘기하다가 다익스트라 관련 얘기가 나왔었는데, 나는 그게 뭐냐고 안 배웠다고 하고 친구는 그걸 왜 모르냐고 중요한 건데 했던 웃픈 사연이 있는 알고리즘이다. 우리 교수님은 안 알려주셨는데 다른 교수님 수업에서는 가르쳐줬다고 한다. 중요한 알고리즘이다. 흔히 우리 주변에서 접할 수 있는 지도의 최단 경로를 구할 때도 이 알고리즘이 적용된다. 오늘 배우긴했지만 또 복습하자. 2. 그래프를 인접 행렬로 구성하면 안 된다. 문제의 조건 범위가 $0\leq V\leq20000$ 인데, 인접 행렬로 구성하게 되면 $20000\times20000=$ 대략 4억으로 메모리 초과가 난다. ..

문제 링크 1. 이전에 풀었던 기본적인 그래프 문제. 항상 BFS로만 풀어와서 이번에는 DFS로 풀어보았다. DFS가 좀 더 직관적인 것 같다. 2. 1. 가장 큰 높이 $h$ 부터 가장 낮은 $1$ 까지 높이를 하나씩 낮춰주며 기준을 잡는다. 2. 기준 높이 $h$ 보다 큰 영역은 물에 잠기지 않으므로 그러한 영역의 개수를 구한다. 3. 영역의 개수의 최대값을 출력한다. 이하 코드 참고 3. import java.util.Scanner; public class Main { static int[][] area; static int n; public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); ..