Algorithm

문제: 퇴사 2 (백준 15486번)문제 분석입력: $N$일 동안 상담을 진행할 수 있으며,각 상담은 걸리는 기간 $T_i$와 얻을 수 있는 금액 $P_i$를 가진다.목표: 상담을 적절히 선택하여 얻을 수 있는 최대 수익을 계산하는 문제.조건: 상담이 끝나는 날을 초과하면 진행할 수 없다.해결 방법: 동적 계획법 (DP)이 문제는 배낭 문제 (Knapsack Problem)와 유사하다.각 날짜별로 상담을 선택할지 말지를 결정해야 하며, 최적의 선택을 누적하면서 해결해야 한다.DP 테이블 정의dp[i]: i번째 날까지 얻을 수 있는 최대 수익즉, i일이 끝났을 때 가능한 최대 이익을 저장한다.점화식현재까지의 최대 수익 유지$$dp[i]=max(dp[i],dp[i-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부터 최대값까지 순회하면서,해당 수가 입력에 포함된 경우,그 수의 배수들을 탐색하여,만약 배수가 입력에 포함되어 있다면,배수인 수에서는 점수를 감소, 기준 수에서는 점수를 증가시킨다.최..

문제: 카드 합체 놀이 (백준 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: 검사할 행 ..