HyeLog

⭕처음 제출한 코드⭕ '에라토스테네스의 체' 개념이 기억나서 풀었다. 맞았습니다!! 이긴 하지만 시간복잡도를 더 개선할 수 있을 것 같아서 구글링해봄. #include #define MAX 1001 using namespace std; bool not_prime[MAX]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, cnt = 0, x; cin >> n; not_prime[1] = true; for (int i = 2; i < MAX; i++) { if (not_prime[i]) continue; for (int j = 2 * i; j < MAX; j += i) { not_prime[j] = true; } } whi..

🙋‍♀️ 문제 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 🧩 알고리즘 다이나믹 프로그래밍 (DP) 💡 아이디어 D[i] = i번 칸에 도착할 수 있는 최소 점프 횟수 j번째 칸에서 i번째 칸으로 갈 때(j < i), i - j ≤ Aj 임 D[i] = min(D[j]) + 1 👩‍💻 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0..

🙋‍♀️ 문제 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 🧩 알고리즘 다이나믹 프로그래밍 (DP) 💡 아이디어 D[i][j] = (1, 1)에서 시작해서 (i, j)에 도착했을 때 사탕 개수의 최댓값. (i, j)에 도착했을 때 가능한 경우의 수 (D[i][j]를 만들 수 있는 방법 3가지): case 1) (1, 1) → (i, j - 1) → (i, j) 이때, D[i][j] = D[i][j - 1] + A[i][j] c..

🙋‍♀️ 문제 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 🧩 알고리즘 BFS 알고리즘 💡 아이디어 바이러스를 놓을 칸을 재귀함수로 고른 후 BFS를 수행한다. 연구소2 문제와 거의 비슷하지만, 비활성화 바이러스가 있으므로 마지막에 답을 구할 때 이 경우는 제외하고 빈 칸에 바이러스를 퍼뜨린 최소 시간만 구해야 한다. 👩‍💻 코드 #include #include #include #include #include using namespace std; i..

🙋‍♀️ 문제 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 🧩 알고리즘 BFS 알고리즘 💡 아이디어 바이러스를 놓을 칸을 재귀함수로 고른 후 BFS를 수행한다. 👩‍💻 코드 #include #include #include #include #include using namespace std; int n, m; int a[50][50]; int dist[50][50]; int dx[4] = { 0,-1,0,1 }; int dy[4] = { -1,0,1,..

🙋‍♀️ 문제 https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 🧩 알고리즘 BFS 알고리즘 💡 아이디어 입력으로 주어진 각 칸의 숫자를 1= m) continue; // 범위 검사 if (area[nx][ny] != 0) continue; // 방문 여부 검사 if (a[x][y] & (1 > m >> n; for (int i = 0; i > a[i][j]..

🙋‍♀️ 문제 https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 🧩 알고리즘 각 칸의 안전거리 = 아기 상어까지의 최소 거리 → BFS 알고리즘 시간복잡도: O((NM)^2) (BFS = O(NM)) 2 ≤ N, M ≤ 50 → BFS 가능 💡 아이디어 모든 빈 칸에 대해 BFS로 안전거리를 계산하면서 최댓값을 갱신 👩‍💻 코드 #include #include #include #include #include using..

🙋‍♀️ 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 🧩 알고리즘 시작점으로부터 모든 정점을 방문하며 간선의 가중치가 1이고 눌러야 하는 버튼의 수의 최솟값을 구하는 문제이므로 BFS 알고리즘 사용 💡 아이디어 기본적인 BFS 문제였다. 👩‍💻 코드 #include #include using namespace std; bool visited[1000001]; int dist[1000001]; int main() { ios_base::sync_wit..