14888번: 연산자 끼워넣기

14888번: 연산자 끼워넣기사용 언어: C++ 문제 요약N개의 수와 N-1개의 연산자가 주어짐.수의 순서를 바꾸지 않고, 주어진 연산자를 모두 사용해 수식을 완성.연산 순서는 앞에서부터(왼쪽에서 오른쪽으로) 진행.가능한 모든 수식 결과 중 최댓값과 최솟값을 출력해야 함.풀이가능한 연산자 순열을 모두 탐색해야 하므로 백트래킹(DFS) 을 사용.각 재귀 단계마다 남아 있는 연산자 중 하나를 선택해 현재까지의 계산 결과를 갱신.나눗셈은 음수 처리를 주의해야 함 (C++ 기준: -(-a / b) 방식으로 처리).#include #include #include using namespace std;int N;vector A;int op[4]; // +, -, *, /int max_val = -1e9;int min..

2580번: 스도쿠

2580번: 스도쿠사용 언어: C++ 풀이문제 요약9×9 스도쿠 판에서, 일부 칸이 비어 있고(0으로 표시됨), 규칙에 맞게 모든 칸을 채워야 함.각 행에 1~9가 한번씩각 열에 1~9가 한번씩각 3×3 구역에 1~9가 한번씩풀이백트래킹 기법을 이용하여 모든 빈 칸에 대해 가능한 수를 대입하고,불가능한 경우 이전 상태로 돌아가서 다른 수를 시도.핵심 아이디어빈 칸을 순서대로 탐색하며 가능한 숫자를 시도숫자를 채울 때마다, 행/열/구역 사용 여부를 표시가능한 경우 다음 칸으로 재귀 호출실패하면 상태를 되돌리고 다음 숫자 시도 (백트래킹)구현 포인트각 행/열/3×3 구역에 대해 숫자 사용 여부를 확인하기 위해bool row[9][10], col[9][10], square[9][10] 배열을 사용한다.(i /..

24060번: 알고리즘 수업 - 병합 정렬 1

24060번: 알고리즘 수업 - 병합 정렬 1사용 언어: C++ 풀이Merge Sort (병합 정렬) 문제.기본 병합 정렬 구현 문제. 핵심은 정렬이 완료된 배열이 아니라, 정렬 중 원소가 배열 A에 저장되는 순간을 추적해서,K번째로 저장되는 값을 출력하는 것.병합 과정에서 A[i] = tmp[t]가 실행될 때마다 저장 횟수(cnt)를 세고,cnt == K가 되면 해당 값을 result에 저장한다.만약 저장 횟수가 K보다 작으면 -1 출력.#include using namespace std;int A[500001], tmp[500001];int N, K, cnt = 0, result = -1;void merge(int p, int q, int r) { int i = p, j = q + 1, t = ..

11505번: 구간 곱 구하기

11505번: 구간 곱 구하기사용 언어: C++ 풀이구간 합 구하기 문제와 유사. 구간의 곱을 구하는 것이므로 트리는 똑같이 만든다. 한 가지 다른 점은, 트리를 만들때 % MOD를 한다는 것인데, 어차피 마지막에 한번 Mod를 하나 중간 계속 Mod를 하나 결과는 같다. 그래서 Overflow가 안나게 매번 % MOD를 해준다는 것. Query에서도 곱을 하면서 % MOD를 해준다.#include using namespace std;typedef long long ll;const int MOD = 1'000'000'007;constexpr int SZ = 1 > N >> M >> K; for (int i = 0; i > num; Set(i, num); } for (int i..

2042번: 구간 합 구하기

2042번: 구간 합 구하기사용 언어: C++ 풀이리프 노드들은 입력 값들, 부모 노드들은 값들의 합으로 설정해서 O(log n)으로 구간의 합을 구하는 세그먼트 트리 문제다. 주의할 점은 a == 1일때 c가 int 범위를 넘어서 오버플로우가 발생할 수 있어서 long long을 설정해야한다.#include using namespace std;typedef long long ll;// SZ는 N보다 크거나 같은 2^k 꼴의 수 (2^20 == 1,048,576 > 1,000,000)constexpr int SZ = 1 > N >> M >> K; for (int i = 0; i > num; Set(i, num); // 세그먼트 트리 초기화 } for (int i = 0; i..

9372번: 상근이의 여행

9372번: 상근이의 여행사용 언어: C++ 풀이모든 도시는 연결되어있고, 현재 위치가 중요하지도 않으므로, 그냥 간선의 수 - 1이 답이다.#include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) { int N, M; cin >> N >> M; for (int i = 0; i > a >> b; } // 모든 도시는 항상 연결되어있음 // -> 최소 간선 수는 항상 N-1 cout

11657번: 타임머신

11657번: 타임머신사용 언어: C++ 풀이음수 간선이 있으므로 벨만포드 알고리즘으로 풀면 된다. 벨만포드는 1번부터 n번 거리 완하를 시도하고, n번째 완하에도 거리가 줄어든다면 무한대로 줄어들 수 있는 경로가 있다는 것이므로 false return 한다.#include using namespace std;typedef long long ll;const ll INF = 1e18; // 무한대int N, M;ll D[555]; // 거리 배열, 최단 거리를 저장vector> E; // 간선 목록 {출발지, 도착지, 가중치}void AddEdge(int s, int e, int w){ E.emplace_back(s, e, w);}// 벨만-포드 알고리즘: 음수 사이클이 있으면 false 반환bool..

11404번: 플로이드

11404번: 플로이드사용 언어: C++ 풀이모든 지점에서 다른 모든 지점으로의 최솟값을 알아야하므로 플로이드 워셜 알고리즘으로 풀어야함.2차원 배열을 자기 자신은 0, 그 외에는 0x3f (매우 큰 수)로 초기화하고, s도시에서 e도시로 방향이 있고 가중치 w인 AddEdge(s, e, w)로 2차원 배열에 값들 저장.Run()은 그냥 모든 점들의 최솟값을 확인하는 함수. G[i][j]와 G[i][k] + G[k][j] 중 최솟값을 계속 업데이트. #include using namespace std;int n, m;int G[101][101];void Init(){ memset(G, 0x3f, sizeof G); // 자기 자신 도시는 0 for (int i = 1; i e, 가중치 ..