경우없는 개발 블로그

https://www.acmicpc.net/problem/13019

#문제 간단 정리

문제의 핵심은 A 문자열에서 한 문자를 선택하여 문자열의 가장 앞으로 가져오는 방식으로 B 문자열을 만드는 것입니다. 그러기 위해 최소한으로 문자열을 바꿔야 하는 횟수를 찾아야 합니다. 만약 A 문자열을 B 문자열로 변경할 수 없는 경우 -1을 출력해야 합니다.

#전체 코드

#include <iostream>
#include <algorithm>

using namespace std;


int main() {

    
    string A, B;
    cin >> A >>  B;

    int ans = 0;

    int B_index = B.length() - 1;
    for (int i = A.length()-1; i >= 0; i--) {
        if (A[i] == B[B_index]) {
            B_index --;
        }
        else ans++;

    }

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    if (A == B) cout << ans;
    else cout << -1;



    return 0;
}

https://www.acmicpc.net/problem/7576

#문제 간단 정리

이 문제는 주어진 토마토의 상태에 따라 모든 토마토가 익게 되는 최소 일수를 찾는 문제입니다. 문제에서 요구하는 답을 찾기 위해 BFS(Breadth-First Search) 탐색 알고리즘을 사용합니다.

#전체 코드

#include <iostream>
#include <queue>
using namespace std;
int a[1000][1000];
int d[1000][1000];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

struct tomato {
    int x, y;
};

