Dev.baelanche

그래프에 대해 공부해 보았다면 DFS 로 풀 수 있는 문제란걸 유추할 수 있다. 연결된 정보를 가지고 문제를 푼다 -> 그래프 문제 만든 그래프로 최단거리, 최소거리를 구해야 한다 -> BFS 그렇지 않다 -> DFS 네트워크 연결이 한방향으로만 되지는 않을것이고 별도의 언급도 없으니 양방향 그래프라고 볼 수 있다. 2차원 배열로 그래프를 만들어 노드마다 연결된 노드 번호를 매겨주고 카운트를 세어주면 된다. 노드 탐색을 할때 연결된 노드를 전부 탐색한 뒤 재귀호출 하는 방식으로 구성하고 싶어서 큐를 이용했다. public class Main { static int n; static int a[][]; static boolean visited[]; static Queue q = new LinkedList(..

각 다리의 수에 따른 경우의 수를 이용하여 풀어야 한다. n / m 1 2 3 4 5 6 1 1 2 3 4 5 6 2 X 1 3 6 10 15 3 X X 1 4 10 20 n이 1일땐 m의 수만큼 경우의 수가 증가한다. n이 2일땐 m이 증가함에 따라 dp[n][m] = dp[n][m-1] + dp[n-1][m-1] 의 형식으로 증가하는걸 볼 수 있다. n이 3일때도 마찬가지이다. n이 1일때의 초기값과 n == m 일때의 초기값을 배열에 대입해주고 위 점화식을 이용하여 풀면된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long dp[][] = new long[30][3..

n 이 1일때 9 (1, 2, 3, 4, ..., 9) n 이 2일때 17 이다. 십의 자리수가 5일때 54 혹은 56 이어야 하므로 자리수 n 이 i, 일의 자리수가 j 일때 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]; 위와 같은 점화식을 얻을 수 있다. n이 2일때의 계단수가 17인 이유는 01 이 빠졌기 때문이다. 일의 자리수가 0일때는 제외해야 하므로 점화식에 추가해준다. if(j == 0) dp[i][j] = dp[i-1][j+1]; else dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]; 마찬가지로 9일때도 90 같은 수는 만들 수 없으니 예외처리 한다. if(j == 0) dp[i][j] = dp[i-1][j+1]; else if(j == 9..

수열의 크기와 같은 크기의 dp 배열을 만들어 각 인덱스별로 최대값을 저장한다. 수열의 값 중 적어도 한 개를 선택해야 하고 연속적으로 사용해야 하므로, 이전 dp의 최대값 + 현재 배열의 값 / 현재 배열의 값을 비교하여 큰 것을 사용하면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a[] = new int[n]; int dp[] = new int[n]; for(int i=0; i

배열 한개에 그리는 방식으로 풀었다. 공백 한칸을 비우는 부분만 신경을 잘 써주면 된다. public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int s = sc.nextInt(); String n = sc.next(); int height = 2*s + 3; int width = s + 2; int len = n.length(); char a[][] = new char[height][len * width + len-1]; for(int i=0; i

어느 부분이 반복되는지 한 3분정도 보다가 찾아냈다. *** * * *** 모양을 재귀호출하면서 채워넣어주면 된다. 예제를 생각해보면, 1. 27*27 배열을 9*9 씩 9개로 분할한다. 2. 9개 배열 중 가운데 배열만 공백으로 채우고 나머지는 *로 채운다. 3. 9개 배열을 3*3 씩 9개로 분할한다. 4. 2번과 같이 채운다. 5. 3*3 의 배열을 채우면 정지한다. 위 순서대로 3^n * 3^n 의 배열에서 3등분 하는 방법으로 접근하면 된다. public class Main { static char a[][]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); a = ..

2^n * 2^n 의 배열에서 좌상, 우상, 좌하, 우하 순으로 분할하여 접근한다. 재귀를 이용하여 접근한 부분배열의 크기가 2*2 일때까지 접근하여 카운트를 세고 (r, c) 일때의 카운트를 출력해주면 된다. public class Main { static int idx = 0; static int r; static int c; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int pow = (int)Math.pow(2, n); r = sc.nextInt(); c = sc.nextInt(); recursive(0, 0, pow); } public static void re..

회의실배정 문제와 유사한데 조금 더 꼬아낸 문제다. 모든 수업이 가능해야 하므로 배열 정렬은 시작 시간에 대해 오름차순으로 정렬한다. 진행중이던 강의가 끝나면 그 강의실을 재사용할 수 있으므로 강의 정보를 담을 자료구조가 필요하다. 처음에는 큐를 이용하여 풀었는데 큐에서도 끝나는 시간이 빠른것을 우선으로 비교해야 하므로 우선순위 큐로 구현했다. 진행은 다음과 같다. 1. 강의 정보를 시작 시간에 따라 오름차순으로 정렬한다. 2. 강의 종료 시간을 우선순위 큐에 담는다. 3. 큐의 front 와 현재 강의 정보의 시작시간과 비교하여 시작시간이 크거나 같다면 큐를 pop 한다. (강의실이 비었다) 4. 마지막에 큐의 개수를 센다. 강의 정보를 구조체나 클래스로 구현하여도 되지만 회의실배정 때 소스를 끌어다가..