이세계개발자의 개발일지

이번 문제는 13549번 숨바꼭질 3이다문제 요약수빈이는 현재 위치 N, 동생은 위치 K에 있고 수빈이가 이동할 수 있는 방법은 세 가지다X - 1 (1초 소요)X + 1 (1초 소요)X * 2 (0초 소요)즉, 간선의 가중치가 0 또는 1인 그래프 최단거리 문제인데 일반 BFS로는 가중치 차이를 반영할 수 없기 때문에, 덱을 이용한 0-1 BFS가 필요합니다. 덱(deque)Double Ended Queue의 줄임말 → “앞뒤 양쪽에서 넣고 뺄 수 있는 큐”std::deque 로 C++ STL에서 제공특징:push_front() / pop_front() → 앞에서 삽입·삭제push_back() / pop_back() → 뒤에서 삽입·삭제즉, 스택(stack)과 큐(queue)의 장점을 합쳐 놓은 자료구..

이번 문제는 3733번 Shares 입니다문제 요약n명의 교수와 s명의 학생이 있다교수들이 학생들에게 돈을 똑같이 나눠주려고 할 때, 학생 한 명이 받을 수 있는 최대 돈의 액수를 출력하는 문제 접근법S를 N+1로 나눈 나머지를 출력합니다.작성코드#include int main(){ int n, s; while (scanf("%d %d", &n, &s) != EOF){ printf("%d\n", s/(n+1)); } return 0;}

이번 문제는 12851번 숨바꼭질 2이다.문제 요약수빈이는 위치 N, 동생은 위치 K에 있다수빈이는 1초마다 다음 세 가지 행동 중 하나를 할 수 있음X - 1 로 이동X + 1 로 이동X × 2 로 순간이동문제는 수빈이가 동생을 찾는 데 걸리는 최소 시간 & 최소 시간으로 도달하는 경우의 수 출력문제 설계노드 = 위치(0 ~ 100000)간선 = 한 번의 이동(X-1, X+1, X*2)이동 시간은 모두 1초 → BFS(너비 우선 탐색) 으로 해결 가능distance[pos] : 시작점에서 pos까지의 최단 시간way[pos] : 시작점에서 pos까지 최단 시간으로 도달하는 경우의 수BFS 탐색 과정에서:처음 방문하는 경우 → 최단 시간 기록 + 경우의 수 전달이미 최단 시간으로 도달한 적 있음 → 경..

이번 문제는 1697번 숨바꼭질이다문제 요약수빈이는 현재 점 N에 있고, 동생은 점 K에 있는데 수빈이는 매 초마다 다음 세 가지 행동 중 하나를 할 수 있다X - 1 로 이동X + 1 로 이동X × 2 로 순간이동목표는 수빈이가 동생에게 도달하는 최소 시간을 구하는 것좌표의 범위 = 0 ≤ N, K ≤ 100000 아이디어모든 이동의 가중치가 동일(=1초) 이므로 BFS(너비 우선 탐색) 을 적용하면 된다BFS는 가까운 곳부터 탐색하기 때문에, 처음으로 K에 도착했을 때의 시간이 곧 최소 시간정점(Vertex): 수빈이가 위치할 수 있는 좌표 (0 ~ 100000)간선(Edge): 한 번의 이동 (X-1, X+1, X*2)작성코드#include using namespace std;int N,K;int ..

이번 문제는 2178번 미로탐색이문제 요약N×M 크기의 미로가 주어질 때 미로는 0(벽), 1(길)로 이루어져 있고,시작점 (1,1)에서 도착점 (N,M)까지 이동할 때 지나야 하는 최소 칸 수를 구하는 문제이다이동은 상하좌우 네 방향만 가능하고 최단 거리를 구해야 하므로 DFS가 아니라 BFS를 써서 해결해야 하는 유형이다 아이디어 정리BFS가까운 곳부터 차례대로 탐색하기 때문에 최단 거리에 적합큐(queue)를 사용하여 현재 칸에서 이동 가능한 칸을 차례로 넣고, 한 칸씩 꺼내면서 탐색한다거리 저장단순히 방문 여부만 체크하면 안 되고, 해당 칸까지 도달하는 최단 거리를 기록해야 한다distance 배열을 따로 두어 (이전 칸 거리 + 1)로 갱신해야 함좌표 주의입력은 (1,1)에서 시작하는 것처럼 보..

