DFS40 [백준 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. [백준 2186] 문자판 / 자바 / dp + dfs #문제 레벨: G3알고리즘: dp + dfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/2186#문제 풀이 처음 문제를 봤을 때 별 생각없이 아래와 같이 dfs 코드를 짰다. 코드는 문제에 맞게 구현됐다. 단지, 시간 초과가 날 뿐이다...잠시 이 dfs 코드를 흝어봐주고 내려와주라.dfs코드import java.io.*;import java.util.*;public class Main { static int N, M, K; static char[][] board; static String word; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, .. 2025. 1. 22. [9663] N-Queen , 자바 , dfs(백트래킹) 1. 문제레벨: G4알고리즘: dfs(백트래킹)풀이시간: 30분힌트 참조 유무: 유https://www.acmicpc.net/problem/96632. 문제 풀이실패 시도:서로 공격하지 않는 경우의 수로 구하려고 하였으나 N^2 C N 의 시간 복잡도가 나왔습니다. 이는 한 눈에 봐도 큰 경우의 수 입니다. 아무리 백트래킹을 한다그래도 N = 15, 시간제한 = 10초 안에 불가능할 거라 판단하였습니다.전체 경우의 수 - 서로 공격하는 경우 로 구하려고 하였으나 서로 공격하는 경우에서 2 ~ N이 서로 공격하는 경우를 구할 때 중복이 발생함으로 중복을 해결하는 과정이 너무 복잡해보였습니다. 잘못된 방법인 냄새실패 원인: N^2 C N에 대한 오해N^2 C N은 "N^2개의 칸에서 N개의 퀸을 선택하여 .. 2025. 1. 19. [백준 16234] 인구 이동 / 자바 / bfs #문제레벨: G4알고리즘: bfs풀이시간: 50분힌트 참조 유무:https://www.acmicpc.net/problem/16234#문제 풀이특정 국가(A)를 기준점으로 삼고 그 국가와 연할될 수 있는 국가(B)를 찾고 B와 연합될 수 있는 국가를 찾고(C) 반복한다. 이 형식 어디서 보지 않았는가? 4방향+bfs(or dfs)이다. 그런데 bfs 한 번으로 모든 국가를 다 탐색할 수는 없다. 그래서 이중 for문으로 모든 국가를 돌대 visited =false(방문하지 않은) 곳만 bfs(or dfs)를 돌린다. 코드는 둘 다 첨부하겠다.코드를 보면 bfs(or dfs)를 마치고나서 인구이동을 시킨다. bfs로 인접국가를 순회하는 김에 인구이동까지 하면 안되나? 라는 충동이 들었지만, 구현이 복잡하고 .. 2025. 1. 17. [백준 2239] 스도쿠 / 자바 / dfs(백트래킹) #문제 레벨: G4 알고리즘: dfs(백트래킹)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2239#문제 풀이 해당 자리에 숫자를 놓으려면 해당 열, 해당 행, 해당 박스 안에 같은 숫자가 있으면 안된다. 이것들을 검사하는 코드를 구현하고 백트래킹을 통해서 숫자를 채워넣으면 된다.dfs 코드는 아래와 같이 방문한다. -------------------------> 1 번째 행-------------------------> 2 번째 행 -------------------------> 3 번째 행 -------------------------> 4 번째 행 -------------------.. 2024. 9. 1. [백준 1240] 노드사이의 거리 / 자바 / dfs (dfs구현연습) #문제 레벨: G5알고리즘: dfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/1240#문제 풀이 dfs + void static void dfs(int current, int end, int distance) { if (current == end) { result = distance; return; } visited[current] = true; for (int[] next : tree[current]) { if (!visited[next[0]]) { dfs(next[0], end, dista.. 2024. 8. 16. [백준 11375] 열혈강호 / 자바 / 이분 매칭 #문제 레벨: P4알고리즘: 이분 매칭 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/11375#문제 풀이 이 문제는 이분 매칭 문제이다. 예시를 통해 문제를 설명하겠다. 헷갈릴 수 있으니 일을 1 ~5로 표현하고 직원을 A,B,C,D,E로 표현하겠다.예제 1을 보면 1. A는 1번 일과 2 번일을 할 수 있다. 일단 1번 일을 맡겠다고 치자. A B C D E1 2. B는 1번 일만 할 수 있다. 그래서 1 번 일을 맡고 있는 A가 다른 일을 맡을 수 있는지 확인한다. 확인하니 1 번 말고 2 번 일을 맡을 수 있다. B는 1 번일, A는 2 번일을 맡도록 하자. A B C D E2 1 3. C는 2, 3 번일을 할 수 있다. .. 2024. 8. 15. [백준 18251] 내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy) / 자바 / dfs + 카데인 알고리즘 #문제 레벨: P4알고리즘: dfs + 카데인 알고리즘풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/18251#문제 풀이 문제 풀기에 앞서 카데인 알고리즘을 알고가야 한다. 카데인 알고리즘이란 최대 부분 합 수열을 구할 때 사용한다. 평소 이 알고리즘 이름은 안적도 없지만, 이러한 방식으로 문제를 푼 경우가 있을 것이다. 이거에 이름을 붙여 더 확실히 기억해보자.예시 배열: [-2, 1, -3, 4, -1, 2, 1, -5, 4]localMaxValue: 현재 위치까지의 연속된 부분 배열의 최대 합 globalMaxValue: 지금까지 발견된 전체 최대 부분 배열의 합초기 상태: [-2, 1, -3, 4, -1, 2,.. 2024. 8. 12. [백준 11400] 단절선 / 자바 / dfs ** #문제 레벨: P4알고리즘: dfs풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/11400#문제 풀이 가장 쉬운 방법은 모든 단절선을 끊어보고 dfs 여러번을 통해 트리의 개수가 2개이상인지 세어보는 것이다. 그러나 입력제한을 보면 시간초과가 날 것을 직감할 수 있다.문제의 해결법은 노드를 처음 발견했을 때의 순서와 만남의 가중치를 이용해 푸는 것이다. 처음 방문한 노드라면 처음 발견했을 때의 변수와 만남의 가중치에 발견한 순서를 부여해준다. 만약 처음 방문한 게 아니라면 1를 시작으로 탐색했을 때 1 -> 4 -> 5 -> 6(1에 의해) -> 7 -> 2 -> 3이렇게 정점을 탐색하는 것이다. 근데 우리가 중요한 건 간선을 .. 2024. 8. 12. 이전 1 2 3 4 5 다음
