skive 🌿

[문제]백준 17265 - 나의 인생에는 수학과 함께 n x n 크기의 격자판에 숫자와 연산자(+, -, *)가 섞여 있다.(0,0)에서 시작하여 오른쪽이나 아래쪽으로만 이동할 수 있다.이동 경로를 따라 수식을 계산했을 때 최댓값과 최솟값을 구하는 문제. [문제 풀이] DFS(깊이 우선 탐색) 를 이용해 모든 가능한 경로를 탐색한다.숫자 칸에 도착하면 현재까지의 값과 직전 연산자를 이용해 새로운 값을 계산한다.연산자 칸에 도착하면 현재 연산자를 갱신한다.(n-1, n-1) 도착 지점에 도착하면 지금까지 계산된 결과로 최댓값과 최솟값을 갱신한다.연산자에 따라 계산하는 함수 cal()을 명확히 분리해서 가독성을 높였다. 첫 시작인 (0,0) 좌표는 항상 숫자라서 DFS를 호출할 때 숫자값만 cur로 ..

[문제]백준 28069 - 김밥천국의 계단 시작점은 0번 계단, 목표는 n번 계단에 정확히 k번 이하의 이동으로 도달하는 것 이동 방식은 두 가지:현재 계단 +1현재 계단 + (현재 계단 / 2)목표: 정확히 k번 이하의 이동으로 n번 계단에 도달할 수 있으면 "minigimbob", 아니면 "water" 출력 int nx1 = cur + 1;int nx2 = cur + (cur / 2); [문제 풀이] 이 문제는 가중치가 모두 1인 그래프의 최단거리 문제와 같으므로 BFS가 적합하다고 생각했다. 방문 배열 visited에 0번 계단에서 x번 계단까지 도달하는 최소 이동 횟수를 저장하고, BFS 탐색 도중 n번 계단에 도달했을 때 visited[n] - 1 BFS에서는 다음 상태를 아래와 같이..

[문제]백준 27971 - 강아지는 많을수록 좋다 [문제 풀이]이 문제는 특정 상태(강아지 수)에서 시작하여 A 또는 B를 더하는 식으로 상태를 확장해 나가는 최단 거리 탐색 문제로 볼 수 있다. 따라서 BFS(너비 우선 탐색)을 활용하여 직관적으로 구현해봤다. 1. q.push({0, 0}): 강아지 수 0마리부터 시작, 행동 횟수도 02. visited[]: 중복 방문 방지3. arr[]: 입력으로 주어진 금지 구간을 마킹. arr[i] == 1이면 해당 수의 강아지를 만들면 안 됨4. next > 100000: 문제 제한 범위를 초과하면 무시. BFS 특성상 가장 먼저 도착한 경로가 곧 최소 행동 횟수가 된다. [소스 코드]#include using namespace std;int n, m, ..

[문제]백준 18126 - 너구리 구구 노드 수 n (최대 5,000개)n-1개의 간선 (트리 구조)각 간선에는 거리 가중치가 있음임의의 두 정점 사이의 최대 거리(트리의 지름)를 출력 [문제 풀이] 1. DFS 탐색으로 1번 노드에서 출발하여 각 노드를 탐색2. cnt를 누적 거리로 전달하면서 res = max(res, cnt)로 최대값 갱신3. 양방향 간선이므로 from → to, to → from 모두 저장* 주의할 점: 자료형 오버플로우 (결과값을 long long으로 해야 한다) - 풀이 과정에서 새로 배운 것 : 구조 분해 선언(structured binding)for (auto [next, d] : a[from]) { ...} 위 문법은 사실상 아래와 같은 동작을 수행한다. fo..

[문제]백준 17271 - 리그 오브 레전설(Small) 스킬을 시전해 정확히 N초를 채우는 모든 경우의 수를 구하는 문제다. 사용할 수 있는 스킬은 두 가지:A 스킬: 1초 소모B 스킬: M초 소모각 스킬은 무제한 사용 가능하고, 결과는 1,000,000,007로 나눈 나머지를 출력해야 한다. [문제 풀이]사용한 알고리즘: 동적 계획법 (DP)처음에는 모든 가능한 스킬 조합을 DFS로 완전탐색하는 방식이 떠올랐지만 N이 최대 10,000이기 때문에, 단순 DFS는 중복 호출이 많아지기 때문에 시간 초과가 발생할 것 같아서 DP를 이용했다. 단순 DFS는 시간 초과지만, 메모이제이션을 적용한 DFS는 사실상 Top-Down DP로 문제를 해결할 수 있다. dp[ i ]: 총 i초를 정확히 채우는 ..