이번 문제는 1189번 컴백홈이다문제 요약지도는 R × C 크기의 격자각 칸은 빈 칸(.) 또는 장애물(T)시작점: 왼쪽 아래 (R-1, 0)도착점: 오른쪽 위 (0, C-1)이동은 상하좌우로만 가능같은 칸을 두 번 방문할 수 없음정확히 K 칸을 지나 도착해야 함접근법DFS (깊이 우선 탐색)현재 위치에서 상하좌우 탐색장애물이거나 방문한 적 있는 칸은 무시이동 거리를 하나씩 늘려가며 탐색거리가 K가 되었을 때 도착점에 있다면 경우의 수 +1백트래킹 (방문 표시 후 해제)방문 여부를 체크하면서 DFS 실행탐색 후에는 방문 해제(visited[nx][ny] = false)해서 다른 경로도 탐색 가능하게 함좌표계 처리 주의입력은 R행 × C열본 코드는 graph[C][R] 구조 (열, 행 순서)로 관리작성코드..

이번 문제는 2583번 영역 구하기다문제 설명크기가 M × N인 2차원 평면이 있고 이 평면에 직사각형 K개가 주어지며, 각 직사각형 영역은 색칠되어 있다고 가정합니다.색칠된 부분을 제외한 나머지 빈 칸들이 몇 개의 분리된 영역을 이루는지, 그리고 각 영역의 넓이를 구하는 문제다출력:영역의 개수각 영역의 넓이(오름차순)접근법그래프 초기화graph[y][x] 형태로 M×N 크기의 2차원 bool 배열을 만든다직사각형이 주어지면 해당 구역을 true(막힘)로 표시한다DFS 탐색아직 방문하지 않았고(!visited), 색칠되지 않은(!graph) 좌표에서 DFS를 시작DFS를 통해 상하좌우로 인접한 빈 칸을 모두 탐색하며 영역의 넓이를 계산결과 저장탐색이 끝날 때마다 영역 개수를 +1 하고, 해당 영역 넓이를..

이번 방학 목표였던 골드 달성에 성공했다 🎉🎉아쉽게도 스트릭이 30일에서 끊겨서 다시 최장스트릭에 도전중이다。。。。。。그래도 골드는 달성했으니 이번 방학 소기의 목표는 달성한 것 같아 기부니가 좋다

문제 요약N명의 사람과 M개의 친구 관계가 주어진다친구 관계는 양방향이며, 한 사람과 다른 사람은 친구의 친구를 통해 연결될 수 있다케빈 베이컨 수: 한 사람이 다른 모든 사람과 연결되는 최소 단계 수들의 합케빈 베이컨 수가 가장 작은 사람의 번호를 출력접근법이 문제의 핵심은 모든 노드에서 다른 모든 노드까지의 최단 거리 합을 구하는 것이다A와 B가 직접 친구라면 거리는 1A의 친구의 친구라면 거리는 2최단 거리 합이 가장 작은 노드를 출력최단 거리 구하는 방법BFS 사용BFS는 한 레벨씩 탐색하므로 최단 거리 계산에 최적시간 복잡도: O(N × (N+M)) → N ≤ 100 이므로 충분히 가능DFS 는 최단거리를 구할 수 없다 （DFS + 백트레킹 -> TLE）플로이드 워셜 or BFS 를 사용해야 함..

이번 문제는 1325번 효율적인 해킹이다문제 설명N개의 컴퓨터와 M개의 단방향 신뢰 관계가 주어짐A B라는 입력은 B 컴퓨터가 A 컴퓨터를 신뢰한다는 뜻한 컴퓨터를 해킹하면, 그 컴퓨터를 신뢰하는 컴퓨터도 해킹 가능가장 많은 컴퓨터를 해킹할 수 있는 시작 컴퓨터 번호를 모두 출력해야 함문제 접근단방향 간선이 주어지고, 한 노드에서 시작해 도달 가능한 모든 노드를 세는 문제이므로 DFS 또는 BFS로 해결할 수 있다A B가 주어졌을 때, B → A 방향으로 그래프를 구성해야 함이유: B를 해킹하면 A도 해킹 가능하기 때문각 노드를 시작점으로 DFS를 실행해 몇 개의 노드를 해킹할 수 있는지 계산가장 많이 해킹할 수 있는 노드의 번호를 출력 작성코드#include using namespace std;int ..