모항이코딩한다

풀이방법 사용된 것: BigInteger 2022.03.31 매우 큰 숫자를 다룰 때 사용하는 BigInteger 클래스를 이용하거나, $n!$의 인수를 활용해 0의 개수를 세면 풀 수 있는 문제이다. 아래는 BigInteger 클래스를 사용한 정답 코드이다. 코드 Java(2022.03.31) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; public class Main { public static void main(String[] args) throws IOException{ // TODO Auto-generated method s..

풀이방법 사용된 것: 다이나믹 프로그래밍(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 번호를 입력받았다면 포켓몬 이름을 출력하고, 포켓몬 이름을 출력받았다면 번호를 출력해야 한다. 두 가지 기준으로 빠르게 자료를 찾아와야 하는 문제이다. 가장 적합한 자료구조가 무엇인지를 판단하는 게 관건이었다. 해시맵을 사용해야겠다는 생각은 쉽게 해낼 수 있었지만, 이름과 번호 두 가지 기준을 고려해야 한다는 까다로운 조건이 있어서 해시맵 사용을 해도 시간초과가 날..

풀이방법 및 문제점 2022.03.27 번호를 입력받았다면 포켓몬 이름을 출력하고, 포켓몬 이름을 출력받았다면 번호를 출력해야 한다. 두 가지 기준으로 빠르게 자료를 찾아와야 하는 문제이다. 결론부터 말하자면 HashMap 하나와 String[] 하나를 사용하면 된다. 이를 알아내기까지 두 번의 시행착오를 거쳤다. 먼저, 한 개의 HashMap만 사용해보았다. 시간초과가 발생한다. Key를 이용해 Value를 찾는 것은 빠르게 해낼 수 있지만 Value를 이용해 Key를 찾고자 할 경우엔 반복문을 사용해야 하기 때문이다. 시간복잡도가 제곱으로 불어난다. 그래서 다음으로는, 두 개의 HashMap을 사용해보았다. HashMap HashMap 동일한 데이터셋을 Key와 Value의 순서만 바꾸어 저장한 두 ..