모항이코딩한다

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 2022.03.30 "ACAYKP"와 "CAPCAK"를 예로 들어 설명하겠다. 다음의 표를 보자. C A P C A K A 0 1 1 1 1 1 C 1 1 1 2 2 2 A 1 2 2 2 3 3 Y 1 2 2 2 3 3 K 1 2 2 2 3 4 P 1 2 3 3 3 4 C A P C A K A 0 1 1 1 1 1 C 1 1 1 2 2 2 A 1 2 2 2 3 3 Y 1 2 2 2 3 3 K 1 2 2 2 3 4 P 1 2 3 3 3 4 (1, 1)은 "ACAYKP"의 첫 번째 글자까지와 "CAPCAK"의 첫 번째 글자까지, 즉 "C"와 "A"를 비교하였을 때 가장 긴 공통 부분수열의 길이이다. "C"와 "A"는 서로 공통된 글자가 하나도 없으므로 (1, ..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) TreeSet 각각의 동전의 가치 값들을 저장하는 데 트리셋을 사용하였다. 중복값을 없애기가 편하고, 집합에 포함된 모든 값을 각각 한 번씩만 이용할 때 pollFirst()가 편해서 사용하였다. 2022.03.30 다이나믹 프로그래밍 문제이다. k원의 금액을 만들어야 할 때, 1원의 금액의 경우부터 k원의 금액에 이르기까지 자신보다 적은 금액의 동전 개수를 이용해 자신의 금액을 구해가며 차근차근 최적의 데이터를 알아낼 수 있기 때문이다. 크기가 k+1인 정수형 1차원 배열 dp를 만든 다음, dp[i]에 i원을 만들기 위한 최소의 동전 개수를 저장한다. 그 후 dp[k]의 값을 이용하여 답을 구하면 된다. 첫 몇 개의 데이터를 가지고 손으로 직접 구해보면..

풀이방법 사용된 것: 반복문 2022.03.29 매우 간단한 문제이다. 문제에서 말하는 과정을 계속 반복해주면서, 몇 번 반복했는지 세어주면 된다. 앞 숫자는 (수)/10 으로, 뒷 숫자는 (수)%10 으로 구할 수 있다. 코드 Java(2022.03.29) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new Inp..

풀이방법 사용된 것: BufferedReader BufferedWriter 2022.03.29 빠른 입출력 방식을 사용해야 풀리는 문제이다. Scanner와 System.out.print의 반복적인 사용으로는 풀 수 없다. BufferedReader, BufferedWriter, StringBuilder 등을 사용하면 된다. 문제는 쉽지만 궁금증이 하나 생겨서 적어둔다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokeniz..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 2022.03.28 매우 간단한 문제이다. 정수 k를 입력받았을 때 출력해야 하는 문자열을 "$zero_k$ $one_k$"라고 할 때, $zero_k = zero_{k-2} + zero_{k-1}$ $one_k = one_{k-2} + one_{k-1}$ 이다. 따라서, 크기가 41인 배열을 만든 후 배열의 0번 요소부터 40번 요소까지 반복문을 돌리며 덧셈을 해주면 문제에서 요구할 수 있는 모든 정수에 대한 답이 저장된 배열이 완성된다. 이후 들어오는 입력값에 따라 이 배열에서 정답을 꺼내 출력하면 된다. 코드 Java(2022.03.28) import java.io.BufferedReader; import java.io.IOException; impo..

풀이방법 사용된 것: HashSet 이 문제에서는 중복값을 허용하지 않는 자료구조를 사용하는 것이 편리하고 정렬은 필요 없기 때문에 해시셋을 사용했다. 2022.03.28 연산이 한 줄에 하나씩 주어질 때마다 StringTokenizer를 사용하여 첫 번째 단어를 가져온다. 이 첫 번째 단어를 기준으로 switch case문을 돌린다. 단, 시간초과에 유의해야 한다. check 연산 시마다 System.out.println()을 실행하면 시간초과가 발생한다. 더 빠른 출력 방식을 사용해야 한다. 아래 코드에서는 StringBuilder를 이용하였다. all 연산에 드는 시간도 줄이기 위하여, for(int j = 1; j

풀이방법 사용된 것: ArrayList 동적 프로그래밍(DP) 2022.03.27 문제에 나온 대로 이름점을 보면 되는 문제이다. 이전 단계의 덧셈의 결과가 이번 단계에서 덧셈의 대상이 되기 때문에 동적 프로그래밍 문제라 볼 수 있다. ArrayList dp를 사용했다. Vector나 Queue 등을 사용해도 된다. 복잡하지 않은 알고리즘이고 코드도 간단하다. 코드를 읽으면 바로 알고리즘을 이해할 수 있다. 그런데 글로 설명하자면 상당히 길다. 귀찮지만, 혹시라도 나 자신이 이 문제의 풀이를 까맣게 잊는다면 다시 읽을 수 있도록... 열심히 설명해보겠다. 편의를 위한 용어정리 설명의 편의를 위해, 이 글에서는 두 수를 더한 뒤 그 합에 (mod 10) 연산을 하는 것을 '덧셈'이라고 부르겠다. 이 연산에..

풀이방법 사용된 것: HashMap 2022.03.27 오답노트 #1620 : 나는야 포켓몬 마스터 이다솜 풀이방법 및 문제점 2022.03.27 번호를 입력받았다면 포켓몬 이름을 출력하고, 포켓몬 이름을 출력받았다면 번호를 출력해야 한다. 두 가지 기준으로 빠르게 자료를 찾아와야 하는 문제이다. 결론 blowupmomo.tistory.com 번호를 입력받았다면 포켓몬 이름을 출력하고, 포켓몬 이름을 출력받았다면 번호를 출력해야 한다. 두 가지 기준으로 빠르게 자료를 찾아와야 하는 문제이다. 가장 적합한 자료구조가 무엇인지를 판단하는 게 관건이었다. 해시맵을 사용해야겠다는 생각은 쉽게 해낼 수 있었지만, 이름과 번호 두 가지 기준을 고려해야 한다는 까다로운 조건이 있어서 해시맵 사용을 해도 시간초과가 날..

풀이방법 사용된 것: Comparator 오버라이딩 정렬 2022.03.26 Comparator를 오버라이딩한 후 Arrays.sort()를 사용해 정렬하면 된다. 코드 Java(2022.03.26, Comparator를 미리 정의해둔 뒤 불러내는 방법) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; public class Main { static String[] arr; public static void main(String[] args) throws IOException{ // TODO ..

풀이방법 2022.03.26 테스트케이스의 개수가 주어지지 않았을 때 어떻게 해야 하는지를 알 수 있는 문제이기 때문에 코드를 적어둔다. BufferedReader는 입력값의 내용물이 없을 경우 null을 가져다준다. 따라서 다음 입력값의 내용물이 null일 경우 반복문을 실행하지 않도록 하면 된다. 코드 Java(2022.03.26) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ // ..