모항이코딩한다

풀이방법 사용된 것: 다이나믹 프로그래밍(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의 순서만 바꾸어 저장한 두 ..

풀이방법 사용된 것: 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{ // ..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 2022.03.24 i번째 수에 도착할 때까지 도출할 수 있는 가장 큰 합의 값을 dp[i]에 저장하는 1차원 정수 배열 dp를 만든다. dp를 완성한 뒤, dp의 데이터 중 삼각형의 가장 아래층에 해당하는 것들만 빼내온 뒤 그 중 최댓값을 화면에 출력하면 해결된다. 이 dp를 만드는 방법은 다음과 같다. 삼각형에 속한 모든 수는 자신의 오른쪽 위 또는 왼쪽 위 중 하나를 선택하여야 한다. 따라서, 1층과 2층에 대하여는 다음과 같이 직접 dp 값을 넣어주고, dp[1] = arr[1]; dp[2] = dp[1] + arr[2]; dp[3] = dp[1] + arr[3]; 3층부터 마지막 층까지는 다음과 같은 반복문을 돌려주면 된다. for(int i = ..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 수학(방정식) 그리디 알고리즘 이 문제의 여러가지 해법 중, 다이나믹 프로그래밍으로 푸는 방법과 5000 이하의 모든 자연수 $n$에 대하여 $5x + 3y = n$을 푸는 방법 두 가지로 풀어보았다. 2022.03.24(1) 다이나믹 프로그래밍으로 푸는 방법이다. 모든 자연수는 다음의 네 가지 경우 중 하나이다. 3의 배수와 5의 배수의 합으로 만들어진 수에 5를 더하여 도출됨 3의 배수와 5의 배수의 합으로 만들어진 수에 3을 더하여 도출됨 1번과 2번 모두 가능함 1번과 2번 중 어떤 것도 불가능함 따라서, 길이가 5001인 1차원 정부 배열 dp를 만들어서 초기의 값들만 다음과 같이 정의해두고 dp[0] = -1; dp[1] = -1; dp[2] =..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 2022.03.24 수 n에 대한 정답의 값이 dp[n]에 저장되어있는 int형 1차원 배열 dp를 미리 만들어둔다. 그 후, 입력값을 받아 그 수에 맞는 답을 dp에서 꺼내오면 된다. dp를 만들어두는 방법은 다음과 같다. 이 문제에서 수 n이 만들어질 수 있는 방법은 다음의 세 가지 뿐이다. 어떤 수에 2를 곱하여 만들어짐 어떤 수에 3을 곱하여 만들어짐 어떤 수에 1을 더하여 만들어짐 따라서, 초기의 값들만 다음과 같이 직접 정의해두고 dp[1] = 0; (1 본인이므로 연산 0회만에 1을 도출) dp[2] = 1; (2로 나누는 연산 1회, 혹은 1을 빼는 연산 1회만에 1을 도출) dp[3] = 1; (3으로 나누는 연산 1회만에 1을 도출) 다음..