문제: 신기한 소수 (백준 2023번)문제 분석문제 개요:길이가 nn인 신기한 소수를 찾는 문제로,신기한 소수란 왼쪽부터 한 자리씩 늘려가며 만들어지는 모든 접두사가 소수인 수이다.예를 들어, 73317331의 경우, 77, 7373, 733733, 73317331 모두 소수여야 한다.접근 방법:백트래킹(Backtracking) 사용:재귀를 통해 자릿수를 늘려가며 후보 숫자를 구성한다.각 단계마다 현재까지 구성된 숫자가 소수인지 판별하고, 소수가 아니면 더 이상 진행하지 않는다.소수 판별 함수:입력된 수가 소수인지 확인하기 위해 22부터 $\sqrt{num}$ 까지의 나눗셈으로 판별한다.문자열 활용:숫자를 문자열로 조작한 후, stoi 함수를 통해 정수로 변환하여 소수 여부를 확인한다.전체 코드#incl..

문제: 빗물 (백준 14719번)문제 분석문제 개요:주어진 높이 hh 와 너비 ww 의 2차원 공간에서, 블록이 쌓인 형태가 주어진다.이때 빗물이 고일 수 있는 칸의 개수를 구하는 문제이다.핵심 개념:특정 위치에 빗물이 고이려면 왼쪽과 오른쪽에 블록이 있어야 한다.각 칸에서 왼쪽과 오른쪽에 블록이 있는지 확인하는 방식으로 문제를 해결코드 설명#include using namespace std;template bool Check(Iterator start, Iterator end){ for (; start != end; ++start) { if (*start) return true; } return false;}int main(){ ios::sync_with_stdi..

문제: 수 나누기 게임 (백준 27172번)문제 분석문제 개요:n개의 정수가 주어지고, 각 정수에 대해 “나누기 게임” 규칙에 따라 점수를 계산해야 한다.만약 정수 $a$가 주어졌을 때, $a$의 배수 중 입력에 포함된 정수들이 있다면,$a$는 그 배수들을 "나눌 수 있음"으로 처리하여 점수를 얻고,반대로, $a$가 다른 수의 배수라면 점수를 잃는다.접근 아이디어:입력 저장 및 최대값 확인:입력받은 정수들을 벡터에 저장하고,존재하는 수들을 빠르게 확인하기 위해 해시맵(unordered_map)에 기록한다.배수 관계 계산:1부터 최대값까지 순회하면서,해당 수가 입력에 포함된 경우,그 수의 배수들을 탐색하여,만약 배수가 입력에 포함되어 있다면,배수인 수에서는 점수를 감소, 기준 수에서는 점수를 증가시킨다.최..

문제: 물건 팔기 (백준 1487번)문제 분석문제 개요:주어진 데이터는 각 물건의 가격과 그에 해당하는 판매 비용들이다. 문제의 목표는 특정 기준 가격 $p$를 정할 때 최대 이익을 주는 $p$의 값을 구하는 것이다. 단, 이익이 같은 경우 더 낮은 $p$를 선택해야 한다.접근 방법:데이터 구조 선택:각 물건의 가격을 키로, 해당 가격에 해당하는 비용 리스트를 값으로 저장하기 위해 unordered_map>를 사용한다.이익 계산:모든 가격에 대해, 기준 가격 $p$를 정하고, 모든 물건들을 순회하면서 다음과 같이 이익을 계산한다:물건의 가격이 $p$ 이상이면 이익 없음물건의 가격이 $p$ 미만이면 $p - \text{물건 가격} - \text{판매 비용}$만큼의 이익 발생최적의 기준 가격 선택:계산된 이..

문제: 카드 합체 놀이 (백준 15903번)문제 분석N장의 카드가 있고, 각 카드에 적힌 숫자가 주어진다.카드 합체 놀이에서는, 매번 두 장의 카드를 골라 그 합을 계산한 뒤, 두 카드 모두 그 합으로 교체한다.이를 총 M번 반복한 후, 모든 카드에 적힌 숫자의 합을 구하는 문제이다.핵심 포인트:최소 힙 활용:매 번 가장 작은 두 수를 선택하면, 앞으로의 합산 결과가 최소가 되어 최종 결과에 큰 영향을 미치게 된다.그래서 최소 힙(우선순위 큐)를 사용하여 O(M log N)의 효율적인 계산을 할 수 있다.알고리즘 흐름:모든 카드 값을 최소 힙에 넣는다.M번 동안, 힙에서 가장 작은 두 수를 꺼내 합을 구하고, 그 합을 다시 힙에 두 번 넣는다.모든 연산이 끝나면 힙에 남은 모든 카드의 값을 합산한다.전체..

