Hello backEnd

[백준 18428번] 감시 피하기 - java

문제 설명1. N X N 복도가 있다.2. T 선생 S 학생 X 빈공간3. 선생은 상하좌우를 볼 수 있고 장애물이 있으면 그 뒤는 못본다.4. 장애물을 정확히 3개 설치해서 모든 학생이 안보이면 된다.풀이 과정1. BF + 백트래킹2. 모든 위치에 장애물을 둬 가면서 학생이 확인되는지를 보면 된다.3. 미리 선생의 위치를 알아두고, 그곳에서 볼 때 장애물인지 파악하기4. 장애물의 배치는 모든 X에 두고 보면 된다.코드import java.util.*;public class Main{ private static char map[][]; private static boolean checker[][]; private static int N; private static boolean ans..

[백준 16987번] 여행 가자 - java

문제 설명1. 테스트용 계란을 왼쪽부터 집는다.2. 다른 계란하고 부딪혀본다. (내구도는 무게에 의해 깎이고 내구도가 0보다 작거나 같으면 깨짐)3. 모든 경우에서 최대한 많은 계란을 깬다면 그 숫자는?풀이 과정1. BF - DFS + 백트래킹으로 풀면 된다.2. 보면 결국 어떤 계란을 집었을 때에 하나씩 테스트하고, 그렇게 마지막까지 도달하면 하나의 경우를 테스트하는 것이다(BF - DFS)3. 그리고 그 테스트가 끝나면 아무일 없던 것처럼 계란을 돌려놓는다(백트래킹)4. 재귀함수를 통해서 구하고 ans를 구해주면 된다.코드import java.util.*;public class Main{ private static List eggList = new ArrayList(); private st..

문제 설명1. 첫번째 줄에 도시의 갯수가 주어진다.2. 그 다음은 여행 계획에 속한 도시의 수가 주어진다.3. 다음부터 그 줄의 도시가 어디랑 연결되었는지 주어진다.4. 마지막에는 여행을 가는 계획이 주어진다.풀이 과정1. 유니온 파인드 문제이다. 모든 도시가 연결되어 있는지를 파악한다.2. 주어지는 값들을 유니온해서(parent에 연결) 같은 루트에 있다고 맞춰준다.3. 이후로는 마지막에 주어진 계획 도시들이 다 같은 루트에 있는지만 파악하면 된다. 코드import java.util.*;public class Main{ private static int[] parent; private static int find(int x) { if (x == parent[x]) { return ..

문제 설명1. 첫째 줄에 회의의 갯수 N이 주어진다.2. 그 다음주터 N개의 회의 시작시간 - 끝나는 시간이 주어진다.3. 그 시간을 통해 모든 회의가 멈추지 않게 작동하는 회의실의 최소 갯수를 구하면 된다.풀이 과정 1. (내가 이렇게 풀어서 시간초과가 발생했었는데) 어떤 회의가 언제부터 언제인지를 알 필요는 없다. 2. 그냥 시작시간부터 회의실 하나의 자리를 차지하고 있고, 뭐가 됐든 나가는 시간에는 나간다는 것이다. 3. 그러니까 어떤 회의가 언제인지 알 필요는 없고, 언제 입장인지 언제 퇴장인지를 알면 된다. 4. 그러고 시간 순서대로 나열하면 회의실에 들어가 있는 회의의 갯수를 알 수 있다.  코드import java.util.*;public class Main { public static v..

문제 설명1. 첫째 줄에 맵의 크기랑 이동거리가 주어진다.2. .은 갈수 있는 곳, T는 장애물로 주어진다.3. 오른쪽 아래부터 시작해서 오른쪽 위까지 이동거리로 이동할 수 있는 경우의 수를 구한다.4. 한번 지나간 길로는 못간다.풀이 과정 1. DFS 문제이다. 2. 한번 지나갔거나, 장애물이 있는 곳은 true, 나머지는 false로 구한다. 3. 현재 위치에서 DFS할 때에 이동할 곳을 이동처리하고 그 DFS끝나면 다시 이동 가능하게 하면 된다. (가게 되면 방문한거니까) 코드/****************************************************************************** Online Java Compile..

문제 설명1. 0부터 N까지의 정수 K 개를 더해서 합이 N이 되어야 한다.2. 즉 N번 계산해서 K가 나오도록 풀이 과정 1. 이거 DP이다. 2. DP는 일단 무식하게 풀면서 점화식을 찾아보는 것이 중요하다. 3. 그래서 풀어보면요런 식으로 나온다.한번 계산할 때에는 (0) | (1) | (2) | (3) | (4)두번 계산할 때에는 (00) | (10) (01) | (03) (12) (21) (30) | (04)(13)(22)(31)(40)이런 식으로 간다. 그래서 저거 잘 들여다 보면 점화식이 대충 보인다.val[i][j] = val[i-1][[j] + val[i][j-1]이런 식으로 그래서 일단 전체를 1로 초기화하고 더해가면 된다. 코드import java.util.*;public class ..

문제 설명1. 사람 수, 파티의 수가 첫 줄에 주어지고2. 둘쨰 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다.3. 그 다음부터는 파티의 갯수만큼 사람들이랑 그 사람의 번호가 주어진다.4. 진실을 아는 사람이 속한 파티나, 그 사람이랑 같은 파티에 한번이라도 참가한 사람이 있거나, 같은 파티에 참석한 점이 있는 사람이 한명이라도 있는 파티에서는 거짓말을 못한다.5. 거짓말 할 수 있는 파티 수를 구하면 된다. 풀이 과정 1. 유니온 파운드 문제이다. 2. 모든 사람의 관계를 조사해서, 진실을 아는 사람이 같은 유니온에 들어가있는지 파악하면 된다. 3. 사실 그렇게 어려운 문제는 아니겠지만(아니겠지?) 유니온 파인드에 관한 지식은 가지고 있어야 풀 수 있다. 한번 브루트포스로 풀어보려 했더니 당..

문제 설명1. R*C 격자가 주어지고, '.'은 갈 수 있는 길 'X' 는 갈 수 없는길(건물) 이다.2. 왼쪽 끝에서부터 시작해서 오른쪽 끝으로 연결이 가능하면 파이프가 이어지는것.3. 하나의 시작점에서는 하나만 도달한다.4. 이미 연결되면 그 다음에는 연결되지 않는다.5. 그래서 도달한게 몇개인지 맞추면 된다. 풀이 과정 1. DFS, 그리디이다. 2. 백트래킹도 가능할 것 같기는 한데... 나는 DFS로 풀었고 그 이유는 3. 위에서부터 아래로 가면서, 그리고 위로 가면서 확인하면 결국 갈 수 있는 길 자체가 정해진다.(그리디의 일종?) 4. 즉, 위에서부터 확인하고 올라가기 - 직선 - 내려가기 할 때에 위에서 이미 갔으면 그거 자체가 하나의 루트가 된다. 즉 아래에서 이거때문에 못간다고 해도 달..

문제 설명1. 맨 윗줄은 테스트 케이스 갯수2. 2줄씩 받고 -> 처음은 [집갯수, 훔칠 집 수, 훔칠 금액 최대값+1] / 두번째는 [집들의 가진 돈] 이 주어진다.3. 도둑이 훔치려고 할 때에 인접한 집을 찾아가면서 훔치고 일정 금액 이상 훔치거나 일정 집 수 이상 훔치면 잡혀감4. 그 안에서 훔칠 경우의 수를 구하면 된다. 풀이 과정 1. 간단한 슬라이딩 윈도우 문제이다. 2. 집을 하나씩 찾으면서 보면 된다. 3. 그리고 보면 그냥 배열이랑 좀 다른거는 처음 맨 뒤쪽 집들은 최초 털어간 집에 대한 확인도 된다는거 4. 내가 풀어낸 방식은 그래서 [123][234][345][451][512] 이렇게이다. 5. 근데 여기서 중요한건 M == N 이면, 4번 방식에서 [123][231][312] 가 된..

문제 설명1. 해석하고 싶은 문자 W가 주어진다.2. 그게 중간에 들어가는 S가 주어진다..3. 이거 뭔소린가.. 엄청 헤맸는데, 말하자면 둘째줄 W의 각각 char 들이 순서와 상관없이 S에 어떻게 있는지를 물어보는 문제이다.즉, 주어진 보기를 보았을 때에첫 번째로 "Acad" (3번째 문자부터), 두 번째로 "cAda" (4번째 문자부터)에서 "cAda"와 동일한 문자 빈도를 가진 부분 문자열을 찾는 문제라는 것이다.4. 앞의 숫자 두개는 별의미 없다. 풀이 과정 1. 딱 봐도 S의 길이가 매우 길다. 2. 브루트포스로는 못풀것 같은데, 슬라이딩 윈도우를 통해 구현한다. 3. W의 문자들이 나타나는 갯수를 구해놓고, 그 크기만큼 S에서 하나씩 찾는다. 하나씩 더하고 빼면서 비교해주면 된다. 4.- [..