문제: 구간 합 구하기 (백준 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..

문제: 트리 (백준 1068번)문제 분석루트 없는 트리가 주어질 때, 특정 노드를 삭제하면 남은 트리에서 리프 노드 개수를 구하는 문제이다.입력 처리graph[i]: 각 노드의 자식들을 저장하는 인접 리스트.depth[i]: 각 노드가 몇 개의 자식을 가지는지 저장.삭제할 노드(target) 반영부모 노드에서 삭제할 노드의 연결을 끊음 (자식 수 감소).BFS를 활용하여 삭제할 노드 및 해당 서브트리를 모두 제거 (depth 값을 -1로 설정).리프 노드 개수 계산depth[i] == 0인 노드 개수를 세어 출력.전체 코드#include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> ..

문제: 스타트링크 (백준 5014번)문제 분석스타트링크라는 고층 건물에는 총 f층이 있고, 현재 s층에 있는 사람이 g층으로 가야 한다. 엘리베이터에는 위로 u층, 아래로 d층만 이동할 수 있는 버튼이 있다. 주어진 조건 내에서 최소한으로 버튼을 눌러 목표 층에 도착해야 한다. 만약 도착할 수 없다면 "use the stairs"를 출력해야 한다.핵심 아이디어BFS 큐 초기화현재 층(s)을 큐에 삽입하고, visited 벡터를 활용해 방문한 층과 해당 층까지의 버튼 누른 횟수를 기록했다.층 이동 로직큐에서 노드를 꺼낸 뒤:위로 이동: 현재 층 + u가 건물의 총 층수 f를 넘지 않으면서 방문한 적이 없다면 큐에 추가.아래로 이동: 현재 층 - d가 1층 이상이면서 방문한 적이 없다면 큐에 추가.종료 조건..

문제: 동물원(백준 1309번)문제 분석3칸짜리 우리에 사자를 배치하는 문제로, 각 줄에 사자를 배치하는 경우의 수를 구하는 DP 문제다.조건: 같은 줄에 사자를 가로로 붙어있게 배치할 수 없다.점화식 도출:dp[i] = i번째 줄까지 사자를 배치하는 경우의 수세 가지 경우의 수:사자를 배치하지 않는 경우왼쪽 칸에 사자를 배치하는 경우오른쪽 칸에 사자를 배치하는 경우이 조건을 고려하면 점화식은 다음과 같다.$dp[i]=(dp[i−1]×2)+dp[i−2]dp[i] = (dp[i-1] \times 2) + dp[i-2]$dp[i-1] × 2: 이전 줄에서의 모든 배치 경우에 대해, 이번 줄에 왼쪽 또는 오른쪽에 사자를 추가하는 경우dp[i-2]: 두 줄 전의 배치에 이번 줄을 빈 상태로 두는 경우 (붙어있을..

문제: 가운데를 말해요(백준 1655번)문제 분석입력이 주어질때마다 중간값을 출력하면 되는 간단명료한 문제이다.본인이 생각한 방법은 maxHeap과 minHeap의 top을 중간값으로 보고 두 우선순위큐의 size 밸런스를 맞추는 것이다.오름차순으로 정렬된 배열을 절반으로 나눠서 앞부분을 maxHeap 뒷부분을 minHeap으로 본다고 생각하면 쉽다. 우선 입력이 주어졌을때 4가지 분기가 있다.1. 빈 큐가 있을때2. 주어진 숫자가 maxHeap의 top보다 작거나 같을때3. 주어진 숫자가 maxHeap의 top보다 크고 minHeap의 top보다 작을때4. 주어진 숫자가 minHeap의 top보다 크거나 같을때 두 큐가 모두 비어있으면 maxHeap에 입력값을 넣고 minHeap만 비어있다면 maxHe..

문제 링크 (백준 1004번)문제 분석어린 왕자가 출발점에서 도착점까지 이동하면서 거쳐야 하는 최소한의 행성계 진입/이탈 횟수를 구하는 문제다.행성계는 원으로 표현되며, 출발점과 도착점, 그리고 행성계의 중심과 반지름이 주어진다.문제의 조건에 따라 행성계 경계는 서로 교차하거나 맞닿지 않고, 출발점과 도착점이 경계에 걸쳐지는 경우도 없다.문제 로직행성계 내부 판정두 점 사이의 거리를 계산해서 해당 점이 행성계 내부에 있는지 확인진입/이탈 횟수 계산출발점과 도착점이 특정 행성계 내부/외부에 속하는 관계가 다를 때만 진입/이탈 횟수를 증가시킨다.이 과정을 통해 최소 진입/이탈 횟수를 구한다.전체 흐름각 테스트 케이스마다 모든 행성계를 검사하면서 위 조건을 만족하는 경우를 카운트한다.거리 계산float Dis..

문제: 합분해 (백준 2225번)문제 분석0부터 $N$까지의 정수 $K$개를 더해서 그 합이 $N$이 되는 경우의 수를 구하는 문제다.이번 문제도 이전 문제와 비슷하게 지문 자체가 참 짧고 간결하고 DP를 사용한 문제이므로 알고리즘도 간결하다.다이나믹 프로그래밍을 이용한 해결 방법$dp[i][j]$를 $j$를 만들기 위해 $i$개의 숫자를 사용하는 경우의 수로 정의한다.초기화: $dp[1][j]$는 1로 초기화한다. (0부터 $j$까지의 합을 1개의 숫자로 나타낼 수 있는 경우의 수는 1이다)상태 전이: $dp[i][j]$ 는 $dp[i-1][k]$ 의 합이다. 여기서 $k$는 0부터 $j$까지의 값이다. 각 단계에서 현재 숫자를 포함하여 만들 수 있는 경우의 수를 누적한다.점화식$dp[i][j] = \..

문제: 행렬 제곱(백준 10830번)문제 분석$N \times N$ 크기의 행렬을 $B$번 제곱한 결과를 출력하는 문제이다.보통 이런 지문 자체가 간단한 문제들은 입력 범위가 특정 알고리즘을 사용해야 시간 초과가 나지 않도록 설계되어 있다. 이번 문제 역시 단순히 행렬 제곱을 반복적으로 계산하면 $O(N^3 \times B)$의 시간 복잡도를 가지므로 1000억 번의 연산이 필요하다. 따라서 시간 복잡도를 $O(\log B \times N^3)$ 수준으로 줄일 수 있는 알고리즘이 필요하다.거듭 제곱을 이용한 행렬 제곱 알고리즘거듭 제곱을 활용하면, 행렬을 효율적으로 제곱할 수 있다.행렬 $M$을 $B$번 제곱하는 과정을 다음과 같이 분할 정복 방식으로 처리한다.$B = 0$일 경우, 단위 행렬을 반환한다..

문제: 신입 사원(백준 1946번)문제 분석이 코드는 신입 사원 선발 문제를 해결하기 위한 코드다.주어진 t개의 테스트 케이스에 대해 각 지원자의 서류 성적과 면접 성적이 주어진다.이 중 두 성적 중 하나라도 다른 지원자보다 나은 경우에만 선발한다.즉, 어떤 지원자가 다른 지원자들에 의해 완전히 밀리지 않는 경우를 찾는 문제다.알고리즘 설명입력받기각 테스트 케이스마다 n명의 지원자 정보(서류 성적, 면접 성적)를 입력받는다.정렬서류 성적 기준으로 오름차순 정렬한다.이로 인해 서류 성적이 앞서는 지원자만 비교하면 된다.최소 면접 성적 추적서류 성적이 낮은 순서로 순회하면서,이전까지의 최소 면접 성적(minVal)보다 현재 지원자의 면접 성적이 더 낮다면,해당 지원자는 선발 가능하다. 이 경우, answer..