int main() {
    int n, m;
    cin >> m >> n;
    queue<tomato> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            d[i][j] = -1;
            if (a[i][j] == 1) {
                q.push({i,j});
                d[i][j] = 0;
            }
        }
    }
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (a[nx][ny] == 0 && d[nx][ny] == -1) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx,ny});
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ans < d[i][j]) {
                ans = d[i][j];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 0 && d[i][j] == -1) {
                ans = -1;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

#코드설명

코드 설명

• 변수 선언
  • a[1000][1000]: 각 토마토의 초기 상태를 저장하는 2D 배열
  • d[1000][1000]: 각 토마토가 익게 되는 데 걸리는 일수를 저장하는 2D 배열. 초기값은 -1로 설정
  • dx[], dy[]: 토마토의 인접한 위치를 찾기 위해 현재 위치에 더할 값들을 저장하는 배열
  • tomato: 토마토의 위치를 나타내는 구조체
• 입력 받기
  • m, n: 상자의 가로와 세로 크기
  • 상자의 토마토 상태를 입력 받으면서, 이미 익어 있는 토마토의 위치를 큐에 넣고, 해당 위치의 d[][] 값을 0으로 설정합니다.
• BFS 탐색
  • BFS 탐색을 시작합니다. 큐가 비어있지 않은 동안, 현재 토마토의 위치에서 인접한 네 방향을 확인하며 다음을 수행합니다:
    • 인접한 위치가 상자 내부에 있는지 확인합니다.
    • 인접한 위치의 토마토가 아직 익지 않았고, 방문하지 않은 상태라면, 현재 토마토가 익는 데 걸린 일수에 1을 더한 값을 인접한 위치의 토마토가 익는 데 걸리는 일수로 설정합니다.
    • 인접한 위치의 토마토를 큐에 넣습니다.
• 결과 찾기
  • BFS 탐색이 끝나면, d[][] 배열에서 가장 큰 값을 찾아 ans에 저장합니다. 이 값이 모든 토마토가 익게 되는 데 필요한 최소 일수입니다.
  • 하지만, 상자 안에 아직 익지 않은 토마토가 있는지 확인하고, 있다면 -1을 출력해야 합니다. 이를 위해 a[][] 배열을 탐색하며 아직 익지 않은 토마토가 있는지 확인합니다. 익지 않은 토마토가 있으면 ans 값을 -1로 설정합니다.
• 결과 출력
  • ans 값을 출력합니다.

이 코드는 BFS 탐색을 사용하여 모든 토마토가 익게 되는 최소 일수를 효율적으로 찾습니다.

https://www.acmicpc.net/problem/7562

#문제 간단 정리

체스판 위에서 나이트가 이동하는 최소 횟수를 계산하는 문제를 해결하기 위한 코드입니다. 코드는 입력으로 주어지는 테스트 케이스를 처리하고, 각 테스트 케이스에 대해 나이트가 최소 몇 번 움직여야 하는지를 출력합니다. 코드는 너비 우선 탐색(BFS)을 사용하여 문제를 해결합니다

#전체 코드

#include <iostream>
#include <queue>

using namespace std;

int dx[] = { 2, 1, -1, -2, -2 ,-1,1,2, };
int dy[] = { 1,2,2,1,-1,-2,-2,-1 };

struct point {
	int x, y;
};

int main() {


	int N; cin >> N;
	while (N--) {
		int I;
		cin >> I;
		point now, target;
		cin >> now.x >> now.y >> target.x >> target.y;

		if (now.x == target.x && now.y == target.y) {
			cout << '0' << endl;
			continue;
		}

		int chessBoard[300][300] = { 0, };

		queue<point> q;
		q.push(now);
		chessBoard[q.front().x][q.front().y] = 0;

		while (!q.empty()) {
			int x = q.front().x;
			int y = q.front().y;
			q.pop();
			for (int i = 0; i < 8; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (0 <= nx && nx < I && 0 <= ny && ny < I) {
					if (chessBoard[nx][ny] == 0) {
						q.push({ nx,ny });
						chessBoard[nx][ny] = chessBoard[x][y] + 1;
					}
				}

			}
		}

		cout << chessBoard[target.x][target.y]<< endl;

		
	}






	return 0;
}

#문제 해결 방법

해당 문제는 나이트의 이동을 최소한의 움직임으로 목표 위치까지 가는 최단 거리를 찾는 문제입니다. 이를 위해 BFS(Breadth-First Search)를 사용합니다.

문제 해설:

1. 나이트의 이동
   나이트는 8가지 방향으로 움직일 수 있습니다. 문제에서 제시한 그림을 참고하면, 나이트의 모든 움직임을 (dx, dy)의 형태로 나타낼 수 있습니다.
2. BFS
   BFS는 시작 지점부터 가장 가까운 지점들부터 차례대로 탐색하는 알고리즘입니다. 체스판에서의 나이트 이동도 이 알고리즘으로 효율적으로 해결할 수 있습니다. BFS를 사용하면, 각 칸에 도달하는 데 필요한 최소한의 움직임 횟수를 찾을 수 있습니다.

코드 설명:

• 변수
  • dx, dy: 나이트의 이동 방향을 저장한 배열입니다.
  • point: x, y 좌표를 갖는 구조체입니다.
  • chessBoard: 각 위치에 도달하기 위한 최소 움직임 횟수를 저장하는 체스판입니다.
• 프로세스
  1. 테스트 케이스의 수를 입력 받습니다.
  2. 각 테스트 케이스마다
     • 체스판의 크기, 시작 위치, 목표 위치를 입력 받습니다.
     • 시작 위치와 목표 위치가 같다면, 움직일 필요가 없으므로 0을 출력하고 다음 테스트 케이스로 넘어갑니다.
     • 그렇지 않다면, BFS로 최단 거리를 찾습니다.
     • BFS를 진행하며, 체스판에 각 칸까지 도달하기 위한 최소 움직임 횟수를 저장합니다.
     • 목표 위치까지의 최소 움직임 횟수를 출력합니다.

BFS를 사용하여 문제를 해결하면, 체스판의 각 칸까지 도달하는 데 필요한 최소 움직임 횟수를 효율적으로 찾을 수 있습니다.

1018번: 체스판 다시 칠하기 (acmicpc.net)

#문제 간단 정리

문제 상황: 지민이는 MxN 크기의 보드를 발견했습니다. 이 보드는 검은색(B)과 흰색(W)의 정사각형으로 구성되어 있습니다. 지민이는 이 보드에서 8x8 크기의 체스판 부분을 잘라내고 싶습니다.

조건: 체스판의 규칙에 따라 각 칸은 검은색과 흰색으로 번갈아가면서 칠해져야 합니다. 체스판의 맨 왼쪽 위 칸의 색깔에 따라 두 가지 색칠 방식이 있습니다.

목표: 8x8 크기로 잘라낸 부분에서 체스판 규칙에 얼마나 많이 위배되는지 확인하고, 최소 몇 개의 정사각형을 다시 칠해야 하는지 결정하는 프로그램을 작성해야 합니다.    

#문제 해결 방법

목적: 이 코드는 주어진 보드에서 8x8 크기의 체스판을 찾아서, 체스판의 첫 번째 칸이 'W' 또는 'B'로 시작할 때 각각 몇 개의 사각형을 다시 그려야 하는지 계산하고, 그 중 최소값을 출력합니다.

변수 및 자료구조 설명:

• board[50][50]: 전체 보드를 나타내는 2차원 문자 배열입니다.
• N, M: 보드의 크기를 나타내는 변수로, N은 행의 수, M은 열의 수입니다.
• ansPoint: 8x8 체스판을 그릴 때 필요한 최소 수정 횟수를 저장하는 벡터입니다.

함수 설명:

• makeChessBoard(int startX, int startY, int N, int M): 시작점 (startX, startY)에서 8x8 크기의 체스판을 그리기 위해 필요한 최소 수정 횟수를 반환합니다.
  • 체스판의 첫 번째 칸이 'W'로 시작하는 경우와 'B'로 시작하는 경우에 대해 각각 계산하여 더 작은 값을 반환합니다.

메인 프로그램 설명:

1. 입출력 속도 향상을 위한 설정을 합니다.
2. 보드의 크기 N과 M을 입력받습니다.
3. 보드의 각 칸에 대한 값을 입력받아 board에 저장합니다.
4. 모든 위치에서 8x8 크기의 체스판을 그릴 수 있는지 확인하고, 가능한 경우 makeChessBoard 함수를 호출하여 필요한 최소 수정 횟수를 계산하고, ansPoint 벡터에 추가합니다.
5. ansPoint 벡터를 오름차순으로 정렬하고, 첫 번째 원소 (즉, 가장 작은 값)을 출력합니다.

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

char board[50][50];
int N, M;
vector<int> ansPoint;

int makeChessBoard(int startX, int startY,int N, int M) {
    int ansCount1 = 0;
    int ansCount2 = 0;

    int n = startX + 8;
    int m = startY + 8;

    if (n > N || m > M) {
        return 123456789;
    }

    for (int i = startX; i < n; i++) {
        for (int j = startY; j < m; j++) {
            // 0 0이 W인경우
            if ((i - startX) % 2 == 0 && (j - startY) % 2 == 0) {
                if (board[i][j] == 'B') ansCount1++;
            }
            if ((i - startX) % 2 == 0 && (j - startY) % 2 != 0) {
                if (board[i][j] == 'W') ansCount1++;
            }
            if ((i - startX) % 2 != 0 && (j - startY) % 2 != 0) {
                if (board[i][j] == 'B') ansCount1++;
            }
            if ((i - startX) % 2 != 0 && (j - startY) % 2 == 0) {
                if (board[i][j] == 'W') ansCount1++;
            }

            //0 0이 B 인경우
            if ((i - startX) % 2 == 0 && (j - startY) % 2 == 0) {
                if (board[i][j] == 'W') ansCount2++;
            }
            if ((i - startX) % 2 == 0 && (j - startY) % 2 != 0) {
                if (board[i][j] == 'B') ansCount2++;
            }

            if ((i - startX) % 2 != 0 && (j - startY) % 2 != 0) {
                if (board[i][j] == 'W') ansCount2++;
            }
            if ((i - startX) % 2 != 0 && (j - startY) % 2 == 0) {
                if (board[i][j] == 'B') ansCount2++;
            }
        }
    }

    return(ansCount1 > ansCount2 ? ansCount2 : ansCount1);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        string input; cin >> input;
        for (int j = 0; j < M; j++) {
            board[i][j] = input[j];
        }
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            int ans = makeChessBoard(i, j,N,M);
            if (ans != 123456789) {
                ansPoint.push_back(ans);
            }
            
        }
    }
    
    
    sort(ansPoint.begin(), ansPoint.end());
    cout << ansPoint.front();
    

    return 0;
}

