Dazzling 개발 노트

[백준] 9655 - 돌 게임 (Java) 문제 https://www.acmicpc.net/problem/9655 풀이/후기 다이나믹 프로그래밍 연습을 위해 선택한 문제인데, 점화식을 찾기 위해 패턴을 찾다가 홀수이면 SK, 짝수이면 SY인 점을 찾았다. 그래서 한 번 홀수, 짝수로 구현해 보니 바로 정답이 나왔다. DP니까 DP로 풀면 어떻게 되는지도 같이 확인했다. (결국엔 동일함) 코드 package DynamicProgramming; import java.io.*; public class Problem9655 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new I..

[백준] 1463 - 1로 만들기 (Java) 문제 https://www.acmicpc.net/problem/1463 풀이/후기 이코테에서 풀었던 1로 만들기와 거의 똑같은 문제였다. 차이점은 5 연산식이 없다는 것. 문제 복습을 위해 점화식을 직접 만들어봤는데, 몇 시간 전에 비슷한 문제를 풀었는데도 한 번에 잘 떠오르지 않았다. 복습이 중요할 것 같다...^^ https://da-zzling.tistory.com/35 코드 package DynamicProgramming; import java.io.*; public class Problem1463 { static int[] d = new int[1000000+1]; public static void main(String[] args) throws I..

문제 https://www.acmicpc.net/problem/11727 풀이/후기 이코테에서 풀었던 바닥 공사 문제와 완전히 동일하다 https://da-zzling.tistory.com/37 코드 package DynamicProgramming; import java.io.*; public class Problem11727 { static int[] d = new int[1000 + 1]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); d..

[백준] 11726 - 2 x N 타일링 (Java) 문제 https://www.acmicpc.net/problem/11726 풀이/후기 이코테에서 DP 유형의 문제를 풀다가, 타일링 문제가 대표적인 유형이라길래 백준에서 비슷한 문제를 풀어봄 총 3가지 경우가 나온다고 생각했는데, 1x2타일이 3번과 같은 경우가 되어 결국 2가지 경우가 나옴 이 부분은 유튜브 풀이 보고 알게된 점인데 역시 글로 여러번 읽는 것보다 영상으로 강의한번씩 듣는게 효과가 큰 것 같다@ 코드 package DynamicProgramming; import java.io.*; public class Problem11726 { static int[] d = new int[1000+1]; public static void main(St..

[백준] 16918 - 봄버맨 (Java) 문제 https://www.acmicpc.net/problem/16918 풀이/후기 처음 생각보다 막히지 않고 잘 풀었는데, 조금씩 정답 출력과 다른 부분이 있어 문제를 찾느라 시간이 좀 걸렸다. bombFunc()에서 if (arr[cx][cy] != 2) 부분을 해주지 않아 자꾸 폭탄이 있는데 터지지 않는(?) 현상이 발생했다. 디버깅으로 열심히 찾아내서 뿌듯함...! 그리고 자바로 제출한 사람들과 비교하니 제출 시간이 좀 걸리길래 StringBuilder로 sysout을 바꾸니 확실히 시간이 확 줄었다!!! 이것 또한 뿌듯! 코드 package GraphTheory; import java.io.*; public class Problem16918 { stat..

[백준] 2740 - 행렬 곱셈 (Java) 문제 https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 풀이/후기 행렬 곱셈 개념이 오랜만이라 다시 찾아보고 풀이하는데, 개념 자체는 어렵지 않았다. 근데 왜 이게 분할정복 문제인지는 의문이었음,, 이 문제를 풀면서 그렇게 느낀 사람이 많은 것 같은데 분할정복으로 풀려면 슈트라센 알고리즘을 이용해야 한다고 한다. .........ㅎ 일단 소스코드 참고용으로만 이해하고 넘어갔다. 코드 ..

[백준] 1629 - 곱셈 (Java) 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이/후기 수상할정도로 단순한 문제처럼 보이지만, 생각할 것이 많은 문제였다. 당연히 입력받은 값끼리 제곱하여 나머지 구하는 문제는 틀렸다고 채점된다. long 자료형 하나로 풀기는 가능하지만, 제곱을 하게되면 그 이상이 나오기 때문에 결과값이 달라 틀렸다고 채점되는것이다. 이 문제는 모르는 것을 인정하고 바로 검색을 하게됐는데, - 지수법칙 - 모듈러 합동 공식 이 두가지를 이용하면 간단하게 풀 수 있다. 두가지 방..

[백준] 1074 - Z (Java) 문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 풀이/후기 처음 풀이가 꽤 마음에 들었는데 배열의 크기가 3 이상이 되면서 잘 안됐당... 검색해보니 당연히 모든 배열을 다 채운 후에 답을 얻어내는 접근은 시간초과가 난다고 한다. 주어진 특정 부분만 돌아야 하므로 문제에서 주어진 r과 c가 어느 구역에 포함되는지를 판단해야 한다. 풀다가 막혀서 검색을 했었는데, 내 코드랑 가장 비슷한 코드를 ..