서론이전 글에서 다익스트라 알고리즘을 다뤘다. 다익스트라는 출발 노드로부터 모든 노드까지의 최단거리를 보장하는 강력한 알고리즘이다. 그런데 게임 AI 길찾기 상황을 생각해보자.캐릭터가 맵의 좌측 끝에서 우측 끝으로 이동해야 한다. 다익스트라는 목적지에 도달하기 전에 출발점을 기준으로 사방으로 탐색을 퍼트린다. 맵 전체를 샅샅이 뒤지는 셈이다. 결국 목적지에 도달했을 때, 이미 탐색한 노드의 절반 이상이 "가지 않아도 될 방향"이었다는 것이다.이 낭비를 없앨 수 없을까? "목적지가 오른쪽에 있다는 걸 알고 있으니, 왼쪽은 덜 살펴봐도 되지 않을까?" — 이 직관이 A* 알고리즘의 시작점이다.A* 알고리즘이란?A* 알고리즘은 출발 노드에서 목적 노드까지의 최단 경로를 찾는 알고리즘이다. 다익스트라와의 결정적..

서론오늘은 최단거리 알고리즘의 대명사 다익스트라 알고리즘에 대해서 알아보도록 하자. 지루하고 현학적인 이론을 설명하기에 앞서 EBS에서 누구나 다익스트라 알고리즘의 원리에 대해 아주 쉽게 시청각 자료를 곁들여서 설명을 해주었다(영상의 40초부터). 따라서 영상을 먼저 보고 온다면 이해해 큰 도움이 될 것이다.다익스트라를 아주 쉽게 설명해준 EBS의 은혜다익스트라 알고리즘(Dijkstra algorithm)이란?다익스트라 알고리즘은 그래프에서 한 노드에서 모든 노드까지의 최단거리를 구하는 알고리즘이다. 영상을 보면 알다시피 Min distance table(MDT)로 불리는 최단거리배열을 갱신하며 최단거리를 구한다. 다익스트라의 핵심은 노드간의 탐색을 할때 현재 도달할 수 있는 간선의 비용중 가장 비용이 ..

문제: 퇴사 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개이면, 곱과 덧셈 중 더 큰..