전체 글
-
H - Grid 1 / atcoder.jpatcoder.jp 2020. 1. 1. 17:45
H - Grid 1 / atcoder.jp 문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_h Submission : https://atcoder.jp/contests/dp/submissions/9270190 Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/H%20-%20Grid%201/src/Main.java 한번 풀어봤던 문제였기도 했지만, 한번에 풀었습니다. System.in 에서 입력받는 양이 많아 질 수록, Scanner의 next???() 메서드에서 사용되는 시간이 많이 집니다. readByte()를 사용해서 최대한 System.in 에서 읽는대 걸리는 시간을 최대한 줄여야 합니다..
-
G - Longest Path / atcoder.jpatcoder.jp 2020. 1. 1. 15:50
문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_g 문제 해설 : https://jinpyo.kim/EducationalDP-solution Submission : https://atcoder.jp/contests/dp/submissions/9268425 Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/G%20-%20Longest%20Path/src/Main.java Educational DP Contest에서 그래프 문제가 처음 나왔습니다. 우선 단어의 뜻을 잘 이해할 필요가 있습니다. -directed : 한쪽 방향으로만 이라는 뜻이구요, -edge가 1→2 이렇게 1에서 2로가는 것만 ..
-
F - LCS / atcoder.jpatcoder.jp 2019. 12. 31. 12:04
F - LCS / atcoder.jp 문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_f 문제 해설 : https://jinpyo.kim/EducationalDP-solution 이번 풀이는 참고했던 문제해설과는 약간 다른게 풀어졌습니다. Submission : https://atcoder.jp/contests/dp/submissions/9250597 Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/F%20-%20LCS/src/Main.java LCS 문제입니다. LongestLongest common subsequence 문제입니다. Longest common substring은 다른 문제..
-
E - Knapsack 2 / atcoder.jpatcoder.jp 2019. 12. 29. 19:41
문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_e 문제 해설 : https://jinpyo.kim/EducationalDP-solution Submission : https://atcoder.jp/contests/dp/submissions/10059004 Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/E%20-%20Knapsack%202/src/Main.java 이전 문제인 'D - Knapsack 1'의 풀이를 그대로 적용하면, Sample Input 1~3에서는 올바른 값이 나올 수도 있지만, 실제 이 문제는 약간 다른 방식으로 접근해야 합니다. 문제의 Constrain..
-
3. Longest Substring Without Repeating Characters / leetcode.com카테고리 없음 2019. 12. 28. 12:36
Dicussion에 보니까, O(N)방법도 가능하더라구요... 어제.. 아니지, 오늘 새벽에 잠안와서 코딩하느라고, O(N^2)으로 풀었네요 ㅋㅋ ps : 잠 안온다고, 코딩하지 맙시다. 문제 링크 : https://leetcode.com/problems/longest-substring-without-repeating-characters/submissions/ 문제 해설 : https://velog.io/@yejinh/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-LeetCode-Longest-Substring-Without-Repeating-Characters-3rk3n08jvu Submission : https://leetcode.com/submissions/detail/28911..
-
D - Knapsack 1 / atcoder.jpatcoder.jp 2019. 12. 27. 19:12
문제링크 : https://atcoder.jp/contests/dp/tasks/dp_d Submission : https://atcoder.jp/contests/dp/submissions/9158698 Java code : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/D%20-%20Knapsack%201/src/Main.java import java.io.*; import static java.lang.Long.max; // D - Knapsack 1 / https://atcoder.jp // 문제링크 : https://atcoder.jp/contests/dp/tasks/dp_d // Submission : https://atcoder.jp/cont..
-
C - Vacation / atcoder.jpatcoder.jp 2019. 12. 27. 17:35
문제 링크 : https://atcoder.jp/contests/dp/submissions/9157155 답 링크(속도 최적화 하기전) : https://atcoder.jp/contests/dp/submissions/9157155 답 링크(속도 최적화된) : https://atcoder.jp/contests/dp/submissions/9157155 자바 코드 : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/C%20-%20Vacation/src/Main.java 문제 정의에 따라서 a, b, c 를 아래와 같이 가정하고, \begin{aligned} a = 0, b = 1, c = 2 \\ 1 \leq N \leq 10^5 \\ (1 \leq i \l..
-
알고리즘 문제풀이 사이트에서 자바로 풀때 속도 올리는 방법카테고리 없음 2019. 12. 26. 20:33
atcoder.jp 에서 'B - Frog 2' 문제를 자바로 풀어 보다가, '왜 내 코드는 다른 사람들 보다 느릴까?' 고민한 끝에... 간단한 문제이기는 하지만, 드디어 속도로 4등했습니다. ^^ 처음에는 489ms 부터 시작했습니다. 마지막에는 118ms까지 줄였네요 그래서 이번에는 속도를 개선하는 방법에 대해서 이야기 해보려고 합니다. 처음 코드와 마지막 최적화 된 코드를 비교해 보실 분은 아래 링크를 참고하세요. 처음 Accept된 코드 489ms : https://atcoder.jp/contests/dp/submissions/9143731 최종 Accpet된 코드 118ms : https://atcoder.jp/contests/dp/submissions/914391..