❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악행 R, 열 C (1 ≤ R, C ≤ 1000)지훈이 위치는 오직 1개탈출할 수있다면 탈출까지 걸린 최소시간없다면 "IMPOSSIBLE" 출력✏️ 문제풀이동시성 구현이 문제에서 가장 까다로운건 '동시성'을 어떻게 해결할지에 대한 고민입니다. 불과 지훈이는 동시에 이동하기 때문입니다.기존 BFS를 돌릴 때, 우리는 큐가 빌 때까지 돌리기 위해 `while(!q.empty())`를 관용구 처럼 사용했습니다.하지만, 이번에는 다릅니다. 현재 시간에 큐에 들어있는 요소들을 처리하는 동안 다음 시간에 이동할 예정인 칸들이 큐에 들어오기 때문입니다. 이것들은 '지금' 처리하면 안 되겠지요.이러한 문제에서 '지금', '현재' 큐에 들어있는 요소만 처리하기 위해서 for..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악땅 크기 N×N (1 ≤ N ≤ 50)L ≤ 인구 차이 ≤ R (1 ≤ L ≤ R ≤ 100)✏️ 문제풀이문제에 인구 이동 로직이 나와있기 때문에 그대로 실수없이 구현하면 되는 문제입니다.인구 이동 과정은 ① 연합 만들기 - ② 인구 이동 - ③ 인구 이동 ? 시간 증가 : 종료 후 정답 출력으로 요약할 수 있습니다. 코드로 간략하게 나타내면 다음과 같습니다.while (true) { // 1. 연합 만들기 for (int y = 0; y  연합은 임의의 시작점을 기점으로 DFS를 1회 돌리면 만들 수 있습니다.갈 수 있는 모든 국가에 방문표시 및 외부 배열에 좌표를 저장합니다. 이렇게 연합이 만들어지면, 인구 이동을 실시합니다. 모든 점을 검사했는데..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악크기가 N×N인 도시, N(2 ≤ N ≤ 50)최대 치킨집 개수 M(1 ≤ M ≤ 13)집의 개수 ≤ 2NM ≤ 치킨집의 개수 ≤ 13도시의 치킨 거리의 최솟값✏️ 문제풀이우선, 문제를 bruteforce로 풀 수 있는지 확인하기 위해, 최악의 경우 몇 번 연산이 필요한지 생각해봅시다.N이 50이고, 총 치킨집이 13개 있으며, 여기서 6개 (또는 7개)를 뽑는 경우라고 생각합시다.치킨집을 뽑는 총 경우의 수는 $_13C_6 = 1,716$입니다.각 경우의 수마다 최대 100개의 집에 대해 치킨거리를 검사합니다.∴ 충분히 시간제한 1초 내로 문제를 풀 수 있다고 판단됐으니, 바로 로직을 생각하러 넘어갑시다.A개 중에서 B개를 뽑는 조합 (combinatio..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악수열 A의 크기 N (1 ≤ N ≤ 1,000,000)✏️ 문제풀이3 5 2 7예제 입력 1을 먼저 생각해봅시다.3은 5와 짝지어집니다.5는 7과 짝지어집니다.2는 7과 짝지어집니다.그래서 결과적으로 `5 7 7 -1` 이라는 답이 나옵니다.짝 지어짐, 짝을 찾음 이라는 개념에서 '스택'을 떠올리셔야 합니다. (관련문제: 9012 :: 괄호, 4949 :: 균형잡힌 세상)스택의 가장 위에 있는 값 (`top()`)보다 작은 값을 만나면 스택에 `push()` 됩니다.반면에 더 큰 값(`big` 이라고 할까요?)을 만나면 `big`보다 큰 값이 스택의 가장 위에 올 때까지 `pop()` 합니다. (없다면 스택이 비게 되겠지요)`pop()` 하면서 오큰수를 저..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악N개의 컴퓨터 ≤ 10,000, M개의 관계도 ≤ 100,000컴퓨터 번호는 1번부터 N번한 번에 가장 많이 해킹할 수 있는 컴퓨터 번호를 오름차순으로 (하나면 한개, 두 개 이상이면 오름차순으로)✏️ 문제풀이트리도 그래프의 일종임을 생각하면 어렵지 않게 접근법을 생각할 수 있습니다. 입력으로 들어오는 A, B는 'A가 B를 신뢰한다' = 'B를 해킹하면 A도 해킹할 수 있다' = B → A로 생각할 수 있습니다. 즉, 문제에서 말하는바와는 반대방향으로 간선이 만들어지는 겁니다. A가 B를 신뢰하지만, 간선은 B에서 A를 향하도록 만들어집니다 이렇게 간선을 이어서 트리를 형성했을 때, 한 번에 가장 많이 해킹할 수 있는 컴퓨터란, 해당 노드를 시점으로 DF..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악노드 개수 N ≤ 50입력: 0 ~ (N-1)번 노드의 부모 정보, 루트노드는 -1출력: 리프노드의 개수✏️ 문제풀이문제에 나와있지 않은 조건을 자신도 모르게 '당연히 그러겠지~'라고 생각하고 풀지 않기를 연습하기 좋은 문제입니다.(비슷한 문제로 2468 :: 안전영역이 있습니다.) 문제 어디에도 주어지는 노드가 '이진 트리'라는 정보가 없습니다. 예시로 주어지는 그림이 이진트리라 햇갈리기 정말 좋습니다. 정말로 트리를 구현할 필요는 없습니다.각 노드의 부모가 입력되므로 배열의 각 칸마다 자식노드의 번호들을 저장하면 됩니다.이때, 앞서 언급했듯이 이진트리가 아니기 때문에 각 칸마다 왼쪽/오른쪽 자식노드의 번호를 저장하기 위해 `std::vector>` 타입..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악가로, 세로 ≤ 100출력: 치즈가 모두 녹는데 걸리는 시간, 모두 녹기 직전에 남아있던 치즈 칸 개수✏️ 문제풀이시뮬레이션(구현) + DFS/BFS 문제로, 문제가 요구하는대로 그대로 구현하면 됩니다.하지만, 바로 코딩에 들어가지 마시고 순서대로 어떤 절차를 밟을지 간단하게나마 손코딩을 한 후 진행합시다.`while(치즈가 남아있는 동안)` - 전체 칸을 순회하며 치즈가 있는지 확인하는 함수가 필요합니다.`(0, 0)` 공기를 시작점으로 DFS 또는 BFS를 돌려서 치즈를 만나면 '녹았다' 표시를 합니다.`(0, 0)`은 무조건 공기입니다. 문제에 '가장자리에는 치즈가 없다'고 나와있기 때문입니다.이 과정이 끝나면, 공기와 맞닿은 치즈는 '녹았다' 표시가..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악세로 크기 N, 가로 크기 M (3 ≤ N, M ≤ 8)0은 빈 칸, 1은 벽, 2는 바이러스2 ≤ 바이러스 개수 ≤ 103 ≤ 빈 칸출력: 안전영역의 최대크기✏️ 문제풀이안전영역의 최대 크기를 구하기 위해서는 주어진 빈칸들 중 3칸을 선택할 수 있는 모든 경우의 수를 따져봐야 합니다.연구실 크기는 최대 8 × 8 = 64칸입니다.최악의 경우, 벽이 하나도 없고 바이러스가 2개 있다면, 3개의 벽을 세울 수 있는 경우는 62 × 61 × 60 = 약 22만충분히 모든 경우의 수를 계산할 수 있습니다. 로직은 다음과 같습니다.선택한 빈칸 3칸을 `1`로 만들어 벽을 세웁니다.DFS 또는 BFS를 이용해서 시뮬레이션을 돌립니다. 각 바이러스마다 갈 수 있는 모..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악100글자보다 짧은 문장 입력문장 입력 : `getline(cin, str)`온점 "." 하나 입력될 때까지 입력 반복균형 문자열이면 "yes", 아니면 "no"✏️ 문제풀이9012 :: 괄호 문제의 진화버전입니다.역시 괄호 / 짝 찾기 문제이므로 스택을 사용한다는 것을 떠올려야합니다. 소괄호는 소괄호끼리, 대괄호는 대괄호끼리 짝지어집니다.스택이 비어있거나, 여는 괄호 (`(` 또는 `[`)를 만났다면 스택에 `push()`하며 나아갑니다.닫는 괄호(`)` 또는 `]`)를 만났다면, 스택 가장 위에 있는 것과 짝을 이루는지 확인합니다.짝을 이루지 않는다면 더 볼 것도 없습니다. 해당 문장은 균형 문자열이 아닙니다.📝 코드#include using name..

❔문제 🔗문제링크🔄 문제 및 입출력 조건 파악여러개의 테스트케이스 T입력: 2 ≤ 각 괄호문자열 길이 ≤ 50출력: 괄호문자열이면 "YES", 아니면 "NO"✏️ 문제풀이괄호, 짝을 찾는다 같은 표현은 '스택'을 생각합시다. 현재 스택이 비어있거나, 여는 소괄호(`(`)를 만나면 스택에 `push()` 하면서 나아갑니다.닫는 소괄호를 만나면스택 가장 위에 있는 괄호가 여는 소괄호(`(`)인지 확인합니다.맞다면, `pop()` 하고, 아니라면, 해당 문자열은 괄호 문자열이 아닙니다.문자열 끝까지 순회했는데, 스택이 비어있지 않고 무언가 남아있다면해당 문자열은 괄호 문자열이 아닙니다.📝 코드#include using namespace std;int main() { ios::sync_with_stdio(..