문제: 스타트링크 (백준 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..

문제: 후위 표기식(백준 1918번)문제 분석이 문제는 주어진 중위 표기식을 스택을 사용하여 후위 표기식으로 변환하는 문제다.후위 표기식은 연산자를 나중에 쓰는 표기법으로, 계산 순서를 명확히 나타낼 수 있다는 장점이 있다.후위 표기식중위 표기식은 연산자가 피연산자 사이에 위치한다.예: A + B후위 표기식은 연산자가 피연산자 뒤에 위치한다.예: AB+후위 표기식의 특징은 괄호 없이도 연산 우선순위를 명확히 알 수 있다는 점이다.예를 들어, A + B * C를 후위 표기식으로 바꾸면 ABC*+가 된다.알고리즘피연산자는 바로 출력한다.(문자열에서 알파벳이 나오면 바로 cout으로 출력)연산자는 스택에 넣는다.단, 스택에 있는 연산자와 우선순위를 비교해,스택의 연산자가 현재 연산자보다 우선순위가 높거나 같으..

문제: 음악 프로그램 (백준 16724번)문제 분석이번 문제는 주어진 그래프에서 사이클의 개수를 구하는 문제이다.입력 형식을 보면 지도 밖으로 나가는 방향의 입력은 주어지지 않기 때문에 결국 화살표들은 사이클을 최소 1개 이상 무조건 생성을 하게 되어있다.DFS를 사용한 사이클 개수 찾기사이클 개수를 구하기 위해 DFS를 활용한다.이때, 사이클 판별을 위해 visited와 finish 배열을 사용한다.visited[y][x]는 현재 칸이 방문되었는지 여부를 저장한다.finish[y][x]는 현재 칸에 대한 탐색이 끝났는지를 나타낸다.DFS를 통해 현재 칸에서 다음 칸으로 이동하면서, 다음과 같은 조건으로 사이클을 판별한다.다음 칸이 방문된 적이 있지만 탐색이 끝나지 않은 칸이라면, 이는 사이클이 형성되었..

문제: 음악 프로그램 (백준 2623번)문제 분석이 문제는 사이클 탐색과 위상 정렬을 결합한 문제이다.지문은 길지만, 문제의 핵심은 주어진 조건에 따라 유방향 그래프를 만들고, 그 그래프에서 사이클이 있는지 확인한 뒤, 사이클이 없다면 위상 정렬을 수행하는 것이다.해결 접근사이클 탐색각 가수 간의 선후 관계를 유방향 그래프로 표현한다.사이클이 있으면 그 그래프는 위상 정렬이 불가능하다.DFS를 사용하여 그래프에서 사이클을 탐지한다.위상 정렬사이클이 없으면 위상 정렬을 통해 가수들의 순서를 결정한다.위상 정렬은 진입 차수가 0인 노드를 먼저 처리하며, 이를 통해 순서를 구한다.우선순위 큐위상 정렬을 수행하는 중에 여러 노드가 진입 차수가 0일 때, 우선순위 큐를 사용하여 가장 작은 번호부터 처리하도록 한다..