C++

문제: 가장 큰 정사각형 (백준 1915번)문제 분석주어진 $(N\times M)$ 크기의 이진 행렬(0과 1로 구성된)에서,1로만 이루어진 정사각형 영역 중 가장 큰 정사각형의 넓이를 구하는 문제이다.즉, 행렬에서 연속된 1들로 구성된 정사각형의 최대 넓이를 구하면 된다.해결 방법: 동적 계획법 (DP)문제를 효율적으로 풀기 위해 동적 계획법(DP)을 사용할 수 있다.여기서 핵심 아이디어는,dp[i][j]를 (i, j)를 우측 하단 모서리로 하는 가장 큰 정사각형의 한 변의 길이로 정의하는 것이다.설명:(i, j) 위치에서 정사각형을 확장하기 위해서는 바로 위, 왼쪽, 그리고 대각선 왼쪽 위의 위치에 있는 정사각형 크기가 모두 일정 이상이어야 한다.이 세 방향 중 가장 작은 값에 1을 더하면 (i, ..

문제: 좋다 (백준 1253번)문제 분석이 문제는 주어진 수열에서 "좋은 수"의 개수를 찾는 문제이다.정의:수열의 한 원소가 다른 두 원소의 합으로 표현될 수 있다면, 그 원소를 "좋은 수"라고 한다.제한:한 원소는 자기 자신을 이용할 수 없다.같은 원소의 인덱스가 겹치면 안 된다.문제의 핵심은 모든 가능한 두 원소의 합을 고려해, 해당 합이 수열 내의 다른 원소와 일치하는지 확인하는 것이다.해결 방법자료구조 준비:벡터 v: 입력받은 수들을 저장.딕셔너리 dict: 각 숫자에 대해 (인덱스, 상태)를 저장하는 unordered_map 사용.키: 해당 숫자값: 해당 숫자가 등장하는 인덱스와, 아직 "좋은 수" 후보로 남아있는지를 나타내는 불리언 값→ true: 아직 후보→ false: 이미 한 번 사용하여..

문제: 신기한 소수 (백준 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 배열에 저장한다.특정 건물의 최소 건설 시간은, 해당 건물에 선행하는 모든 건물들의 건설 시간 중 최대값에 현재 건물의 건설 시간을 더한 값이다.(즉, 선행 건물 중 가장 늦게 완공되는 시점을 고려하여 건물을 지어야 한다...