[문제]백준 17484 - 진우의 달 여행 로봇은 맨 위 줄의 어느 칸에서든 시작 가능매 턴마다 ↙, ↓, ↘ 방향 중 하나로 이동단, 같은 방향을 연속해서 사용할 수 없음n행에 도달할 때까지의 최소 연료 소비량을 구해야 함 [문제 풀이]DFS로 모든 경로를 탐색하고 있었지만, "같은 방향을 연속해서 이동할 수 없다"는 제약 조건을 고려하지 못함.이로 인해 조건을 위반한 경로도 포함되어 정답보다 더 작은 잘못된 값이 결과로 출력될 수 있음.같은 방향을 연속해서 쓰지 않도록 prev_dir이라는 인자를 추가해 이전 방향과 비교 DFS는 중복 경로가 많아 효율이 떨어짐.그래서 dp[y][x][dir] = y행 x열에 dir 방향으로 도착했을 때 최소 연료로 정의하면 중복 경로 제거 + 빠른 연산 가능...

[문제]백준 2156 - 포도주 시식 포도주 잔 n개가 일렬로 놓여 있고, 각 잔마다 포도주의 양이 주어진다.포도주는 연속으로 3잔을 마실 수 없다.마실 수 있는 포도주의 최대 양을 구하라. [문제 풀이]접근 방법: Dynamic Programmingdp[i]를 i번째 잔까지 고려했을 때 마실 수 있는 최대 포도주 양이라고 정의한다. i번째 포도주의 양은 a[i]이다.선택지는 아래 세 가지 중 하나이다:현재 잔을 마시지 않음 → dp[i - 1]현재 잔만 마심 (이전 잔은 마시지 않음) → dp[i - 2] + a[i]이전 잔과 현재 잔 둘 다 마심 (i-3번째는 마시지 않아야 함) → dp[i - 3] + a[i - 1] + a[i] 점화식: dp[0] = a[0];dp[1] = a[0] + ..

[문제]백준 16401 - 과자 나눠주기 조카 M명에게 과자 N개를 나누어 주려고 한다. 각 조카는 동일한 길이의 과자 한 개만 받는다.과자들은 자를 수 있고, 조카의 수보다 과자의 개수가 적을 수도 있다.모든 조카에게 동일한 길이의 과자를 나눠주되, 그 길이를 최대로 하는 것이 목표다. [문제 풀이]사용한 알고리즘: 이분 탐색 (Binary Search)이 문제는 '조건을 만족하는 최대값'을 찾는 Parametric Search(파라메트릭 서치) 문제다.이분 탐색을 통해 나눠줄 수 있는 최대 길이를 찾아야 한다. [소스 코드]#include using namespace std;int m, n, res, l, r, mid, mx, cnt;vector v;int main() { cin >> m >> ..

[문제]백준 1783 - 병든 나이트 체스판의 크기가 주어진다: n x m총 4가지 이동 방법만 가능하다:(−2, +1), (−1, +2), (+1, +2), (+2, +1)단, 이동 횟수가 4번 이상이면 4가지 방향 모두 한 번씩 사용해야 한다.나이트는 최대한 많은 칸을 방문하려고 한다.방문할 수 있는 칸의 최댓값을 구하는 문제  [문제 풀이]이동 제약을 기반으로 예외를 처리했다. 이동 방식이 일반적인 나이트와 달리 4가지로 한정되고, 위로는 움직일 수 없기 때문에 행(n)의 값이 매우 중요하다.n == 1: 시작점만 방문 가능 → 정답은 1n == 2: 이동 가능한 형태가 제한되어 (+1, +2) 또는 (-1, +2)만 가능. 즉, 오른쪽으로 두 칸, 위아래로 한 칸.2칸을 오른쪽으로 가면 하나 이동..

[문제]백준 2437 - 저울  하나의 양의 정수 무게를 측정할 수 있는 여러 개의 추가 주어진다. 이때, 주어진 추들로 측정할 수 없는 가장 작은 양의 정수를 구하는 문제다. 예를 들어, 추들이 {1, 1, 2, 5}일 때, 10까지는 만들 수 있지만 11은 만들 수 없다. 이처럼 누락된 최소의 무게를 찾는 게 핵심이다.   [문제 풀이]이 문제는 그리디 알고리즘(Greedy Algorithm)으로 해결할 수 있다. 가장 작은 무게부터 만들 수 있는지 차례로 확인하면서, 측정 가능한 무게의 범위를 확장하였다. 입력받은 추 무게들을 정렬한다.res 를 1로 초기화한다. res 는 지금까지 만들 수 있는 무게 범위 [1, res]를 의미한다.추의 무게를 하나씩 보며,만약 현재 추의 무게가 res보다 크면,..