#후기

훨씬더 간단한 해결책이 있다...

바로 정답 체스판을 가져와서 비교하는 방법이다.

어쩌면 이렇게 간단한 풀이법이 묘미일지도 모른다 

더 간단한 해결한 블로그 링크

[백준 / BOJ] - 1018번 체스판 다시 칠하기 C++ 풀이 :: Just Give Me The Code (tistory.com)

https://www.acmicpc.net/problem/2178

#문제 간단 정리

핵심: 최단거리 문제는 BFS 를 사용하자

DFS를 사용하면 시간 초과가 난다

쉽게 생각해보면 하나의 길을 끝까지 갔다가

다시 되돌아 와서 다시 가니까 

BFS보다 시간이 훨씬 더 걸릴 거라는 것을 알아낼 수 있다.

#문제 해결 방법

1. 전역 변수 선언:
   • maze[100][100]: 미로 정보 저장 (1은 이동 가능, 0은 이동 불가능).
   • check[100][100]: 해당 위치를 방문했는지 여부를 저장.
   • dist[100][100]: 시작점부터 해당 위치까지의 이동 횟수를 저장.
   • dx[], dy[]: 주변 4 방향(상, 하, 좌, 우)을 탐색하기 위한 좌표 변경값.
   • q: BFS(너비 우선 탐색)에 사용되는 큐.