문제: 귀찮아 (SIB) (백준 14929번)문제 분석주어진 n개의 정수에 대해, 모든 서로 다른 두 수의 곱의 합을 구하는 문제이다.즉,$\text{result} = \sum_{1 \leq i 직접 모든 쌍을 계산하면 O(n²) 시간 복잡도가 발생하지만, n의 범위가 클 경우 시간 초과가 날 수 있다.해결 방법수학적 아이디어:두 수의 곱의 합은 다음 식으로 변형할 수 있다.$\left(\sum_{i=1}^{n} a_i\right)^2 = \sum_{i=1}^{n} a_i^2 + 2\sum_{1 \leq i 따라서,$\sum_{1 \leq i 이 식을 이용하면 O(n) 시간 내에 결과를 구할 수 있다.전체 코드#include using namespace std;int main() { ios::syn..

문제: 수 묶기 (백준 1744번)문제 분석주어진 N개의 정수에 대해, 덧셈과 곱셈 연산을 적절히 활용하여 최종 합을 최대화하는 문제이다.핵심 포인트:양수의 경우 1보다 큰 수들은 곱하는 것이 더 큰 효과를 낼 수 있다.음수와 0의 경우, 두 개씩 묶어 곱하면 음수의 부호를 상쇄하거나 0으로 만들 수 있다.1은 곱셈보다 덧셈하는 것이 유리하다.문제 해결의 관건은 입력 배열을 정렬한 후, 왼쪽(음수 및 0)과 오른쪽(양수)에서 각각 최적의 조합을 선택하는 것이다.해결 방법정렬: 배열을 오름차순으로 정렬한다.양쪽 후보 고려:왼쪽 부분에서는 인접한 두 수의 곱과 개별 값 중 큰 값을 선택한다.오른쪽 부분에서는 인접한 두 수의 곱과 개별 값 중 큰 값을 선택한다.만약 남은 요소가 2개이면, 곱과 덧셈 중 더 큰..

문제: ACM Craft (백준 1005번)문제 분석문제 개요:각 건물마다 건설에 걸리는 시간이 주어지고, 특정 건물을 짓기 위해 먼저 지어져야 하는 건물들의 관계(선행 조건)가 주어진다.목표는 주어진 목표 건물 W를 짓기 위한 최소 건설 시간을 구하는 것이다. 핵심 아이디어:위상 정렬:선행 조건을 고려한 건설 순서를 결정하기 위해 위상 정렬을 사용한다.indegree(진입 차수)를 활용해 선행 조건이 없는 건물부터 처리한다.DP (동적 계획법):각 건물을 짓기 위한 최소 시간을 dp 배열에 저장한다.특정 건물의 최소 건설 시간은, 해당 건물에 선행하는 모든 건물들의 건설 시간 중 최대값에 현재 건물의 건설 시간을 더한 값이다.(즉, 선행 건물 중 가장 늦게 완공되는 시점을 고려하여 건물을 지어야 한다...

문제: 경사로 (백준 14890번)문제 분석n×n 크기의 지도에서 각 칸의 높이가 주어지고, 경사로를 설치할 수 있는 조건에 맞춰 길(행 또는 열) 중 지나갈 수 있는 길의 개수를 구하는 빡구현 문제이다.높이 차이가 2 이상이면 해당 길은 지나갈 수 없다.높이 차이가 1일 경우,오르막: 바로 이전 칸들이 l칸 이상 연속해서 동일한 높이여야 경사로를 설치할 수 있다.내리막: 앞으로 l칸이 모두 현재 칸과 같은 낮은 높이여야 하며, 해당 칸에 이미 경사로가 설치되지 않아야 한다.경사로는 한 번만 설치 가능하다.해결 방법함수 설계:checkRow 함수는 주어진 행 또는 열이 조건에 맞게 경사로를 설치할 수 있는지를 판단한다.매개변수:vector>& v: 지도 정보s, e: 시작과 끝 인덱스row: 검사할 행 ..

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