문제: 효율적인 해킹 (백준 1325번)문제 분석N개의 컴퓨터와 M개의 신뢰 관계가 주어질 때, 한 컴퓨터를 해킹하면 그 컴퓨터를 신뢰하는 다른 컴퓨터들도 해킹할 수 있다.각 컴퓨터를 시작점으로 하여 해킹할 수 있는 컴퓨터의 수(직접 및 간접)를 구한 뒤, 가장 많은 컴퓨터를 해킹할 수 있는 노드를 출력하는 문제이다. 접근입력으로 주어지는 (a, b) 관계는 "a가 b를 신뢰한다"는 의미이므로,b를 해킹하면 a도 해킹할 수 있다.이를 위해, 각 노드에 대해 역방향 그래프를 구성하여, 해당 노드에서 출발해 도달할 수 있는 노드의 수를 구하면 된다.해결 방법그래프 구성:입력 (a, b)를 받으면, graph[b]에 a를 추가한다.→ 이렇게 하면 b를 해킹했을 때, a로 확산되는 효과를 모사할 수 있다.BFS..

문제: 1로 만들기 2 (백준 12852번)문제 분석주어진 정수 x를 아래 연산 세 가지를 사용하여 1로 만드는 최소 연산 횟수를 구하고, 그 과정에서 거친 수열(경로)도 출력하는 문제이다.가능한 연산은:x가 3으로 나누어 떨어지면 3으로 나눈다.x가 2로 나누어 떨어지면 2로 나눈다.x에서 1을 뺀다.BFS(너비 우선 탐색)를 활용하면 최단(최소 연산) 경로를 자연스럽게 찾을 수 있으며, 각 단계에서 이전 상태(부모 노드)를 기록하면 경로 재구성이 가능하다.해결 방법BFS 탐색을 통한 경로 찾기시작점: 입력받은 x를 시작 노드로 한다.방문 기록: visited 배열(혹은 벡터)을 사용해 각 숫자에 도달한 직전 노드를 저장한다.연산 적용: 현재 노드에 대해,만약 2로 나누어 떨어진다면 node/2를,만약..

문제: 골드바흐의 추측 (백준 6588번)문제 분석골드바흐의 추측은 "4 이상인 모든 짝수는 두 개의 소수의 합으로 나타낼 수 있다" 는 정수론의 가설이다.이 문제에서는 n이 주어졌을 때, 두 소수의 합으로 표현하는 방법을 찾아 출력하는 것이 목표이다.에라토스테네스의 체를 이용한 소수 판별100만까지의 숫자에서 소수를 빠르게 판별하기 위해 에라토스테네스의 체를 사용한다.prime[i]가 true이면 소수, false이면 합성수로 설정한다.두 포인터를 활용한 탐색left는 2부터 시작하고, right는 n부터 시작한다.두 포인터가 가리키는 값이 소수인지 확인하면서,합이 n보다 크다면 right를 줄인다.합이 n보다 작다면 left를 증가시킨다.합이 n이 되는 순간 두 수를 출력한다.전체 코드#include..

문제: 맥주 마시면서 걸어가기 (백준 9205번)문제 분석편의점에서 맥주를 최대 20병까지 들고 이동할 수 있으며, 50m마다 한 병을 마셔야 한다. 따라서 한 번에 이동할 수 있는 최대 거리는 1000m이다.출발지에서 도착지까지 이동 가능한지를 판단하는 문제로, 노드를 방문하면서 연결된 곳을 탐색하는 BFS를 사용하면 해결할 수 있다.해결 방법각 장소(출발지, 편의점, 도착지)를 노드로 보고, 이동 가능한 거리(1000m 이하)라면 간선을 연결해 그래프를 구성한다.이후 BFS를 이용해 출발지에서 도착지까지 도달할 수 있는지 탐색한다.노드 정의Node 구조체를 정의해 위치 (x, y)와 간선 정보를 저장한다.operator- 연산자를 오버로딩하여 두 지점 사이의 맨해튼 거리(절댓값 거리)를 계산할 수 있..