2. findWay 함수:
   • BFS를 사용하여 미로 탐색.
   • 현재 위치에서 상하좌우 4 방향을 탐색하여 이동 가능하고 아직 방문하지 않은 위치를 큐에 추가.
   • 큐에서 뽑힌 위치는 이미 방문한 것이므로 check를 true로 설정.
   • 이동 횟수(dist)는 이전 위치의 이동 횟수 + 1.
3. main 함수:
   • 입력을 받아 미로를 초기화.
   • 시작점인 (0, 0)을 큐에 추가하고 check와 dist를 초기화.
   • findWay 함수를 호출하여 BFS로 미로 탐색.
   • 최종 목적지인 (n-1, m-1)까지의 최단 이동 횟수를 출력.

이 코드의 핵심은 BFS를 사용하여 미로 내에서의 최단 경로를 찾는 것입니다. BFS는 모든 가능한 경로를 너비 우선으로 탐색하므로 최초로 목적지에 도달할 때, 그 경로는 가장 짧은 경로가 보장됩니다.

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, m;

int maze[100][100];
int check[100][100] = { false };
int dist[100][100];

int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1,-1,0,0 };
queue<pair <int, int>> q;

void findWay(queue<pair<int,int>> q) {
    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 (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (check[nx][ny] == false && maze[nx][ny] == 1) {
                    q.push(make_pair(nx, ny));
                    dist[nx][ny] = dist[x][y] + 1;
                    check[nx][ny] = true;
                }
            }
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        string input; cin >> input;
        for (int j = 0; j < m; j++) {
            if (input[j] == '1') {
                maze[i][j] = 1;
            }
            else {
                maze[i][j] = 0;
            }
        }
    }

    q.push(make_pair(0, 0));
    check[0][0] = true;
    dist[0][0] = 1;

    findWay(q);

    

    cout << dist[n-1][m-1];

    return 0;
}

https://www.acmicpc.net/problem/9252

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

string input1;
string input2;

