브루트포스4 [백준 2251] 물통 / 자바 / 브루트포스(dfs or bfs) ** #문제 레벨: G5알고리즘: dfs or bfs풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2251#문제 풀이 물을 옮기는 방법은 6가지이다.{ (A->B) ( A -> C) ( B -> A) (B -> C) (C -> A) (C -> B) } 우린 물을 옮기는 6가지 방법을 계속 꼬리를 물어 탐색하면 되는 것이다. 구현은 어떻게 할 것인가? 이중 for문으로 구현하던가 4방향으로 움직이는 dx = {1,0,0,-1} dy = {0,1,-1,0}처럼 from[], to[]로 구현하면된다. 그러면 언제 탐색을 멈춰야 하나? 세 물통의 담겨있는 용량을 방문한적 있을 때 멈춰야한다. 물통의 리터제한은 200리터이다. 리터제.. 2024. 7. 23. [백준 2098] 외판원 순회 / 자바 / dp + 브루트 포스 ** #문제 레벨: G1알고리즘: dp + 브루트 포스 + 비트 마스킹풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2098#문제 풀이 TSP(Traveling Salesman Problem)시간 복잡도 O(n^2 * 2^n)모든 경우의 수를 살펴봐야 하는 문제임은 확실하다. 그러나 최악의 상황을 가장해보면 16!이다. 20조 9,227억 8,988만 8천이라는 것이다. ( 11! = 39,916,800 (약 3.99 × 10^7) 안에 들어야 시간복잡도에 통과할 수 있다.) 브루트 포스는 확실한데 시간이 걸린다면 dp 도입을 의심하면 된다. dp + dfs 는 postorder로 코드 구현한다. dp를 재귀함수로 구현하려면 값이 저장된.. 2024. 7. 12. [백준 15683] 감시 / 자바 / 브루트 포스(그래프 순회) 문제 레벨: G3알고리즘: 브루트 포스(그래프 순회)풀이시간: 1:30힌트 참조 유무: 무https://www.acmicpc.net/problem/156831 번째 시도: 실패 [알고리즘 선택 과정]각 cctv마다 방향 설정이 중요합니다그렇다면 각 cctv의 방향을 무슨 기준으로 놓아야 할까요주장: 각 CCTV마다 칸을 많이 차지하는 방향으로 반론: A가 칸이 많이 차지하는 방향, B가 칸이 많이 차지하는 방향으로 설정했는데 A,B가 겹치는 것이 많은 상황을 가장해보자.(주장 답안)0 0 #0 0 2(A)0 0 #0 0 2(B)0 0 #(정답 답안)0 0 0# # 2(A)0 0 0# # 2(B)0 0 0 그래서 이 주장은 옳지 않습니다. 패스그렇다면 완전탐색으로 각 CCTV의 모든.. 2024. 5. 30. [백준] 2048(Easy) / 자바(feat 브루트 포스, 백트래킹, DFS 차이점) 문제 레벨: G2알고리즘: 브루트 포스풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/121001 번째 시도 [사고 과정]이 게임의 규칙을 못 찾겠다.최대 N= 20 최대 탐색횟수 5번 4방향으로, 5*4*20*20 =8,000이므로 완전탐색이 가능할 것 같다.5번의 완전탐색으로 구현 자! 그렇다면 어느 것을 기준으로 다음 탐색지를 정해야 할까?각각의 숫자들을 타겟 or 방향각각의 숫자들을 기준에 맞추어 어느 숫자를 크게 만들까 생각한다면 다른 숫자들도 영향을 받기 때문에 머리가 너무 아프다당연히 4가지로만 나누어진 방향에 초점을 맞추는 게 맞다!(이번 기회를 통해 어는 것의 초점을 맞추어 다음 탐색지를 정할지 중요할 것을 알았다) [구현.. 2024. 5. 23. 이전 1 다음