문제: 팰린드롬? (백준 10942번)문제 분석입력으로 주어진 단어(숫자 배열)의 구간에 대해, 해당 구간이 팰린드롬인지 판별하는 문제다.n개의 수가 주어지고, m개의 질의가 주어진다. 각 질의는 시작 인덱스 S와 끝 인덱스 E가 주어지며, 이 구간이 팰린드롬이면 1, 아니면 0을 출력한다.동적 계획법(DP)을 이용해, 구간 $[i, j]$가 팰린드롬인지 판별하는 2차원 배열 dp를 구성한다. 기저 조건:한 글자짜리 구간은 항상 팰린드롬이므로, $dp[i][i] = true$인접한 두 수가 같으면, $dp[i][i+1] = true$ 점화식:$dp[i][j] = \text{true} \quad \text{if} \quad v[i] = v[j] \quad \text{and} \quad dp[i+1][j-1..

문제: 보물섬(백준 2589번)문제 분석지도 상에 있는 땅('L')과 물('W')이 주어질 때, 모든 땅에서 출발하여 가장 멀리 떨어진 땅까지의 최단 거리를 구하는 문제다. 즉, 모든 땅을 시작점으로 BFS를 수행하여 최대 이동 거리를 계산한 후 그 중 가장 큰 값을 출력하면 된다.문제의 핵심은 다음과 같다.BFS를 사용해 각 땅에서의 최대 거리를 계산맵 상에서 땅('L')에서 시작해 상하좌우로 이동하며, 각 칸까지 도달하는 최소 이동 횟수를 구한다.모든 땅을 시작점으로 탐색물('W')는 탐색 대상이 아니므로 건너뛴다.최대 이동 횟수를 찾는다.BFS역할:주어진 시작점에서 BFS를 수행하여, 도달할 수 있는 모든 땅까지의 최단 거리를 계산하고, 그 중 최대 거리를 반환한다.동작:depth 배열을 통해 각 ..

문제: 단어 수학(백준 1339번)문제 분석주어진 여러 단어에서 각 알파벳에 0부터 9까지의 숫자를 배정하여, 이 단어들이 나타내는 수들의 합을 최대화하는 문제이다.즉, 각 알파벳에 적절한 가중치를 부여해, 전체 합이 최대가 되는 배정을 찾아야 한다.알파벳 집합 생성입력받은 각 단어를 벡터 v에 저장하고, 각 단어에 포함된 알파벳을 unordered_map dict에 넣어 초기값 0으로 설정한다.Calc 함수Calc 함수는 현재 dict의 배정 상태를 기반으로, 각 단어의 값을 계산해 전체 합을 구한다.각 단어의 문자들을 해당 알파벳에 할당된 숫자로 바꾼 후 stoi를 통해 정수로 변환하고, 이를 모두 합산한다.BT 함수 (백트래킹)BT(int depth) 함수는 아직 숫자가 배정되지 않은 알파벳에 대해..

문제: 탈출 (백준 3055번)문제 분석출발 지점부터 도착 지점까지 최단 거리를 구하는 문제인데, 매 이동마다 물에 잠기는 구간이 늘어난다. 맵이 물에 잠기는 시간에 따른 시뮬레이션과, 출발 지점부터 도착 지점까지의 이동 경로를 구하는 과정을 따로 처리해야 한다. 언뜻 보면 단순한 시뮬레이션 문제로 보이지만, 실제로는 맵이 물에 잠기는 시간을 계산하는 BFS와, 출발 지점부터 도착 지점까지의 최단 거리를 구하는 BFS를 두 번 수행하면 쉽게 계산할 수 있다. 먼저 보드(board)를 입력받는다. 보드는 r×c 크기의 2차원 배열로, 각 칸에 문자('S', 'D', '*', '.', 'X')가 주어진다.'S'는 시작 지점, 'D'는 도착 지점, '*'는 물, 'X'는 바위(갈 수 없는 구역), '.'은 빈..

문제: 구간 합 구하기 (백준 2042번)이번 문제는 직접 모든 구간을 계산하면 당연히 시간초과가 발생하고 세그먼트 트리를 이용해 $O(\log N)$시간 안에 구간 합을 구하는 문제이다.우선 전역으로 세그먼트 트리와 원본 배열을 tree와 v의 이름으로 선언하고 n의 입력값에 따라 resize를 한다.MakeTreelong long MakeTree(int start, int end, int node) { if (start == end) return tree[node] = v[start]; int mid = (start + end) >> 1; int next = node 역할:MakeTree 함수는 주어진 배열 v를 기반으로 세그먼트 트리를 구축하는 역할을 한다.동작 원리:기저 조건:st..

문제: 괄호의 값 (백준 2504번)문제 분석괄호 ()와 []로 이루어진 문자열이 주어질 때, 올바른 괄호열이라면 그 값을 계산하고, 올바르지 않다면 0을 출력하는 문제이다.괄호의 구조를 유지하면서 값을 계산해야 하므로 스택 활용(가 나오면 temp를 2배, [가 나오면 3배)가 나오면 (가 있어야 하고, ]가 나오면 [가 있어야 함값을 계산하는 규칙닫는 괄호 )나 ]가 나왔을 때, 직전이 여는 괄호였다면 현재 temp 값을 sum에 더함닫는 괄호가 나왔을 때는 temp 값을 원래대로 되돌림유효성 검사스택이 비어있거나 올바르지 않은 괄호가 나오면 0 출력문자열을 끝까지 처리한 후에도 스택이 비어있지 않다면 0 출력전체 코드#include using namespace std;int main() { i..