개발자 블로그 다른 곳보다 10원이라도 비싸면 100% 환불

다이나믹 프로그래밍은 큰 문제를 작은 문제로 쪼개어 해결하는 방법을 말합니다. 이때, 작은 문제를 풀어나가는 방법에는 Memoization과 Tabulation 방식이 있습니다. Memoization 방식은 큰 문제를 풀기 위해 필요한 값들을 저장해 두었다가 다시 활용하는 방식으로, Top-down 방식이라고도 부릅니다. Memoization 방식에서는 한 번 계산된 값을 메모이제이션(기록)하여 중복 계산을 방지합니다. 이를 통해 작은 문제를 해결하고, 그 결과를 저장해 놓는 과정에서 dp 배열이 생성됩니다. Tabulation 방식은 작은 문제부터 큰 문제까지 순차적으로 풀어나가는 방식으로, Bottom-up 방식이라고도 부릅니다. Tabulation 방식에서는 작은 문제의 해결에 필요한 값을 이전 계..

난이도: Silver 2 번호: 11060 사용 함수, 자료 구조: Memoization, Tabulation 생성일: February 28, 2023 3:28 PM 알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 다이나믹 프로그래밍 언어: C++ 11060번: 점프 점프 C++ BFS + memoization #include #include #include using namespace std; int N; int arr[1002], memo[1002]; int BFS() { queue Q; memo[0] = 0; Q.push(0); while (!Q.empty()) { int idx = Q.front(); Q.pop(); for (int k = 1; k memo[idx] + 1) { me..

난이도: Silver 2 번호: 21938 생성일: February 27, 2023 3:15 PM 알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 언어: C++ 21938번: 영상처리 C++ BFS 메모리 시간 6924 kb 400 ms #include #include #include using namespace std; int map[1002][1002]; bool visit[1002][1002]; const int dX[] = {0, 0, -1, 1}; const int dY[] = {-1, 1, 0, 0}; int N, M, T, res; void BFS(int i, int j) { queue Q; Q.push({i, j}); visit[i][j] = true; whi..

난이도: Silver 2 번호: 21736 생성일: February 25, 2023 4:28 PM 알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 언어: C++ C++ BFS // BOJ 21736 헌내기는 친구가 필요해 #include #include #include using namespace std; int N, M, res; char map[602][602]; bool visit[602][602]; const int dX[] = {1, -1, 0, 0}; const int dY[] = {0, 0, 1, -1}; void BFS(int i, int j) { queue Q; Q.push({i, j}); visit[i][j] = true; while (!Q.empty())..

난이도: Silver 1 번호: 6588 생성일: February 25, 2023 10:21 AM 알고리즘 분류: 소수 판정, 수학, 에라토스테네스의 체, 정수론 언어: C++ 6588번: 골드바흐의 추측 C++ // BOJ6588 골드바흐의 추측 #include #include #include using namespace std; bool prime[1000001]; void eratosthenes(int n) { memset(prime, true, n); for (int i = 2; i * i > n; if (!n) break; bool flag; for (int i = 3; i < n; i += 2) { if (prime[i] && prime[n - i]) { cout

난이도: Silver 2 번호: 13565 생성일: February 24, 2023 3:37 PM 알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 언어: C++ C++ BFS 메모리 시간 3980 kb 28 ms // BOJ 13565 침투 #include #include using namespace std; int N, M; char map[1002][1002]; bool visited[1002][1002]; const int dX[] = {0, 0, 1, -1}; const int dY[] = {1, -1, 0, 0}; void BFS(int i, int j) { queue Q; Q.push({i, j}); visited[i][j] = true; while (!Q.emp..

난이도: Silver 2 번호: 11123 생성일: February 22, 2023 4:48 PM 알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 언어: C++ 11123번: 양 한마리... 양 두마리... C++ BFS를 이용한 풀이 #include #include using namespace std; int T, H, W, res = 0; char node[102][102]; bool visited[102][102]; const int dX[] = {1, -1, 0, 0}; const int dY[] = {0, 0, -1, 1}; void BFS(int i, int j) { // 좌표가 담긴 pair를 담을 queue 생성 queue Q; Q.push({i, j}); v..

난이도: Silver 2 번호: 11724 알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 언어: C++ 11724번: 연결 요소의 개수 C++ DFS #include #include #include using namespace std; int N, M, cnt = 0; bool visited[1001]; vector V[1001]; queue Q; void DFS(int start) { visited[start] = true; for (int j = 0; j ios::sync_with_stdio(..

섬의 개수 난이도: Silver 2 번호: 4963 사용 함수, 자료 구조: memset 알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 언어: C++ 4963번: 섬의 개수 C++ 상하좌우와 대각선 방향까지 8방 탐색을 할 수 있도록 방향배열(dX, dY)을 설정해준다. const int dX[] = {1, -1, 0, 0, 1, 1, -1, -1}; const int dY[] = {0, 0, -1, 1, 1, -1, 1, -1}; 8방 탐색중에 Out of Bound가 발생할수 있는데 해결에는 2가지 방법이 있다. if 조건 추가 if (i = M || j >= N) continue; 그래프 배열 상하좌우에 1칸씩 여유공간을 만들어준다...

유기농 배추 난이도: Silver 2 번호: 1012 사용 함수, 자료 구조: memset 알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색 언어: C++ 1012번: 유기농 배추 C++ BFS #include #include using namespace std; const int dX[] = {1, -1, 0, 0}; const int dY[] = {0, 0, -1, 1}; int N, M, K, cnt; bool node[51][51]; bool visited[51][51]; void reset() { cnt = 0; for (int i = 0; i < 51; i++) for (int j = 0; j < 51; j++) { node[i][j] = false; visited..