반응형
1번 문제 변형
문제 1. 다양한 퍼짐 속도를 가진 풀
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int n, k;
vector<vector<int>> grid, speed;
int bfs(int startX, int startY) {
vector<vector<int>> visited(n, vector<int>(n, 0));
queue<pair<int, int>> q;
vector<vector<int>> year(n, vector<int>(n, 0));
int count = 1;
q.push({startX, startY});
visited[startX][startY] = 1;
year[startX][startY] = 0;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny] && grid[nx][ny] == 0) {
year[nx][ny] = year[x][y] + 1;
if (year[nx][ny] > k) continue;
q.push({nx, ny});
visited[nx][ny] = 1;
count++;
}
}
}
return count;
}
int main() {
ifstream input("input1.txt");
input >> n;
grid.resize(n, vector<int>(n));
speed.resize(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
input >> grid[i][j];
}
}
input >> k;
int maxCount = 0;
pair<int, int> bestPosition = {-1, -1};
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0) {
int currentCount = bfs(i, j);
if (currentCount > maxCount) {
maxCount = currentCount;
bestPosition = {i, j};
}
}
}
}
cout << bestPosition.first + 1 << " " << bestPosition.second + 1 << endl;
cout << maxCount << endl;
return 0;
}
문제 2. 암석을 제외한 가장 큰 영역 구하기
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int n;
vector<vector<int>> grid;
void bfs(int startX, int startY, vector<vector<bool>>& visited, int& area) {
queue<pair<int, int>> q;
q.push({startX, startY});
visited[startX][startY] = true;
area++;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny] && grid[nx][ny] == 0) {
q.push({nx, ny});
visited[nx][ny] = true;
area++;
}
}
}
}
int main() {
ifstream input("input1.txt");
input >> n;
grid.resize(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
input >> grid[i][j];
}
}
vector<vector<bool>> visited(n, vector<bool>(n, false));
int maxArea = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (!visited[i][j] && grid[i][j] == 0) {
int area = 0;
bfs(i, j, visited, area);
maxArea = max(maxArea, area);
}
}
}
cout << "Maximum area of grass-growing space: " << maxArea << endl;
return 0;
}
문제 3. 두 개의 시작점에서 동시에 풀 자라기
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int n, k;
vector<vector<int>> grid;
int bfs(int startX1, int startY1, int startX2, int startY2) {
vector<vector<int>> visited(n, vector<int>(n, 0));
queue<pair<int, int>> q1, q2;
q1.push({startX1, startY1});
q2.push({startX2, startY2});
visited[startX1][startY1] = 1;
visited[startX2][startY2] = 2;
int years = 0;
while (!q1.empty() || !q2.empty()) {
int qSize = q1.size() + q2.size();
while (qSize--) {
if (!q1.empty()) {
int x = q1.front().first;
int y = q1.front().second;
q1.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny] && grid[nx][ny] == 0) {
q1.push({nx, ny});
visited[nx][ny] = 1;
}
}
}
if (!q2.empty()) {
int x = q2.front().first;
int y = q2.front().second;
q2.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny] && grid[nx][ny] == 0) {
q2.push({nx, ny});
visited[nx][ny] = 2;
}
}
}
}
years++;
}
return years;
}
int main() {
ifstream input("input1.txt");
input >> n;
grid.resize(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
input >> grid[i][j];
}
}
int startX1, startY1, startX2, startY2;
input >> startX1 >> startY1 >> startX2 >> startY2;
int years = bfs(startX1 - 1, startY1 - 1, startX2 - 1, startY2 - 1);
cout << "Years for grass to meet: " << years << endl;
return 0;
}
문제 4. 회전 가능한 그리드에서 풀 자라기
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int n, k;
vector<vector<int>> grid;
void rotateGrid() {
vector<vector<int>> newGrid(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
newGrid[j][n - 1 - i] = grid[i][j];
}
}
grid = newGrid;
}
int bfs(int startX, int startY) {
vector<vector<int>> visited(n, vector<int>(n, 0));
queue<pair<int, int>> q;
visited[startX][startY] = 1;
q.push({startX, startY});
int count = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny] && grid[nx][ny] == 0) {
visited[nx][ny] = 1;
q.push({nx, ny});
count++;
}
}
}
return count;
}
int main() {
ifstream input("input1.txt");
input >> n;
grid.resize(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
input >> grid[i][j];
}
}
int maxCount = 0;
for (int r = 0; r < 4; ++r) {
int currentCount = bfs(0, 0);
maxCount = max(maxCount, currentCount);
rotateGrid();
}
cout << "Maximum grass-growing cells after rotation: " << maxCount << endl;
return 0;
}
문제 5. 특정 경로를 따라 풀이 자라기
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int n;
vector<vector<int>> grid;
int bfsAlongPath(vector<pair<int, int>>& path) {
vector<vector<int>> visited(n, vector<int>(n, 0));
queue<pair<int, int>> q;
int count = 0;
for (auto& p : path) {
q.push(p);
visited[p.first][p.second] = 1;
}
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
count++;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && !visited[nx][ny] && grid[nx][ny] == 0) {
visited[nx][ny] = 1;
q.push({nx, ny});
}
}
}
return count;
}
int main() {
ifstream input("input1.txt");
input >> n;
grid.resize(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
input >> grid[i][j];
}
}
vector<pair<int, int>> path = {{0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}};
int result = bfsAlongPath(path);
cout << "Cells covered by grass: " << result << endl;
return 0;
}
2번
변형 문제 1: 대각선 이동이 가능한 미로
문제 설명:
기존의 미로 문제에서 대각선으로 이동할 수 있는 옵션을 추가하라. 즉, 상, 하, 좌, 우뿐만 아니라 대각선 방향(좌상, 우상, 좌하, 우하)으로도 이동할 수 있다. 이때 꺽은 횟수를 최소화하는 경로를 구하라.
- 대각선으로 이동 시에는 꺽은 횟수가 추가되지 않으며, 직선 방향으로 이동할 때만 꺽은 횟수가 증가한다.
- 이 문제에서는 총 8방향으로 이동이 가능하다.
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int x, y, direction, bends;
};
const int dx[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int dy[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int INF = 1000000;
int findMinBends(vector<vector<int>>& maze, int n) {
vector<vector<vector<int>>> visited(n, vector<vector<int>>(n, vector<int>(8, INF)));
queue<Node> q;
for (int d = 0; d < 8; ++d) {
q.push({0, 0, d, 0});
visited[0][0][d] = 0;
}
int minBends = INF;
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.x == n - 1 && cur.y == n - 1) {
minBends = min(minBends, cur.bends);
continue;
}
for (int d = 0; d < 8; ++d) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
int newBends = cur.bends + (cur.direction != d);
if (nx >= 0 && ny >= 0 && nx < n && ny < n && maze[nx][ny] == 0 && visited[nx][ny][d] > newBends) {
visited[nx][ny][d] = newBends;
q.push({nx, ny, d, newBends});
}
}
}
return minBends;
}
int main() {
ifstream input("input2.txt");
int n;
input >> n;
vector<vector<int>> maze(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
input >> maze[i][j];
}
}
int result = findMinBends(maze, n);
cout << result << endl;
return 0;
}
변형 문제 3: 여러 출구 찾기
문제 설명:
입구(0, 0)에서 출구(여러 지점)까지 가는 경로들 중에서 꺽은 횟수가 최소인 경로를 구하라. 출구는 여러 곳이 있을 수 있으며, 그 중에서 가장 최소한으로 꺽은 횟수를 찾는다.
- 출구는 여러 개가 있을 수 있고, 여러 출구 중에서 최소한의 꺽은 횟수를 갖는 경로를 선택해야 한다.
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int x, y, direction, bends;
};
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int INF = 1000000;
int findMinBendsToMultipleExits(vector<vector<int>>& maze, int n, vector<pair<int, int>>& exits) {
vector<vector<vector<int>>> visited(n, vector<vector<int>>(n, vector<int>(4, INF)));
queue<Node> q;
for (int d = 0; d < 4; ++d) {
q.push({0, 0, d, 0});
visited[0][0][d] = 0;
}
int minBends = INF;
while (!q.empty()) {
Node cur = q.front();
q.pop();
for (auto& exit : exits) {
if (cur.x == exit.first && cur.y == exit.second) {
minBends = min(minBends, cur.bends);
continue;
}
}
for (int d = 0; d < 4; ++d) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
int newBends = cur.bends + (cur.direction != d);
if (nx >= 0 && ny >= 0 && nx < n && ny < n && maze[nx][ny] == 0 && visited[nx][ny][d] > newBends) {
visited[nx][ny][d] = newBends;
q.push({nx, ny, d, newBends});
}
}
}
return minBends;
}
int main() {
ifstream input("input2.txt");
int n;
input >> n;
vector<vector<int>> maze(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
input >> maze[i][j];
}
}
vector<pair<int, int>> exits = {{2, 3}, {4, 5}, {1, 6}}; // 예시 출구 위치들
int result = findMinBendsToMultipleExits(maze, n, exits);
cout << result << endl;
return 0;
}
변형 문제 5: 미로에서 장애물이 랜덤으로 생성된다
문제 설명:
미로에서 일정 시간 간격으로 장애물이 랜덤하게 추가되거나 제거된다. 경로를 찾는 중에도 이 장애물이 언제 추가되거나 제거되는지 예측할 수 없으므로, 경로 탐색을 할 때 장애물이 추가되기 전이나 후를 고려해야 한다.
- 장애물이 추가될 때마다 해당 위치를 다시 계산하여 경로를 찾아야 한다.
- 장애물이 추가되거나 제거되는 시간은 랜덤하게 주어지며, 시간에 맞춰 경로를 재조정해야 한다.
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Node {
int x, y, direction, bends, time;
};
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int INF = 1000000;
void addRandomObstacles(vector<vector<int>>& maze, int n, int time) {
// 장애물이 랜덤하게 추가되는 부분
if (rand() % 2 == 0) {
int x = rand() % n;
int y = rand() % n;
maze[x][y] = 1; // 장애물 추가
}
}
int findMinBendsWithRandomObstacles(vector<vector<int>>& maze, int n) {
vector<vector<vector<int>>> visited(n, vector<vector<int>>(n, vector<int>(4, INF)));
queue<Node> q;
for (int d = 0; d < 4; ++d) {
q.push({0, 0, d, 0, 0});
visited[0][0][d] = 0;
}
int minBends = INF;
srand(time(0)); // 랜덤 시드 초기화
while (!q.empty()) {
Node cur = q.front();
q.pop();
// 장애물 추가
addRandomObstacles(maze, n, cur.time);
if (cur.x == n - 1 && cur.y == n - 1) {
minBends = min(minBends, cur.bends);
continue;
}
for (int d = 0; d < 4; ++d) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
int newBends = cur.bends + (cur.direction != d);
if (nx >= 0 && ny >= 0 && nx < n && ny < n && maze[nx][ny] == 0 && visited[nx][ny][d] > newBends) {
visited[nx][ny][d] = newBends;
q.push({nx, ny, d, newBends, cur.time + 1});
}
}
}
return minBends;
}
int main() {
ifstream input("input2.txt");
int n;
input >> n;
vector<vector<int>> maze(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
input >> maze[i][j];
}
}
int result = findMinBendsWithRandomObstacles(maze, n);
cout << result << endl;
return 0;
}
변형 문제 6: 미로에서 벽을 통과할 수 있는 능력 추가
문제 설명:
미로의 각 칸은 "일반 벽"과 "투명 벽"으로 나뉜다. "투명 벽"은 일정 시간 동안만 한 번 통과할 수 있으며, 그 후에는 다시 통과할 수 없다. 투명 벽을 통과한 횟수도 꺽은 횟수로 포함된다.
- 각 칸은 0 (통과 가능), 1 (일반 벽), 2 (투명 벽)으로 구분된다.
- "투명 벽"은 최대 한 번 통과 가능하며, 통과할 때마다 해당 칸을 다시 벽으로 바꿔야 한다.
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int x, y, direction, bends, transparentPasses;
};
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int INF = 1000000;
int findMinBendsWithTransparentWalls(vector<vector<int>>& maze, int n) {
vector<vector<vector<vector<int>>>> visited(n, vector<vector<vector<int>>>(n, vector<vector<int>>(4, vector<int>(2, INF))));
queue<Node> q;
for (int d = 0; d < 4; ++d) {
q.push({0, 0, d, 0, 0});
visited[0][0][d][0] = 0;
}
int minBends = INF;
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.x == n - 1 && cur.y == n - 1) {
minBends = min(minBends, cur.bends);
continue;
}
for (int d = 0; d < 4; ++d) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
int newBends = cur.bends + (cur.direction != d);
int newTransparentPasses = cur.transparentPasses;
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
if (maze[nx][ny] == 0) {
if (visited[nx][ny][d][newTransparentPasses] > newBends) {
visited[nx][ny][d][newTransparentPasses] = newBends;
q.push({nx, ny, d, newBends, newTransparentPasses});
}
} else if (maze[nx][ny] == 2 && newTransparentPasses == 0) {
newTransparentPasses = 1; // 투명 벽을 한 번 통과
if (visited[nx][ny][d][newTransparentPasses] > newBends) {
visited[nx][ny][d][newTransparentPasses] = newBends;
q.push({nx, ny, d, newBends, newTransparentPasses});
}
}
}
}
}
return minBends;
}
int main() {
ifstream input("input2.txt");
int n;
input >> n;
vector<vector<int>> maze(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
input >> maze[i][j];
}
}
int result = findMinBendsWithTransparentWalls(maze, n);
cout << result << endl;
return 0;
}형 문제 8: 미로에서 특정 칸을 반드시 지나야 한다
문제 설명:
미로에서 (a, b) 지점을 반드시 지나야 하는 경로를 구하라. 입구(0, 0)에서 출구(N-1, N-1)로 가는 경로 중 (a, b) 지점을 지나가야 하며, 이 경로에서의 꺾인 횟수를 최소화해야 한다.
- 미로에서 출발지(0,0)부터 반드시 (a, b) 지점까지 가고, 그 후 (N-1, N-1)으로 가는 경로를 찾는다.
- (a, b)를 반드시 통과하는 경로로 꺾인 횟수가 최소가 되는 경로를 찾아라.
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int x, y, direction, bends;
};
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int INF = 1000000;
int findMinBendsWithMandatoryPoint(vector<vector<int>>& maze, int n, int ax, int ay) {
vector<vector<vector<int>>> visited(n, vector<vector<int>>(n, vector<int>(4, INF)));
queue<Node> q;
for (int d = 0; d < 4; ++d) {
q.push({0, 0, d, 0});
visited[0][0][d] = 0;
}
int minBends = INF;
while (!q.empty()) {
Node cur = q.front();
q.pop();
// (a, b) 지점에 도달한 경우
if (cur.x == ax && cur.y == ay) {
// (a, b)를 지나가면 출구로 향하는 경로를 탐색
for (int d = 0; d < 4; ++d) {
if (visited[ax][ay][d] > cur.bends) {
visited[ax][ay][d] = cur.bends;
q.push({ax, ay, d, cur.bends});
}
}
}
// 출구까지의 경로 탐색
if (cur.x == n - 1 && cur.y == n - 1) {
minBends = min(minBends, cur.bends);
continue;
}
for (int d = 0; d < 4; ++d) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
int newBends = cur.bends + (cur.direction != d);
if (nx >= 0 && ny >= 0 && nx < n && ny < n && maze[nx][ny] == 0 && visited[nx][ny][d] > newBends) {
visited[nx][ny][d] = newBends;
q.push({nx, ny, d, newBends});
}
}
}
return minBends;
}
int main() {
ifstream input("input2.txt");
int n;
input >> n;
vector<vector<int>> maze(n, vector<int>(n));
int ax, ay;
input >> ax >> ay; // 반드시 지나야 할 지점
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
input >> maze[i][j];
}
}
int result = findMinBendsWithMandatoryPoint(maze, n, ax, ay);
cout << result << endl;
return 0;
}변형 문제 10: 미로에서 출구를 찾기 위한 여러 조건 추가
문제 설명:
미로에서 출구로 가는 경로를 찾는데, 이동 가능한 칸의 개수와 꺾인 횟수를 함께 고려해야 한다. 경로에서 반드시 일정 수 이상의 칸을 지나야 하며, 꺾인 횟수를 최소화하는 경로를 구하라.
- 경로에서 반드시 지나야 할 칸의 개수 (k개)를 지정한다.
- 그 조건을 만족하면서, 꺾은 횟수를 최소화하는 경로를 찾아라.
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct Node {
int x, y, direction, bends, visitedCount;
};
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int INF = 1000000;
int findMinBendsWithMinVisitedCells(vector<vector<int>>& maze, int n, int k) {
vector<vector<vector<vector<int>>>> visited(n, vector<vector<vector<int>>>(n, vector<vector<int>>(4, vector<int>(n*n, INF))));
queue<Node> q;
for (int d = 0; d < 4; ++d) {
q.push({0, 0, d, 0, 1});
visited[0][0][d][1] = 0;
}
int minBends = INF;
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.x == n - 1 && cur.y == n - 1 && cur.visitedCount >= k) {
minBends = min(minBends, cur.bends);
continue;
}
for (int d = 0; d < 4; ++d) {
int nx = cur.x + dx[d];
int ny = cur.y + dy[d];
int newBends = cur.bends + (cur.direction != d);
int newVisitedCount = cur.visitedCount + 1;
if (nx >= 0 && ny >= 0 && nx < n && ny < n && maze[nx][ny] == 0 && visited[nx][ny][d][newVisitedCount] > newBends) {
visited[nx][ny][d][newVisitedCount] = newBends;
q.push({nx, ny, d, newBends, newVisitedCount});
}
}
}
return minBends;
}
int main() {
ifstream input("input2.txt");
int n, k;
input >> n >> k;
vector<vector<int>> maze(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
input >> maze[i][j];
}
}
int result = findMinBendsWithMinVisitedCells(maze, n, k);
cout << result << endl;
return 0;
}
3번
변형 문제 1: 합이 K가 되는 정수 쌍의 개수 카운트 (K 범위 확장)
문제 설명:
기존의 문제에서 합이 정확히 K인 정수 쌍을 찾는 것 대신, 합이 K보다 작거나 K보다 큰 정수 쌍을 찾도록 변형하라. 이 문제는 K의 값이 주어졌을 때, 정수 쌍이 K보다 작은 경우와 큰 경우를 각각 구하라.
입력 예시:
10
1 2 3 4 5 6 7 8 9 10
13#include <iostream>
#include <string>
#define MAX 1000
using namespace std;
int arr[MAX];
int N, K;
int findCount(int start, int end, int count, bool findGreater)
{
if (start >= end)
return count;
int sum = arr[start] + arr[end];
if (findGreater) {
if (sum > K)
return findCount(start, end - 1, count + 1, findGreater);
else
return findCount(start + 1, end, count, findGreater);
} else {
if (sum < K)
return findCount(start + 1, end, count + 1, findGreater);
else
return findCount(start, end - 1, count, findGreater);
}
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> arr[i];
}
cin >> K;
int countLessThanK = findCount(0, N - 1, 0, false);
int countGreaterThanK = findCount(0, N - 1, 0, true);
cout << "Less than K: " << countLessThanK << endl;
cout << "Greater than K: " << countGreaterThanK << endl;
return 0;
}
변형 문제 2: 합이 짝수 또는 홀수인 정수 쌍 카운트
문제 설명:
정수 쌍의 합이 홀수인 경우와 짝수인 경우를 구하라. 주어진 정수 배열에서 합이 홀수인 쌍과 짝수인 쌍을 각각 카운트하는 프로그램을 작성하라.
입력 예시:
10
1 2 3 4 5 6 7 8 9 10#include <iostream>
#include <string>
#define MAX 1000
using namespace std;
int arr[MAX];
int N;
int findOddEvenCount(int start, int end, int oddCount, int evenCount)
{
if (start >= end)
return oddCount, evenCount;
int sum = arr[start] + arr[end];
if (sum % 2 == 0)
return findOddEvenCount(start + 1, end - 1, oddCount, evenCount + 1);
else
return findOddEvenCount(start + 1, end - 1, oddCount + 1, evenCount);
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> arr[i];
}
int oddCount, evenCount;
tie(oddCount, evenCount) = findOddEvenCount(0, N - 1, 0, 0);
cout << "Odd pairs: " << oddCount << endl;
cout << "Even pairs: " << evenCount << endl;
return 0;
}
변형 문제 3: 최대 합을 찾는 정수 쌍
문제 설명:
정수 배열에서 합이 K와 가까운 정수 쌍을 찾으라. 즉, arr[start] + arr[end]의 합이 K와 가장 가까운 쌍을 찾고, 그 합을 출력하는 프로그램을 작성하라.
#include <iostream>
#include <string>
#include <cmath>
#define MAX 1000
using namespace std;
int arr[MAX];
int N, K;
int findClosestSum(int start, int end, int closestSum)
{
if (start >= end)
return closestSum;
int sum = arr[start] + arr[end];
if (abs(sum - K) < abs(closestSum - K))
closestSum = sum;
if (sum > K)
return findClosestSum(start, end - 1, closestSum);
else if (sum < K)
return findClosestSum(start + 1, end, closestSum);
else
return closestSum;
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> arr[i];
}
cin >> K;
int result = findClosestSum(0, N - 1, arr[0] + arr[N - 1]);
cout << result << endl;
return 0;
}
변형 문제 4: 합이 K인 쌍 중, 두 숫자의 차이가 최소인 경우 찾기
문제 설명:
합이 K인 정수 쌍 중, 두 숫자의 차이가 최소인 쌍을 구하라. 합이 K인 모든 정수 쌍에 대해 두 숫자의 차이를 계산하고, 그 중 최소 차이를 가진 쌍을 구하라.
#include <iostream>
#include <string>
#include <cmath>
#define MAX 1000
using namespace std;
int arr[MAX];
int N, K;
int findMinDifference(int start, int end, int minDiff)
{
if (start >= end)
return minDiff;
int sum = arr[start] + arr[end];
if (sum == K) {
minDiff = min(minDiff, abs(arr[start] - arr[end]));
}
if (sum > K)
return findMinDifference(start, end - 1, minDiff);
else
return findMinDifference(start + 1, end, minDiff);
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> arr[i];
}
cin >> K;
int result = findMinDifference(0, N - 1, INT_MAX);
cout << result << endl;
return 0;
}변형 문제 5: 합이 K인 정수 쌍의 인덱스를 출력
문제 설명:
합이 K인 정수 쌍의 인덱스를 출력하라. 합이 K인 모든 정수 쌍에 대해 그 인덱스를 출력하는 프로그램을 작성하라.
#include <iostream>
#include <string>
#define MAX 1000
using namespace std;
int arr[MAX];
int N, K;
void findPairs(int start, int end)
{
if (start >= end)
return;
int sum = arr[start] + arr[end];
if (sum == K) {
cout << "(" << start + 1 << ", " << end + 1 << ")\n";
}
if (sum > K)
findPairs(start, end - 1);
else
findPairs(start + 1, end);
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> arr[i];
}
cin >> K;
findPairs(0, N - 1);
return 0;
}
4번
변형 문제 1: 양의 정수 배열에서 주어진 범위 내에서 floor와 ceiling 찾기
문제 설명:
오름차순으로 정렬된 양의 정수 배열에서 주어진 범위 내에서 K보다 작거나 같은 가장 큰 정수와 K보다 크거나 같은 가장 작은 정수를 찾으라. 범위는 주어진 min 값과 max 값으로 제한된다. 만약 해당 범위 내에서 존재하지 않으면 -1을 반환한다.
#include <iostream>
#include <vector>
using namespace std;
int floorValue(const vector<int>& arr, int start, int end, int K) {
if (start > end) return -1;
int mid = (start + end) / 2;
if (arr[mid] == K) return arr[mid];
if (arr[mid] > K) return floorValue(arr, start, mid - 1, K);
int res = floorValue(arr, mid + 1, end, K);
return res == -1 ? arr[mid] : res;
}
int ceilingValue(const vector<int>& arr, int start, int end, int K) {
if (start > end) return -1;
int mid = (start + end) / 2;
if (arr[mid] == K) return arr[mid];
if (arr[mid] < K) return ceilingValue(arr, mid + 1, end, K);
int res = ceilingValue(arr, start, mid - 1, K);
return res == -1 ? arr[mid] : res;
}
int main() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int K, minRange, maxRange;
cin >> K >> minRange >> maxRange;
int floor = floorValue(arr, minRange - 1, maxRange - 1, K);
int ceiling = ceilingValue(arr, minRange - 1, maxRange - 1, K);
cout << "Floor: " << floor << ", Ceiling: " << ceiling << endl;
return 0;
}
변형 문제 2: 배열에서 주어진 값보다 작은 모든 정수들 중 가장 큰 값을 찾아라
문제 설명:
주어진 오름차순 배열에서 K보다 작은 정수 중에서 가장 큰 값을 찾는 함수 findFloor를 구현하라. 만약 그런 값이 없으면 -1을 반환한다.
#include <iostream>
#include <vector>
using namespace std;
int findFloor(const vector<int>& arr, int start, int end, int K) {
if (start > end) return -1;
int mid = (start + end) / 2;
if (arr[mid] >= K) return findFloor(arr, start, mid - 1, K);
int res = findFloor(arr, mid + 1, end, K);
return res == -1 ? arr[mid] : res;
}
int main() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int K;
cin >> K;
int result = findFloor(arr, 0, N - 1, K);
cout << "Floor: " << result << endl;
return 0;
}
변형 문제 3: 배열에서 K보다 크거나 같은 값 중 가장 작은 값을 찾기
문제 설명:
주어진 오름차순 배열에서 K보다 크거나 같은 값 중 가장 작은 값을 찾는 함수 findCeiling을 구현하라. 만약 그런 값이 없으면 -1을 반환한다
#include <iostream>
#include <vector>
using namespace std;
int findCeiling(const vector<int>& arr, int start, int end, int K) {
if (start > end) return -1;
int mid = (start + end) / 2;
if (arr[mid] < K) return findCeiling(arr, mid + 1, end, K);
int res = findCeiling(arr, start, mid - 1, K);
return res == -1 ? arr[mid] : res;
}
int main() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int K;
cin >> K;
int result = findCeiling(arr, 0, N - 1, K);
cout << "Ceiling: " << result << endl;
return 0;
}
변형 문제 4: 범위 내에서 가장 큰 floor와 가장 작은 ceiling을 동시에 찾기
문제 설명:
주어진 범위 내에서 floor와 ceiling을 동시에 찾는 함수들을 구현하라. floor는 범위 내에서 K보다 작거나 같은 값 중 가장 큰 값을 찾고, ceiling은 범위 내에서 K보다 크거나 같은 값 중 가장 작은 값을 찾는다.
#include <iostream>
#include <vector>
using namespace std;
int findFloorInRange(const vector<int>& arr, int start, int end, int K) {
if (start > end) return -1;
int mid = (start + end) / 2;
if (arr[mid] > K) return findFloorInRange(arr, start, mid - 1, K);
int res = findFloorInRange(arr, mid + 1, end, K);
return res == -1 ? arr[mid] : res;
}
int findCeilingInRange(const vector<int>& arr, int start, int end, int K) {
if (start > end) return -1;
int mid = (start + end) / 2;
if (arr[mid] < K) return findCeilingInRange(arr, mid + 1, end, K);
int res = findCeilingInRange(arr, start, mid - 1, K);
return res == -1 ? arr[mid] : res;
}
int main() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int K, startRange, endRange;
cin >> K >> startRange >> endRange;
int floor = findFloorInRange(arr, startRange - 1, endRange - 1, K);
int ceiling = findCeilingInRange(arr, startRange - 1, endRange - 1, K);
cout << "Floor: " << floor << ", Ceiling: " << ceiling << endl;
return 0;
}
변형 문제 5: 정수 배열에서 floor와 ceiling이 두 값으로 나누어진 구간 찾기
문제 설명:
정수 배열에서 K를 기준으로 floor와 ceiling이 각각 다른 값으로 나누어지는 구간을 찾아라. 배열을 두 부분으로 나누고, 각 부분에서 floor와 ceiling을 찾는다. floor와 ceiling을 나누는 경계 인덱스를 출력하라
#include <iostream>
#include <vector>
using namespace std;
int findFloorInPart(const vector<int>& arr, int start, int end, int K) {
if (start > end) return -1;
int mid = (start + end) / 2;
if (arr[mid] > K) return findFloorInPart(arr, start, mid - 1, K);
int res = findFloorInPart(arr, mid + 1, end, K);
return res == -1 ? arr[mid] : res;
}
int findCeilingInPart(const vector<int>& arr, int start, int end, int K) {
if (start > end) return -1;
int mid = (start + end) / 2;
if (arr[mid] < K) return findCeilingInPart(arr, mid + 1, end, K);
int res = findCeilingInPart(arr, start, mid - 1, K);
return res == -1 ? arr[mid] : res;
}
int main() {
int N;
cin >> N;
vector<int> arr(N);
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
int K;
cin >> K;
int floor = findFloorInPart(arr, 0, N - 1, K);
int ceiling = findCeilingInPart(arr, 0, N - 1, K);
cout << "Floor: " << floor << ", Ceiling: " << ceiling << endl;
return 0;
}
5번문제
변형 문제 1: 다양한 시작점과 끝점으로 가는 경로의 개수 계산
문제 설명:
N x N 크기의 미로가 주어집니다. 미로의 출발점과 도착점은 각각 여러 곳으로 주어지며, 각 출발점에서 도착점으로 가는 경로의 개수를 계산하시오. 다만, 같은 위치를 두 번 이상 방문하지 않는 경로만 유효합니다. 모든 출발점에서 도착점까지 가능한 경로의 개수를 출력하시오.
조건:
- 미로에서 벽은 1, 빈 공간은 0으로 주어집니다.
- 출발점은 여러 개일 수 있습니다.
- 경로를 계산할 때, 이미 방문한 위치는 다시 방문할 수 없습니다.
- 출발점과 도착점은 각각 (0, 0)과 (N-1, N-1)입니다.
#include <iostream>
#include <vector>
using namespace std;
int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
bool visited[100][100] = { false };
int arr[100][100];
int pathCount = 0;
int N;
vector<pair<int, int>> starts; // 출발점들
int exit_x, exit_y;
void dfs(int x, int y) {
if (x == exit_x && y == exit_y) {
pathCount++;
return;
}
for (int i = 0; i < 4; i++) {
int newX = x + directions[i][0];
int newY = y + directions[i][1];
if (newX >= 0 && newX < N && newY >= 0 && newY < N &&
arr[newX][newY] == 0 && !visited[newX][newY]) {
visited[newX][newY] = true;
dfs(newX, newY);
visited[newX][newY] = false;
}
}
}
int main() {
cin >> N;
int x, y;
// 미로 입력
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
}
}
// 출발점 입력
int numStarts;
cin >> numStarts;
for (int i = 0; i < numStarts; i++) {
cin >> x >> y;
starts.push_back({x, y});
}
// 도착점은 항상 (N-1, N-1)
exit_x = N - 1;
exit_y = N - 1;
// 모든 출발점에서 DFS 실행
for (auto start : starts) {
int start_x = start.first;
int start_y = start.second;
visited[start_x][start_y] = true;
dfs(start_x, start_y);
visited[start_x][start_y] = false;
}
cout << pathCount << endl;
return 0;
}
변형 문제 2: 특정 칸을 반드시 통과해야 하는 경로 찾기
문제 설명:
미로에서 출발점과 도착점은 주어지고, 반드시 거쳐야 하는 특정 칸을 통과해야만 유효한 경로로 간주됩니다. 이 경로를 찾아서 가능한 경로의 개수를 출력하시오. 출발점에서 반드시 통과해야 하는 칸을 지나 도착점에 도달하는 경로만 계산합니다.
#include <iostream>
using namespace std;
int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
bool visited[100][100] = { false };
int arr[100][100];
int pathCount = 0;
int N;
int must_x, must_y; // 반드시 통과해야 하는 칸
int exit_x, exit_y;
void dfs(int x, int y, bool passedMust) {
if (x == exit_x && y == exit_y) {
if (passedMust) pathCount++; // 반드시 통과한 경로만 카운트
return;
}
for (int i = 0; i < 4; i++) {
int newX = x + directions[i][0];
int newY = y + directions[i][1];
if (newX >= 0 && newX < N && newY >= 0 && newY < N &&
arr[newX][newY] == 0 && !visited[newX][newY]) {
visited[newX][newY] = true;
dfs(newX, newY, passedMust || (newX == must_x && newY == must_y));
visited[newX][newY] = false;
}
}
}
int main() {
cin >> N;
int x, y;
// 미로 입력
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
}
}
// 반드시 통과해야 할 칸 입력
cin >> must_x >> must_y;
// 도착점은 항상 (N-1, N-1)
exit_x = N - 1;
exit_y = N - 1;
visited[0][0] = true;
dfs(0, 0, false);
cout << pathCount << endl;
return 0;
}
변형 문제 3: 출발점과 도착점의 벽으로 둘러싸인 미로 경로
문제 설명:
미로에서 출발점과 도착점이 벽으로 둘러싸인 구역에 있을 때, 경로를 찾는 문제입니다. 이 미로는 벽과 빈 공간 외에도 L 모양으로 길이 막혀있는 구역이 주어집니다. 미로를 탐색하여, 출발점에서 도착점까지 가는 경로의 개수를 계산하시오.
#include <iostream>
using namespace std;
int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
bool visited[100][100] = { false };
int arr[100][100];
int pathCount = 0;
int N;
int exit_x, exit_y;
void dfs(int x, int y) {
if (x == exit_x && y == exit_y) {
pathCount++;
return;
}
for (int i = 0; i < 4; i++) {
int newX = x + directions[i][0];
int newY = y + directions[i][1];
if (newX >= 0 && newX < N && newY >= 0 && newY < N &&
arr[newX][newY] == 0 && !visited[newX][newY]) {
visited[newX][newY] = true;
dfs(newX, newY);
visited[newX][newY] = false;
}
}
}
int main() {
cin >> N;
// 미로 입력
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
}
}
// 출발점은 항상 (0, 0), 도착점은 항상 (N-1, N-1)
exit_x = N - 1;
exit_y = N - 1;
visited[0][0] = true;
dfs(0, 0);
cout << pathCount << endl;
return 0;
}
변형 문제 4: 미로에서 다른 경로로 갈 수 있는 최소 경로 길이 찾기
문제 설명:
미로에서 두 개의 출발점에서 도착점까지 가는 여러 경로 중, 가장 짧은 경로를 구하는 문제입니다. 주어진 출발점에서 도착점까지 최소 경로 길이를 구하시오.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int arr[100][100];
bool visited[100][100] = { false };
int N;
struct Node {
int x, y, dist;
};
int bfs(int start_x, int start_y) {
queue<Node> q;
q.push({start_x, start_y, 0});
visited[start_x][start_y] = true;
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.x == N-1 && cur.y == N-1) {
return cur.dist;
}
for (int i = 0; i < 4; i++) {
int newX = cur.x + directions[i][0];
int newY = cur.y + directions[i][1];
if (newX >= 0 && newX < N && newY >= 0 && newY < N &&
arr[newX][newY] == 0 && !visited[newX][newY]) {
visited[newX][newY] = true;
q.push({newX, newY, cur.dist + 1});
}
}
}
return -1; // 경로가 없을 경우
}
int main() {
cin >> N;
// 미로 입력
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
}
}
int start_x = 0, start_y = 0;
visited[start_x][start_y] = true;
int result = bfs(start_x, start_y);
cout << result << endl;
return 0;
}
- 변형 문제 5: 미로에서 경로를 가는데 장애물이 있는 경우
- 문제 설명:
미로에서 출발점에서 도착점까지 가는 경로 중 장애물로 인해 일부 경로가 막히거나 제한됩니다. 장애물이 있는 구간을 피하면서 경로를 찾는 프로그램을 작성하시오. 경로 중 일부는 이동이 불가능하게 만들어지며, 그 장애물을 피하면서 출발점에서 도착점까지 가는 유효한 경로의 개수를 출력하시오.
#include <iostream>
using namespace std;
int directions[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
bool visited[100][100] = { false };
int arr[100][100];
int pathCount = 0;
int N;
int exit_x, exit_y;
void dfs(int x, int y) {
if (x == exit_x && y == exit_y) {
pathCount++;
return;
}
for (int i = 0; i < 4; i++) {
int newX = x + directions[i][0];
int newY = y + directions[i][1];
if (newX >= 0 && newX < N && newY >= 0 && newY < N &&
arr[newX][newY] == 0 && !visited[newX][newY]) {
visited[newX][newY] = true;
dfs(newX, newY);
visited[newX][newY] = false;
}
}
}
int main() {
cin >> N;
// 미로 입력
for (int i = 0; i < N; i++) {
for (int j = 0; j < N
문제 6
문제 1: 이진수열에서 K비트만큼 변경 가능한 모든 경우 출력하기
문제: 주어진 이진수열에서 정확히 K개의 비트를 변경하여 새로운 이진수열을 만들 수 있는 모든 경우를 출력하시오. K개의 비트를 변경한 모든 이진수열을 출력하되, 한 번에 하나의 비트만 변경 가능합니다. 출력되는 이진수열은 순서대로 출력하되, 중복을 제외해야 합니다.
입력:
- 첫 번째 줄에 이진수열 binarySeq와 정수 K가 주어진다. (1 ≤ N ≤ 16, 0 ≤ K ≤ N)
출력:
- K개의 비트만 변경하여 만들 수 있는 모든 이진수열을 출력한다. 중복되는 수열은 제외한다.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
// 비트 변경 함수
void generateSequences(string& binarySeq, int K, int index, int changedBits, set<string>& result) {
if (changedBits == K) {
result.insert(binarySeq);
return;
}
if (index == binarySeq.length()) return;
// 현재 비트를 변경하지 않은 경우
generateSequences(binarySeq, K, index + 1, changedBits, result);
// 현재 비트를 변경한 경우
binarySeq[index] = (binarySeq[index] == '0') ? '1' : '0'; // 반전
generateSequences(binarySeq, K, index + 1, changedBits + 1, result);
binarySeq[index] = (binarySeq[index] == '0') ? '1' : '0'; // 원래 상태로 복구
}
int main() {
string binarySeq;
int K;
cin >> binarySeq >> K;
set<string> result;
generateSequences(binarySeq, K, 0, 0, result);
for (const string& seq : result) {
cout << seq << " ";
}
cout << endl;
return 0;
}
문제 2: 주어진 이진수열에서 최소 반전 횟수로 목표 수열 만들기
문제: 주어진 이진수열에서 최소 반전 횟수를 이용해 목표 수열을 만들어야 합니다. 한 번에 전체 수열을 반전시키는 방식으로 작업을 합니다. 최소 횟수로 목표 수열을 만들어야 하며, 목표 수열을 만들 수 없는 경우는 -1을 출력하시오.
입력:
- 첫 번째 줄에 현재 이진수열과 목표 이진수열이 주어진다. (길이 N ≤ 16)
출력:
- 목표 수열을 만들기 위한 최소 반전 횟수를 출력한다. 불가능한 경우 -1을 출력한다
#include <iostream>
#include <string>
#include <queue>
#include <unordered_set>
using namespace std;
// 전체 수열을 반전시키는 함수
string flip(string s) {
for (int i = 0; i < s.length(); i++) {
s[i] = (s[i] == '0') ? '1' : '0';
}
return s;
}
int minFlipsToTarget(string binarySeq, string targetSeq) {
if (binarySeq == targetSeq) return 0;
queue<string> q;
unordered_set<string> visited;
q.push(binarySeq);
visited.insert(binarySeq);
int flips = 0;
while (!q.empty()) {
int size = q.size();
flips++;
for (int i = 0; i < size; i++) {
string current = q.front();
q.pop();
string flipped = flip(current);
if (flipped == targetSeq) return flips;
if (visited.find(flipped) == visited.end()) {
visited.insert(flipped);
q.push(flipped);
}
}
}
return -1; // 목표 수열을 만들 수 없는 경우
}
int main() {
string binarySeq, targetSeq;
cin >> binarySeq >> targetSeq;
int result = minFlipsToTarget(binarySeq, targetSeq);
cout << result << endl;
return 0;
}문제 3: 이진수열의 하밍 거리 계산하기 (하밍 거리 조건 추가)
문제: 두 이진수열이 주어졌을 때, 두 수열에서 서로 다른 비트의 개수를 계산하여 하밍 거리를 구하시오. 이때, 두 이진수열에서의 "하밍 거리"는 두 수열에서 한 번에 변경할 수 있는 비트 수로 정의합니다. 각 이진수열에서 K번만 비트를 변경하여 두 수열이 같아질 수 있는지 판단하시오. 만약 같아지지 않으면 -1을 출력합니다.
입력:
- 첫 번째 줄에 두 이진수열이 주어지며, 두 번째 줄에 K가 주어진다.
출력:
- 두 수열이 같아질 수 있으면 최소 비트 변경 횟수를 출력하고, 불가능한 경우 -1을 출력하시오.
#include <iostream>
#include <string>
using namespace std;
int calculateHammingDistance(const string& seq1, const string& seq2) {
int distance = 0;
for (int i = 0; i < seq1.length(); i++) {
if (seq1[i] != seq2[i]) {
distance++;
}
}
return distance;
}
int main() {
string seq1, seq2;
int K;
cin >> seq1 >> seq2 >> K;
if (seq1.length() != seq2.length()) {
cout << "-1" << endl;
return 0;
}
int hammingDistance = calculateHammingDistance(seq1, seq2);
if (hammingDistance == K) {
cout << K << endl;
} else {
cout << "-1" << endl;
}
return 0;
}
문제 7
문제 1: 행운수 찾기 (범위 제한과 무한 연산의 결합)
문제: 주어진 수 N(1 ≤ N ≤ 1,000,000)에 대해, 주어진 범위 내에서 행운수인지 아닌지 판별하는 프로그램을 작성하시오. 이 문제에서는 단순히 N이 행운수인지 아닌지를 확인하는 것이 아니라, 주어진 범위 내에서 행운수의 개수를 구하는 문제로 변형됩니다.
입력:
- 첫 번째 줄에 하나의 정수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
출력:
- 1부터 N까지의 범위 내에서 행운수의 개수를 출력하시오
#include <iostream>
#include <vector>
using namespace std;
vector<bool> generateLuckyNumbers(int maxLimit) {
vector<bool> isLucky(maxLimit + 1, true);
vector<int> luckyNumbers;
isLucky[0] = false; // 0은 제외
for (int i = 2; i <= maxLimit; i++) {
if (isLucky[i]) {
luckyNumbers.push_back(i);
for (int j = i * 2; j <= maxLimit; j += i) {
isLucky[j] = false;
}
}
}
return isLucky;
}
int countLuckyNumbers(int N) {
vector<bool> lucky = generateLuckyNumbers(N);
int count = 0;
for (int i = 1; i <= N; i++) {
if (lucky[i]) {
count++;
}
}
return count;
}
int main() {
int N;
cin >> N;
cout << countLuckyNumbers(N) << endl;
return 0;
}
문제 2: 행운수에서 소수 찾기 (행운수와 소수의 결합)
문제: 주어진 수 N까지의 범위에서, 행운수이면서 소수인 수들의 개수를 구하는 프로그램을 작성하시오. 이 문제에서는 행운수로 필터링된 수들 중에서 소수인 숫자만 골라 출력해야 합니다.
입력:
- 첫 번째 줄에 하나의 정수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
출력:
- 1부터 N까지의 범위 내에서 행운수이면서 소수인 수들의 개수를 출력하시오.
#include <iostream>
#include <vector>
using namespace std;
vector<bool> generateLuckyNumbers(int maxLimit) {
vector<bool> isLucky(maxLimit + 1, true);
vector<int> luckyNumbers;
isLucky[0] = false;
for (int i = 2; i <= maxLimit; i++) {
if (isLucky[i]) {
luckyNumbers.push_back(i);
for (int j = i * 2; j <= maxLimit; j += i) {
isLucky[j] = false;
}
}
}
return isLucky;
}
vector<bool> generatePrimeNumbers(int maxLimit) {
vector<bool> isPrime(maxLimit + 1, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= maxLimit; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= maxLimit; j += i) {
isPrime[j] = false;
}
}
}
return isPrime;
}
int countLuckyPrimes(int N) {
vector<bool> lucky = generateLuckyNumbers(N);
vector<bool> prime = generatePrimeNumbers(N);
int count = 0;
for (int i = 1; i <= N; i++) {
if (lucky[i] && prime[i]) {
count++;
}
}
return count;
}
int main() {
int N;
cin >> N;
cout << countLuckyPrimes(N) << endl;
return 0;
}
문제 3: 행운수에 대한 최소 비트 연산을 찾기
문제: 주어진 수 N에 대해, 행운수 중에서 1부터 N까지의 수들 중 가장 작은 두 행운수의 XOR값을 구하시오. (XOR 연산은 두 수를 이진수로 바꾼 뒤 대응하는 비트를 비교하여 다른 비트가 있을 경우 1, 동일하면 0을 반환하는 연산입니다.)
입력:
- 첫 번째 줄에 하나의 정수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
출력:
- 1부터 N까지의 범위 내에서 행운수들 중 가장 작은 두 수의 XOR값을 출력하시오.
#include <iostream>
#include <vector>
using namespace std;
vector<bool> generateLuckyNumbers(int maxLimit) {
vector<bool> isLucky(maxLimit + 1, true);
isLucky[0] = false; // 0은 제외
for (int i = 2; i <= maxLimit; i++) {
if (isLucky[i]) {
for (int j = i * 2; j <= maxLimit; j += i) {
isLucky[j] = false;
}
}
}
return isLucky;
}
int main() {
int N;
cin >> N;
vector<bool> lucky = generateLuckyNumbers(N);
// 행운수들만 찾기
vector<int> luckyNumbers;
for (int i = 1; i <= N; i++) {
if (lucky[i]) {
luckyNumbers.push_back(i);
}
}
if (luckyNumbers.size() < 2) {
cout << -1 << endl; // 두 개 이상의 행운수가 없으면 -1
} else {
// 가장 작은 두 행운수 XOR 계산
int result = luckyNumbers[0] ^ luckyNumbers[1];
cout << result << endl;
}
return 0;
}문제 4: 행운수들의 합이 주어진 수에 맞는 경우 찾기
문제: 1부터 N까지의 범위 내에서 행운수들의 합이 주어진 K와 일치하는 경우를 찾아 출력하시오. (여러 개의 경우가 있을 수 있음)
입력:
- 첫 번째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ K ≤ 100,000)
출력:
- 행운수들의 합이 K가 되는 경우가 있을 경우 그 합을 만드는 행운수들의 수열을 출력하시오. 없다면 -1을 출력하시오.
#include <iostream>
#include <vector>
using namespace std;
vector<bool> generateLuckyNumbers(int maxLimit) {
vector<bool> isLucky(maxLimit + 1, true);
isLucky[0] = false; // 0은 제외
for (int i = 2; i <= maxLimit; i++) {
if (isLucky[i]) {
for (int j = i * 2; j <= maxLimit; j += i) {
isLucky[j] = false;
}
}
}
return isLucky;
}
bool findLuckySum(int N, int K) {
vector<bool> lucky = generateLuckyNumbers(N);
vector<int> luckyNumbers;
for (int i = 1; i <= N; i++) {
if (lucky[i]) {
luckyNumbers.push_back(i);
}
}
// 부분합을 구해 K와 일치하는지 확인
for (int i = 0; i < (1 << luckyNumbers.size()); i++) {
int sum = 0;
for (int j = 0; j < luckyNumbers.size(); j++) {
if (i & (1 << j)) {
sum += luckyNumbers[j];
}
}
if (sum == K) {
cout << "Lucky numbers sum: ";
for (int j = 0; j < luckyNumbers.size(); j++) {
if (i & (1 << j)) {
cout << luckyNumbers[j] << " ";
}
}
cout << endl;
return true;
}
}
return false;
}
int main() {
int N, K;
cin >> N >> K;
if (!findLuckySum(N, K)) {
cout << -1 << endl;
}
return 0;
}
8번이동
문제 1: 다양한 말들이 있는 장기판에서 포(包)의 이동
문제: 주어진 N×N 크기의 장기판에서 포(包)는 다른 말들을 하나 건너뛰고 상하좌우로 이동할 수 있습니다. 하지만 장기판에는 여러 종류의 말들이 존재하고, 포(包)는 자신이 속한 색상의 말만 건너뛸 수 있습니다. 목표는 주어진 출발점에서 도착점까지 이동이 가능한지 여부를 판단하는 프로그램을 작성하는 것입니다. 각 말의 색상은 다른 값으로 주어집니다.
입력:
- 첫 번째 줄에 장기판의 크기 N이 주어진다. (1 ≤ N < 16)
- 그 다음 N개의 줄에 장기판 상태가 주어진다. 빈 칸은 0, 다른 말들은 1 이상으로 주어진다.
- 포(包)가 놓인 출발점 좌표와 목표점 좌표가 주어진다.
출력:
- 주어진 출발점에서 목표점까지 포(包)가 이동할 수 있으면 "Yes", 그렇지 않으면 "No"를 출력한다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int directions[4][2] = {{-2, 0}, {2, 0}, {0, -2}, {0, 2}}; // 상, 하, 좌, 우로 이동 (건너뛰기)
vector<vector<int>> board;
int N;
bool isValid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && board[x][y] == 0;
}
bool bfs(pair<int, int> start, pair<int, int> end) {
queue<pair<int, int>> q;
vector<vector<bool>> visited(N, vector<bool>(N, false));
visited[start.first][start.second] = true;
q.push(start);
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == end.first && y == end.second) return true;
for (auto& dir : directions) {
int nx = x + dir[0];
int ny = y + dir[1];
if (isValid(nx, ny) && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
return false;
}
int main() {
cin >> N;
board.resize(N, vector<int>(N));
pair<int, int> start, end;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
}
}
cin >> start.first >> start.second;
cin >> end.first >> end.second;
if (bfs(start, end)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}문제 2: 장기판에서 포(包)와 다른 말들이 상호작용하는 문제
문제: 주어진 장기판에서 포(包)는 상하좌우로 이동할 수 있지만, 다른 말들이 있을 때마다 특정 조건이 충족되어야만 이동할 수 있습니다. 포는 자신이 이동할 때 다른 말을 '건너뛰어야' 하는데, 그 말이 특정 색상일 경우에만 가능합니다. 이 문제에서는 포(包)가 이동하려는 칸에 특정 색상의 말이 있을 때만 이동이 가능하며, 그 말의 색상을 기준으로 이동해야 합니다.
입력:
- 첫 번째 줄에 장기판의 크기 N이 주어진다. (1 ≤ N < 16)
- 그 다음 N개의 줄에 장기판 상태가 주어진다. 빈 칸은 0, 말들은 1 이상으로 표시됩니다.
- 포(包)가 놓인 출발점 좌표와 목표점 좌표가 주어진다.
- 포는 자신이 이동할 때, 같은 색상의 말이 있는 칸만 건너뛰고 이동할 수 있습니다.
출력:
- 주어진 출발점에서 목표점까지 포(包)가 이동할 수 있으면 "Yes", 그렇지 않으면 "No"를 출력합니다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int directions[4][2] = {{-2, 0}, {2, 0}, {0, -2}, {0, 2}};
vector<vector<int>> board;
int N;
bool isValid(int x, int y, int targetColor) {
return x >= 0 && x < N && y >= 0 && y < N && (board[x][y] == 0 || board[x][y] == targetColor);
}
bool bfs(pair<int, int> start, pair<int, int> end, int targetColor) {
queue<pair<int, int>> q;
vector<vector<bool>> visited(N, vector<bool>(N, false));
visited[start.first][start.second] = true;
q.push(start);
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == end.first && y == end.second) return true;
for (auto& dir : directions) {
int nx = x + dir[0];
int ny = y + dir[1];
if (isValid(nx, ny, targetColor) && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
return false;
}
int main() {
cin >> N;
board.resize(N, vector<int>(N));
pair<int, int> start, end;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
}
}
cin >> start.first >> start.second;
cin >> end.first >> end.second;
int targetColor = board[start.first][start.second];
if (bfs(start, end, targetColor)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}
문제 3: 다중말이 있는 장기판에서 포(包)의 이동을 여러 번 수행
문제: 주어진 장기판에서 포(包)가 여러 번 이동해야 할 때, 포가 지정된 횟수만큼 이동할 수 있는지 검사하는 문제입니다. 포(包)는 각 이동마다 건너뛸 수 있는 칸이 제한되므로, 정해진 횟수만큼 정확히 이동할 수 있는지 판단합니다.
입력:
- 첫 번째 줄에 장기판의 크기 N이 주어진다. (1 ≤ N < 16)
- 그 다음 N개의 줄에 장기판 상태가 주어진다. 빈 칸은 0, 말들은 1 이상으로 표시됩니다.
- 포(包)의 출발점 좌표와 목표점 좌표가 주어진다.
- 포(包)가 이동해야 할 횟수 K가 주어진다.
출력:
- 포(包)가 정확히 K번 이동하여 목표 위치에 도달할 수 있으면 "Yes", 그렇지 않으면 "No"를 출력합니다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int directions[4][2] = {{-2, 0}, {2, 0}, {0, -2}, {0, 2}};
vector<vector<int>> board;
int N, K;
bool isValid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && board[x][y] == 0;
}
bool bfs(pair<int, int> start, pair<int, int> end, int K) {
queue<pair<pair<int, int>, int>> q;
vector<vector<vector<bool>>> visited(N, vector<vector<bool>>(N, vector<bool>(K+1, false)));
visited[start.first][start.second][0] = true;
q.push({start, 0});
while (!q.empty()) {
auto [[x, y], step] = q.front(); q.pop();
if (x == end.first && y == end.second && step == K) return true;
if (step < K) {
for (auto& dir : directions) {
int nx = x + dir[0];
int ny = y + dir[1];
if (isValid(nx, ny) && !visited[nx][ny][step+1]) {
visited[nx][ny][step+1] = true;
q.push({{nx, ny}, step + 1});
}
}
}
}
return false;
}
int main() {
cin >> N >> K;
board.resize(N, vector<int>(N));
pair<int, int> start, end;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
}
}
cin >> start.first >> start.second;
cin >> end.first >> end.second;
if (bfs(start, end, K)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}문제 2: 왕과 차의 이동
문제: 주어진 장기판에서 왕(王)과 차(車)가 출발점에서 목표지점으로 이동할 수 있는지 여부를 확인하는 프로그램을 작성하세요.
- **왕(王)**은 상하좌우로 1칸씩만 이동할 수 있습니다.
- **차(車)**는 수평, 수직으로 한 번에 여러 칸을 이동할 수 있지만, 중간에 다른 말이 있으면 이동할 수 없습니다.
- 장기판은 0으로 빈 칸, 1로 다른 말들이 차지하고 있습니다.
입력:
- 첫 번째 줄에 장기판의 크기 N이 주어진다. (1 ≤ N ≤ 16)
- 그 다음 N개의 줄에 장기판 상태가 주어진다. 0은 빈 칸, 1은 다른 말들이 차지하고 있다.
- 왕과 차의 출발점 좌표와 목표지점 좌표가 주어진다.
출력:
- 왕과 차가 목표지점에 도달할 수 있으면 "Yes", 그렇지 않으면 "No"를 출력한다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 왕(王)의 이동 규칙: 상하좌우 1칸씩만 이동
int kingDirections[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 차(車)의 이동 규칙: 수평, 수직으로 한 번에 여러 칸을 이동 (중간에 다른 말이 있으면 안 됨)
int carDirections[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<int>> board;
int N;
bool isValid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && board[x][y] == 0;
}
bool bfsKing(pair<int, int> start, pair<int, int> end) {
queue<pair<int, int>> q;
vector<vector<bool>> visited(N, vector<bool>(N, false));
visited[start.first][start.second] = true;
q.push(start);
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == end.first && y == end.second) return true;
for (auto& dir : kingDirections) {
int nx = x + dir[0];
int ny = y + dir[1];
if (isValid(nx, ny) && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
return false;
}
bool bfsCar(pair<int, int> start, pair<int, int> end) {
queue<pair<int, int>> q;
vector<vector<bool>> visited(N, vector<bool>(N, false));
visited[start.first][start.second] = true;
q.push(start);
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
if (x == end.first && y == end.second) return true;
for (auto& dir : carDirections) {
int nx = x;
int ny = y;
// 차는 수평, 수직으로 여러 칸을 이동하므로 한 방향으로 계속 이동
while (true) {
nx += dir[0];
ny += dir[1];
if (!isValid(nx, ny)) break; // 벽이나 다른 말이 있으면 멈춤
if (visited[nx][ny]) break; // 이미 방문한 칸은 멈춤
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
return false;
}
int main() {
cin >> N;
board.resize(N, vector<int>(N));
pair<int, int> kingStart, kingEnd, carStart, carEnd;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> board[i][j];
}
}
// 왕과 차의 출발점과 목표지점 입력 받기
cin >> kingStart.first >> kingStart.second;
cin >> kingEnd.first >> kingEnd.second;
cin >> carStart.first >> carStart.second;
cin >> carEnd.first >> carEnd.second;
bool kingCanReach = bfsKing(kingStart, kingEnd);
bool carCanReach = bfsCar(carStart, carEnd);
if (kingCanReach && carCanReach) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}문제 4: 기병과 포의 이동
문제:
- 주어진 N×N 크기의 장기판에서, 기병과 포라는 말을 출발점에서 목표지점으로 이동할 수 있는지 검사하는 프로그램을 작성하세요.
- 기병은 "말처럼" 이동합니다. 즉, "L"자 모양으로 이동할 수 있습니다. (2칸 직선, 1칸 회전)
- 포는 "사각형" 모양으로 이동합니다. 즉, 직선으로 여러 칸을 이동할 수 있으며, 중간에 다른 말이 있어도 지나갈 수 있습니다.
- 장기판은 0으로 빈 칸, 1로 다른 말들이 차지하고 있습니다.
- 기병과 포는 같은 이동을 할 수 없으며, 각각의 말이 목표지점에 도달할 수 있는지 여부를 출력해야 합니다.
입력:
- 첫 번째 줄에 장기판의 크기 N이 주어진다. (1 ≤ N ≤ 16)
- 그 다음 N개의 줄에 장기판 상태가 주어진다. 0은 빈 칸, 1은 다른 말들이 차지하고 있다.
- 기병과 포의 출발점 좌표와 목표지점 좌표가 주어진다.
출력:
- 기병과 포가 각각 목표지점에 도달할 수 있으면 "Yes", 그렇지 않으면 "No"를 출력한다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N;
vector<vector<int>> board;
struct Position {
int x, y;
};
int knightMoves[8][2] = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}, {2, -1}, {2, 1}};
int cannonMoves[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool isValid(int x, int y) {
return x >= 0 && x < N && y >= 0 && y < N && board[x][y] == 0;
}
// 기병의 이동을 위한 BFS
bool bfsKnight(Position start, Position target) {
queue<Position> q;
vector<vector<bool>> visited(N, vector<bool>(N, false));
q.push(start);
visited[start.x][start.y] = true;
while (!q.empty()) {
Position cur = q.front();
q.pop();
if (cur.x == target.x && cur.y == target.y)
return true;
for (int i = 0; i < 8; ++i) {
int nx = cur.x + knightMoves[i][0];
int ny = cur.y + knightMoves[i][1];
if (isValid(nx, ny) && !visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
return false;
}
// 포의 이동을 위한 BFS (직선으로만)
bool bfsCannon(Position start, Position target) {
queue<Position> q;
vector<vector<bool>> visited(N, vector<bool>(N, false));
q.push(start);
visited[start.x][start.y] = true;
while (!q.empty()) {
Position cur = q.front();
q.pop();
if (cur.x == target.x && cur.y == target.y)
return true;
for (int i = 0; i < 4; ++i) {
int nx = cur.x;
int ny = cur.y;
// 직선으로 여러 칸 이동
while (true) {
nx += cannonMoves[i][0];
ny += cannonMoves[i][1];
if (!isValid(nx, ny)) break;
if (visited[nx][ny]) continue;
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
return false;
}
int main() {
cin >> N;
board.resize(N, vector<int>(N));
// 장기판 입력 받기
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> board[i][j];
}
}
Position knightStart, cannonStart, target;
cin >> knightStart.x >> knightStart.y;
cin >> cannonStart.x >> cannonStart.y;
cin >> target.x >> target.y;
// 기병과 포의 이동 여부 검사
if (bfsKnight(knightStart, target)) {
cout << "Knight can reach the target!" << endl;
} else {
cout << "Knight cannot reach the target." << endl;
}
if (bfsCannon(cannonStart, target)) {
cout << "Cannon can reach the target!" << endl;
} else {
cout << "Cannon cannot reach the target." << endl;
}
return 0;
}
반응형
'IT 프로그래밍 > 자료구조' 카테고리의 다른 글
| 연결리스트 - 스택 큐 구현 (0) | 2024.12.15 |
|---|---|
| 자료구조 예상문제 3 - 시간복잡도 (0) | 2024.12.15 |
| 자료구조 - 예상문제 3 스택, 큐, 직접 구현하기 (0) | 2024.12.15 |
| 자료구조 예상문제2 - 미로찾기문제 (2) | 2024.12.15 |
| 자료구조 예상 문제 1 (0) | 2024.12.15 |