반응형 알고리즘12 [백준] 9095번 - 1,2,3 더하기 (Java) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 메모이제이션을 좀 안다고 생각했는데 한 방 먹은 문제다. 1시간 동안 고민했는데 풀지 못했다. 알고 봤더니 1~3까지 숫자를 계산할 때 약간의 상상력을 보태야 하는데 그까지 생각이 미치지가 못했다. * DP(Dynamic Programming) 문제 푸는 공식 3단계 1) DP 테이블 정의 2) 점화식 찾기 3) 초기값 정하기 1) DP 테이블 정의 - DP테이블은 1,2,3의 합으로 조합할 수 있는 경우의 수를 가진다. - 정수 n은 < 11이므로 DP[10+1]로 구성해서 값을 미리 구한 다.. 2022. 9. 28. [백준] 1003번 - 피보나치 함수 (Java) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. DP 테이블의 성격 정의 - DP[N][2]로 생성해서 DP[i][0]에는 0의 출력 횟수, DP[i][1]에는 1의 출력 횟수를 저장한다. - N 2022. 9. 27. [백준] 1463번 - 1로 만들기 (Java) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP(Dynamic Programming) 문제 푸는 공식 3단계 1) DP 테이블 정의 2) 점화식 찾기 3) 초기값 정하기 1. 테이블 정의 DP[i] = 정수 i를 1로 만들때까지 걸리는 연산 횟수의 최소값 2. 점화식 찾기 DP[12]의 경우 a. 3으로 나눌 경우 -> DP[12] = DP[4] + 1 -> DP[x] = DP[x/3] + 1 b. 2로 나눌 경우 -> DP[12] = DP[6] + 1 -> DP[x] = DP[x/2] + 1 c. 1을 뺄경우 -> DP[12] = DP[11] + 1 .. 2022. 9. 26. [백준] 9935번 - 문자열 폭발 (Java) 1. 문자열을 폭발문자열로 split 한 다음 머지하자. 2. 머지한 문자열을 다시 재귀호출하자. 2-1. 문자열에서 폭발문자열이 없으면 문자열 리턴 2-1. 문자열의 사이즈가 0이면 "FRULA"리턴 import java.util.*; import java.io.*; /* [백준] 9935번 - 문자열 폭발 (Java) */ public class Main { static String str, bom; void InputData() { Scanner in = new Scanner(System.in); str = in.next(); bom = in.next(); } String DFS(String s) { if (!s.contains(bom)) { if (s.length() == 0) return "FR.. 2022. 9. 21. [백준] 14490번 - 백대열 (Java) 문자열을 split 해서 분리하는 것과 최대공약수를 구하는 법을 알아야 한다. 최대공약수는 유클리드 호제법을 이용해서 구현했다. import java.util.*; import java.io.*; /* [백준] 14490번 - 백대열 (Java) */ public class Main { static int N, number; static int A[]; void InputData() { Scanner in = new Scanner(System.in); //N = in.nextInt(); String str = in.next(); String s[] = str.split(":"); A = new int[2]; for (int i=0; i 2022. 9. 21. [백준] 11720번 - 숫자의 합 (Java) (방법 #1) 숫자가 문자열 한개로 입력된다. 입력 받은 문자열을 char 배열로 잘라서 정수형 배열에 나눠 담아야 한다. 나눠담은 정수형 배열을 순차적으로 더하면 된다. (방법 #2) 정수 하나로 받아서 MOD를 사용해서 각 자리수를 계산할 수 있다. import java.util.*; import java.io.*; /* [백준] 11720번 - 숫자의 합 (Java) */ public class Main { static int N, number; static int A[]; void InputData() { Scanner in = new Scanner(System.in); N = in.nextInt(); String str = in.next(); A = new int[N]; for (int i=0; i 2022. 9. 21. [백준] 2206번 - 벽 부수고 이동하기 (Java)(△) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. 최단거리 구하기 문제이므로 BFS 탐색을 사용하면 된다. 2. 벽을 한개까지 부술 수 있다. 탐색 시에 벽을 만나도 한번 더 나갈 수 있다는 뜻. 2-1. 최대 한개까지 1 -> 0으로 바꿀 수 있다. 2-2. 벽 공사 여부를 변수로 넣고 dist 배열을 dist[N][M][2]개로 만들어서 관리 2-3. 벽을 한번도 안 뚫은 경우는 dist[][][0]으로 거리 저.. 2022. 9. 20. [백준] 1436 - 영화감독 숌 (Java) https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 1. 부르트포스 알고리즘을 이용해서 한자리씩 수를 증가시키면서 "666"이 포함되었으면 count++한다. 2. if (count == N)이면 그 때의 수를 리턴한다. 3. 문자열 체크는 정수를 String으로 바꾼다면 contains(문자)로 검색하면 된다. import java.util.*; import java.io.*; /* [백준] 1436 - 영화감독 숌 (Java) */ publi.. 2022. 9. 19. [백준] 10872번 - 팩토리얼 (Java) https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 팩토리얼은 그 수 보다 작은 모든 정수의 곱이다. 5! = 5 x 4 x 3 x 2 x1이다. 즉, n! = n x (n-1)!과 동일하다. 이를 재귀함수로 구성하자. import java.util.*; import java.io.*; /* [백준] 10872번 - 팩토리얼 (Java) */ public class Main { static int N; void InputData() { Scanner in = new Scanner(System.in); N = in.nextInt(); } // 재귀함수로.. 2022. 9. 19. 이전 1 2 다음 반응형
