브루트포스4 [백준 2098] 외판원 순회 / 자바 / TSP(dp + 비트마스킹 + dfs) #문제레벨: G1알고리즘: dp + 브루트 포스 + 비트 마스킹풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2098#문제 풀이TSP(Traveling Salesman Problem)시간 복잡도 O(n^2 * 2^n)이 문제는 전형적인 TSP 문제입니다. 한 노드에서 출발하여 모든 노드를 순회하고 다시 시작점으로 돌아오는데 최소값을 구하는 문제가 TSP입니다.TSP 문제를 가장 무식하게 푸는 방법은 모든 경우의 수를 다 탐색해보는 것입니다. 모든 경우의 수를 탐색해보는 것은 N!인데, 알고리즘에서 가장 나쁜 경우의 수가 N!입니다.저희는 DP를 사용해야 합니다. 큰 문제를 작은 문제로 쪼갠다. N = 3 일 때를 가정하면 아래와 같은 경우의 수가 있습니다.1.. 2025. 1. 23. [백준 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. [백준 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 다음