void findAns(int i, int j, vector<vector<int>>& dp) {
    if (i == 0 || j == 0) return; // Base case
    if (input1[i - 1] == input2[j - 1]) {
        findAns(i - 1, j - 1, dp);
        cout << input1[i - 1];
    }
    else {
        if (dp[i - 1][j] > dp[i][j - 1]) {
            findAns(i - 1, j, dp);
        }
        else {
            findAns(i, j - 1, dp);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> input1 >> input2;

    int n = input1.size();
    int m = input2.size();

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (input1[i - 1] == input2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[n][m] << endl;

    findAns(n, m, dp); // 출력 함수 호출

    return 0;
}

https://www.acmicpc.net/problem/1260

#전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;
vector<int> a[1001];
bool check[1001];

void dfs(int node) {
    check[node] = true;
    cout << node<<" ";

    for (int i = 0; i < a[node].size(); i++) {
        int next = a[node][i];
        if (check[next] == false) {
            dfs(next);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    memset(check, false, sizeof(check));
    check[start] = true;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node<<" ";
        for (int i = 0; i < a[node].size(); i++) {
            int next = a[node][i];
            if (check[next] == false) {
                check[next] = true;
                q.push(next);
            }
        }
    }
}

int main() {
    int n, m, start;

    cin >> n >> m >> start;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        sort(a[i].begin(), a[i].end());
    }

    dfs(start);
    puts("");

    bfs(start);
    puts("");

    

    return 0;
}

전체 코드

#include<vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int arr[10001] = { 0, };
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int input;
        cin >> input;
        arr[input]++;
        
    }

    for (int i = 1; i <= 10000; i++) {
        if (arr[i] != 0) {
            for (int j = 1; j <= arr[i]; j++) {
                cout << i << "\n";
            }
        }
    }
}

다른 정렬방법으로 나중에 풀어봐야겠다.

https://www.acmicpc.net/problem/11866

문제 간단 정리

원으로 앉아있고 K번째마다 제거되기 때문에 K 번째가 아닐때는 제외하고 큐를 사용하여 뒤를 넘겨주면 

구현이 가능할테지만... 큐를 사용하지 않고 풀었다, 큐를 사용해서 푼 블로그 참조 https://cocoon1787.tistory.com/234

하지만 나는 그냥 큐 사용을 안하고 구현될 것 같아서 다르게 풀었다.

문제 해결 방법

대략 내가 직접 하나하나 세가면서 한다 생각하고 구현하였다.

수를 제거함을 알기위해서 count 변수, 지금 가리키고 있는 수인 포인터 index 변수

수가 제거되었는지 체크하기 위해서 bool 변수 flag를 설정해 두었다.

flag가 false라면 count++(그 수를 지나감을 의미) ,

count가 K(번째 수)가 되었다면 그 수를 제외하고(flag를 true로) 정답에 넣기

정답의 수가 총 N의 개수와 같아진다면 break;

만일 index가 범위를 벗어났다면 1로 초기화

전체 코드

#include<vector>
#include <iostream>
using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin >> N >> K;

    int index = 1, count = 0;
    bool flag[1001] = { 0, };
    vector<int> ans;

    while (1) {


        if (flag[index] == false) {
            
            count++;

            if (count == K) {
                ans.push_back(index);
                flag[index] = true;
                count = 0;
            }
        }

        if (ans.size() == N) {
            break;
        }

        index++;
        if (index > N) {
            index = 1;
        }

        //cout << "index:" << index << "\n";
    }

    cout << "<";
    for (int i = 0; i < ans.size(); i++) {
        if (i == ans.size() - 1) {
            cout << ans[i] << ">";

        }else cout << ans[i] << ", ";


    }

}

문제 간단 정리

정렬문제 아마도 내장함수를 사용하지 않는다면 n logN의 시간복잡도를 갖는 정렬로 풀어야한다.

문제 해결 방법

sort 내장함수 사용 ><

전체 코드

#include<vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<int> vec;
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int input;
        cin >> input;
        vec.push_back(input);
    }
    sort(vec.begin(), vec.end());

    for (int a : vec) {
        cout << a << "\n";
    }
}