민우의 코딩노트

✅️[문제/problem] https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net ✅️[풀이/Explanation] 백트래킹 문제이다. 재귀함수랑 백트래킹은 유사성이 크다. 일단 isarr 배열로 1~n까지의 숫자가 쓰인 여부를 체크한다. arr 배열은 숫자를 저장할 배열이다. 종료 조건은 k == n일때 숫자를 출력하고 return;을 반환한다. ✅️[코드/code] #include using namespace std; int n,m; bool i..

✅️[문제/problem] https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net ✅️[풀이/Explanation] 재귀 문제이다! 종료 조건(base_condition)은 n=3일때 그리고, 종료한다. 그림에서 가로는 n, 세로는 n/2 인걸 알 수 있다. (x,y) 기준으로 재귀적으로 3개의 삼각형을 그려주면 되는데, (x+n/2, y), (x, y+n/2), (x+n/2, y+n)의 좌표를 호출하면 된다! memset으로 배열을 공백으로 초기화하고 별을 찍을때 *값을 대입했다. ✅️[코드/code]..

✅[문제/Problem] https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ✅[풀이/Explanation] BFS 문제이다. 단순히 for 문을 돌려 1일때 큐에 좌표값을 넣고, BFS를 돌려 넓이 값을 벡터에 넣어주면 된다. 주의할 점은 입력을 받을때 숫자가 띄어져 있지 않으므로, 문자열에 입력받아야 한다. 이것이 은근 헷갈린다. 마지막으로인자를 넣은 벡터의 사이즈와 배열 값을 출력한다. The solving method is to use BFS..

✅️[문제/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..

✅️[문제] https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net ✅️[풀이] BFS 문제! 단순히 BFS를 돌릴때 방문횟수가 없는 큐에 처음 넣을때 ans+=1을 해주면 되는 문제이다! ✅️[코드] #include using namespace std; #define X first #define Y second int arr[52][52]; bool vis[52][52]; int dx[4] = {1,0,-1,0}; int dy[4] = {0,1,0,-1}; in..

✅️[문제] https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net ✅️[풀이] BFS 문제 적록색약이 아닌 경우, 이중 for문을 돌려 방문횟수가 없는 경우 ans+=1을 해주고, 큐에 넣어 BFS를 진행한다. 적록색약인 경우, 앞서와 같이 이중 for문을 돌려 방문횟수가 없는 경우 ans+=1을 해주고, 큐에 넣는다. BFS를 진행할때 색이 R or G인 경우에 B가 나오면 continue를 시키면 된다! ✅️[코드] #include usi..