하수하따 록기장

📍알고리즘 분류: DP 동적 프로그래밍큰 문제를 작은 문제로 나눌 수 있으며 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 경우 DP를 사용한다.📍문제 풀이:처음에는 조합(Combination)을 이용한 수식으로 문제에 접근했다. 문제에서 높이는 2로 고정되어 있으므로 2xn 타일을 쪼개보면 타일을 구성할 수 있는 경우는 '2x1' 혹은 '1x2 두개를 위아래로 붙인 2x2' 뿐이다. 그래서 2x1의 모양을 A, 2x2의 모양을 B라고 하자.A는 가로를 1만큼 차지하고 B는 한번에 2만큼 차지한다. 따라서 2xn의 모양에서 n = (1 x A의개수) + (2 x B의개수)라는 수식을 세울 수 있다. A와 B의 범위는 0과 자연수이다. 따라서 A와 B의 순서쌍 조합을 구하면 이 과정에..

📍알고리즘 분류: DFS, BFSDFS란 Depth First Search, 깊이 우선 탐색. 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 재귀호출이나 스택 배열로 구현할 수 있다.📍문제풀이: 재귀호출 방식의 DFS로 문제를 풀었다. dfs가 처음 호출되면 인접한 집들을 다 탐색하여 한 단지를 구성하는 집의 개수를 모두 센다.📍코드#include #include #include #include using namespace std;#define MAX_N 26int map[MAX_N][MAX_N];bool visited[MAX_N][MAX_N];int dx[4] = {-1,1,0,0};int dy[4] = {0,0..