5주차 내용정리 📌 백트래킹 백트래킹(Backtracking) 이란 ? 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다. 스무고개를 생각하면 쉽게 이해할 수 있음. ex ) 미로탐색 미로 탐색 문제같은 경우, 출발지부터 상,하,좌,우로 경우의 수를 dfs로 뻗어나가게 되는데, 더이상 진행할 수 없는 경우 다른 경우의 수로 해를 찾게된다. 📌 조합 nCr = n! / (n-r)! * r! 이 공식을 쓰지 않고 다음 공식을 쓴다. nCr = n-1Cr-1 + n-1Cr 위의 공식으로 예를들어 5명중에서 3명을 뽑는 경우의 수를 식으로 풀면 다음과 같다. 5C3 = 4C2 + 4C3 말로 풀어서 이야기 하면 5명중에서 3명을 뽑..

문제 링크 연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net ❗ 풀이 방법 문제가 복잡한 만큼 로직을 나눠서 생각한 뒤, 구현해주는 것이 좋다. 문제를 읽어보면 다음의 세가지 로직이 필요한 것을 깨달을 수 있다. 벽을 세워보는 로직 바이러스를 퍼트리는 로직 안전영역의 갯수를 세는 로직 이렇게 정리가 되었다면, 다음은 위 세가지 로직을 어떻게 구현할 지 생각해보아야 한다. 벽을 세워보는 로직 모든 조합수를 따져보아야 하니 백트래킹으로 벽을 세워보고 허물어보고 하는식으로 하는것이 적절하지 않을까? 따라서 벽을 3개까지 세..

문제 링크 DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 코드 import java.util.*; public class Main { static int n; static int m; static int[][] graph; static boolean[] visited; /** * 입,출력 */ public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nex..

4주차 내용정리 📌 DFS (Depth-First Search) DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문처리. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄. 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복 다음의 그래프를 DFS로 탐색해본다고 가정하자.(방문 순서는 1번부터 시작하여 인접한 노드중 번호가 낮은 노드를 방문) 탐색 순서 : 1→ 2 → 7 → 6 → 8 → 3 → 4 → 5 위의 과정을 ..