결정알고리즘
결정 알고리즘의 핵심은 lp 처음 시작점과 rp 끝지점의 설정
while문안에서 lp와 rp가 만나서 lp와 rp의 이동을 어찌할지에 따라 달렸다.
비교 시, 메서드를 하나 추가해 검증로직을 짜는 식으로 구현한다.
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
public class Main{
private static void solution(int horse, int house, int[] arr) {
Arrays.sort(arr); //정렬하고
int lp = 1; //1
int rp = arr[house-1]; //9
int answer = 0;
while (lp <= rp){
int mid = (lp + rp) / 2; //5 간격 예시
if(testing(arr,mid) >= horse) {
answer = mid;
lp = mid + 1;
}
else
rp = mid - 1;
}
System.out.println(answer);
}
private static int testing(int[] arr, int mid) {
int pointer = arr[0];
int counter = 1;
for (int i = 1; i < arr.length; i++) {
if(pointer + mid <= arr[i]) {
counter++;
pointer = arr[i];
}
}
return counter;
}
}
메모이제이션
5C3 조합문제를 구할때 공식은 4C2 + 4C3이다.
이런식으로 3C1+ 3C2 + 3C2 + 3C3 쭉쭉 재귀를 타면~ 해당값이 구해지는데 문제는 33C19 이런식의 데이터를 구할때 엄청나게 메모리소모와 시간이 소요되므로 메모이제이션 을 이용해서 미리 계산한 값은 계산하지 않는 방식으로 진행하는 테크닉이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Main {
int[][] memo = new int[35][35]; //메모이제이션 35C35 기준으로 구한 값이다.
public static void main(String[] args) {
Main m = new Main();
Scanner sc = new Scanner(System.in);
int i = sc.nextInt();
int j = sc.nextInt();
System.out.println(m.dfs(i, j));
}
private int dfs(int i, int j) {
if(memo[i][j]>0) return memo[i][j]; //해당 구한 값을 수행했느냐?
if(j==0 || i==j) return 1;
else return memo[i][j] = dfs(i-1, j-1) + dfs(i-1, j); //값을 기록하고 리턴하는 방법
}
}
DFS와 BFS로 풀수있는 문제를 가져왔다.
공통적인 특징
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
public class Main{
static int[] px = {-1, -1, 0, 1, 1, 1, 0, -1};
static int[] py = {0, -1, -1, -1, 0, 1, 1, 1};
static int[][] maze;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
maze = new int[num][num];
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
maze[i][j] = sc.nextInt();
}
}
int answer = 0;
for (int i = 0; i < num; i++) {
for (int j = 0; j < num; j++) {
if(maze[i][j] == 1) {
dfs(i, j); // dfs로 풀때
bfs(i,j); // bfs로 풀때
answer++;
}
}
}
System.out.println(Arrays.deepToString(maze));
System.out.println(answer);
static class Point{
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
BFS
최단거리, 최소00 을 구할떄 자주 사용하는 기법
Queue를 쓰는게 포인트
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void bfs(int x, int y) {
Queue<Point> que = new LinkedList<>();
que.add(new Point(x,y));
maze[x][y] = 0;
while (!que.isEmpty()) {
Point tmp = que.poll();
for (int i = 0; i < px.length; i++) {
int nx = tmp.x + px[i];
int ny = tmp.y + py[i];
if(nx >=0 && ny >= 0 && nx< maze.length && ny < maze.length && maze[nx][ny] == 1) {
maze[nx][ny] = 0;
que.add(new Point(nx, ny));
}
}
}
}
DFS
총 거리수, 가는방법수 모든 경우의수를 따질떄 유리
재귀를 쓰는게 포인트
1
2
3
4
5
6
7
8
9
10
public static void dfs(int x, int y) {
maze[x][y] = 0;
for (int i = 0; i < px.length; i++) {
int nx = x + px[i];
int ny = y + py[i];
if(nx >=0 && ny >= 0 && nx< maze.length && ny < maze.length && maze[nx][ny] == 1)
dfs(nx,ny);
}
}