1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 import java.util.*; //dfs 기본 public class Main { static int nV; //정점의 개수 static int nE; //간선의 개수 static boolean[] visit; //방문 배열 static int[][] arr; static int dfs_count(){ int..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int nV; //정점 수 static int nE; //간선 수 static int[][] arr; static boolean[] visit; static int cnt = -1; public static void ..

이 문제를 처음에 접할 때, 문제가 무슨 말인지 이해가 가질 않았다. 그래서 힌트를 보고 문제가 무슨 말을 하고 싶었는지 알 수 있었다. 그러고 나서 점화식을 어떻게 찾을지 N = 1부터 N = 3까지 개수를 다 써보았다. 하지만 처음에는 이차원 배열을 생각하지 못하고, 규칙만 찾았는데 표로 정리해보니 이차원 배열을 사용하면 되겠다는 생각이 들었다. 그래서 기본 점화식인 dp[i][j] = dp[i-1][j] + dp[i][j-1]을 구했었다. 하지만 if( j == 0) 이 부분을 생각하지 못하고 N = 1일 때만 1로 초기화를 시키고 나머지 dp [N][k]에서 k가 0일 때, 1로 어떻게 초기화를 시켜야 하나 엄청 고민을 했다. 그래서 고민을 풀지 못한 채 점화식만 찾고 풀이를 하질 못했다. 그래서..

Top down 방식 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStrea..

이 문제를 처음에 접할 때, 이차원 배열, 일차원 배열을 생각하면서 접근했다. 그런데 n = 1부터 n = 5까지 그림을 그리면서 하는데 규칙성이 보이게 됬다. 피보나치와 비슷한 규칙을 가지게 된다. Top down 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int[] dp; public ..

이 문제는 dp의 가장 기본적인 문제라고 한다. 처음에 이 문제를 보았을 때에는 cnt 변수를 선언해서 연산을 할 때마다 더해준다라는 생각으로 접근을 했다. 하지만 cnt값을 계속 증가해주기 때문에 연산의 최소가 비교가 되질 않았다. 그래서 풀지 못하고 힌트를 보았다. 그래서 보니 cnt을 설정하지 않고 -1 연산할 때, /2 연산할 때, /3 연산할 때 +1을 해주는 것이다. 왜냐하면 연산을 해주었기 때문이다. 그래서 dp[n] 에는 n이 1이 될때까지의 연산 횟수를 저장하는 것이다. 예로 10을 들어보자. 그러면 10을 1 뺄수 있고, 2로 나눌 수도 있다. 그러면 9 와 5가 된다. 여기서 9를 3 으로 나누고 또 3으로 나눌 수 있다. 총 연산 수는 3이다. 5를 -1 하고 4를 2로 2번 나누면..

ArrayList을 쓰면서 이를 이용해서 이차원 배열도 만들 수 있지 않을까 라는 생각이 들었다. 그래서 ArrayList는 제네릭이므로 T를 다시 ArrayList로 할 수 있지 않을까해서 구글링을 기반으로 직접 해보았다. 그래서 시도했더니 성공했다. 그림으로 생각해보면 list 라는 인스턴스 상자 안에 alist, alist2 인스턴스 상자가 들어 있고, alist alist2 각각에는 ArrayList형 배열들이 존재한다고 생각하고, 이 값들을 반환하기 위해서는 처음 list라는 상자에서 alist alist2 상자를 get해야하고, 그 다음에 alist 와 alist2 상자 안을 get해야한다고 순차적으로 생각했다.

StringTokenizer 긴 문자열을 지정된 구분자를 기준으로 문자열을 나열 -> 여러 구분자를 사용할 수 있다. 생성자 StringTokenizer(String str, String delim) : 특정 delim(구분자)로 문자열 분리 StringTokenizer(String str, String delim, boolean return Delims) : str을 delim 기준으로 분리시키는데, 그 delim까지 token으로 포함할지 포함하면 true 입력, false일 때는 포함하지 않는다. delim default값은 공백 문자들(\t \n \r \ t)이다. booelan return delims default값은 false인 것 같다. 입력하지 않으면 자동으로 구분자를 포함시키지 않음. ..

ArrayList 로 생성한 인스턴스는 1차원 배열이라고 생각하게 된다. 그렇다면 ArrayList로 2차원 배열은 어떻게 생성이 되는지 궁금하게 됐다. 그래서 제네릭 T 안에 ArrayList 를 또 집어넣는 것이다. 코드로 보면 어렵지만 머릿 속으로 그림을 생각하면서 이해하면 쉽다. aList라는 ArrayList 형 상자 안에, a1이라는 ArrayList형 상자, a2라는 ArrayList형 상자가 있다고 생각하자. 그리고 a1 상자안에는상자 안에는 1,2가 저장되어있고, a2 상자 안에는 3이 저장되어있다. 그래서 1 2 를 꺼내는 방법은 바깥에서부터 순차적으로 aList.get() 한 뒤, 또 get()메소드를 사용해 출력하면 된다.