민우의 코딩노트

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

✅️[한 것] 1. 백준 알고리즘 BFS 4문제 풀기 2. 사이드 프로젝트 회고글 1개 올리기 ✅️[배운점] Spring Security, JWT, OAuth 복습 ✅️[느낀점] ❗️사이드 프로젝트를 진행했었는데, 회고글 및 프로젝트 정리가 필요함을 다시금 느낀다. 늘 다른 사람들을 보면 내가 부족한 것이 엄청 많음이 와닿는 것 같다. 포기하지 않고 꾸준히 라는 모토로, 부족하더라도 욕심없이 배우려고 노력하자.😊 언젠가는 성장하겠지? 📚[할것] 1. BFS 4문제 풀기 2. 사이드 프로젝트 회고글 1개 작성하기 3. 우아한테크코스 영상 정리하기

✅️[문제] https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ✅️[풀이] ❗️주의할점은 인덱스가 200000을 넘기면 안된다는 것이다! 인덱스가 200000을 넘어가면 OutofBound 에러가 생기므로 주의하자. ✅️ 각각의 좌표마다 +1, -1, ×2를 해주어 좌표를 누적하여 더한후, k에 도달하면 출력해주면 된다! ✅️[코드] #include using namespace std; int arr[2000100]; ..

✅️[문제] https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ✅️[풀이] ❗️(m,n) 에서 좌표중 값이 1인 것을 큐에 넣는다! BFS를 돌려서, 이동 가능한 좌표에 이전 좌표의 값 + 1을 해주는 방식이다. (m,n)에 대해 좌표값중 0이 있으면 불가능으로 판단하고, 0이 없는 경우 각 좌표의 최댓값을 출력하면 된다! ✅️[코드] #include using namespace std; #define X first #define..

✅️[문제] https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net ✅️[풀이] 불과 지훈이의 좌표를 따로 큐에 넣어 각각 BFS를 돌리면 된다! ❗️주의할점은 지훈이의 좌표보다 불의 좌표를 큐에 먼저 넣어야 되는 점이다. 왜냐하면, 지훈이의 맨 처음 좌표가 가장자리에 있는 경우라면 지훈이의 탈출 최소 경로가 잘못되어 계산할 수 있기 때문이다. ❗️지훈이와 불의 방문 여부를 체크하지 않으면 시간초과가 날 수 있으므로 주의하자! ✔️ 지훈..