민우의 코딩노트

✅️[문제/Problem] https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net ✅️[풀이/Explanation] 재귀 문제이다. 재귀 문제를 풀때 baseConditon(종료 조건)과 n, n+1일때 풀이에 집중해야 한다. 종료 조건은 처음 주어진 수와 반복문 내에서 배열 값이 같지 않을때 종료하도록 한다. 재귀함수에서 n/2를 호출하여 좌표값을 부르면 된다. Solving method is the recursive fu..

✅️[문제] https://www.acmicpc.net/source/47203953 로그인 www.acmicpc.net ✅️[풀이] BFS 문제이다. 입력받은 좌표에 대해 arr의 값을 1씩 증가시키고, arr이 0인 것에 대해 BFS를 돌려 횟수를 증가시킨다. ✅️[코드] #include using namespace std; #define X first #define Y second int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; int main(){ ios::sync_with_stdio(0); cin.tie(0); int m,n,k; cin >> m >> n >> k; int arr[m][n]; bool vis[m][n]; memset(arr, 0, sizeof(..

✅️[문제] https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net ✅️[풀이] 재귀 문제이다! 재귀 문제를 풀때에는 수학적 귀납법을 이용하면 된다. 수학적 귀납법은 k=1이 성립하고, k와 k+1이 성립하면 식은 참이 된다. 이 문제에서 b가 1일때 나머지를 구할수 있고, 2b와 2b+1의 나머지를 구할 수 있다. 즉 b가 1일때는 a%c를 리턴하고, b/2를 재귀적으로 호출한다. 이때 b/2가 홀수라면, a를 한번 더 곱하여 나머지를 리턴하고, 짝수라면 그냥 나머지를 리턴하면 된다. ✅️[코드] #include ..

✅️[문제] https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net ✅️[풀이] 나이트의 이동을 BFS로 풀면 된다. 한 번의 이동을 8번으로 늘리면 된다! 그리고 목표 좌표에 도착하면 vis 값을 출력한다. ✅️[코드] #include using namespace std; #define X first #define Y second int dx[8] = {-2,-1,1,2,-2,-1,1,2}; int dy[8] = {-1,-2,-2,-1,1,2,2,1}..

✅️[문제] https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net ✅️[풀이] BFS 문제이다! 불이 먼저 이동 하기 위해 불을 먼저 큐에 넣어두고, 상근이의 위치를 맨 나중에 넣어준다. 그리고 3차원 배열 vis를 통해 불의 이동과 상근이의 이동을 분리 시켜주고, 상근이가 가장자리에 도착했다면 vis값을 출력한 후 탈출시킨다. ✅️[코드] #include using namespace std; #define X first #define Y second int v..