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, 가중치 ..

2252번: 줄 세우기

2252번: 줄 세우기사용 언어: C++ 풀이위상 정렬 문제. 학생 1이 3보다 앞에 있어야 하면 AddEdge(1, 3)에 넣어서 G[1].push_back(3)으로 방향을 나타내고, In[3]++로 학생 3은 진입 차수가 증가해 자기보다 앞선 사람이 있다고 마킹해두는 것.큐에 TopSort()로 진입차수가 0인 사람은 다 push해서 자기 이전에 오는 사람이 없으므로 바로 출력. 그 사람을 출력했으면 그 사람과 연결된 남은 사람들은 진입차수가 1 감소하므로 1을 빼주고, 뺐는데 진입차수가 0이되면 다시 큐에 넣어서 더 이상 남은 사람이 없을때까지 진행.#include using namespace std;int In[100010];vector G[100010];int N, M;void AddEdge(i..

24445번: 알고리즘 수업 - 너비 우선 탐색 2

24445번:  알고리즘 수업 - 너비 우선 탐색 2사용 언어: C++ 풀이단순 BFS -> 큐에 넣어서 해당하는 애를 검사할땐 pop하면서 visited = true 해주고 다음 인접한 애를 visit 한 적 없으면 push하고 걔를 검사. 내림차순이므로 sort할때 greater() 넣기.#include #include #include #include using namespace std;vector graph[100001];int visited[100001];int cnt = 1;void bfs(int start){ queue q; q.push(start); visited[start] = cnt++; while (!q.empty()) { int node = q...

24444번: 알고리즘 수업 - 너비 우선 탐색 1

24444번:  알고리즘 수업 - 너비 우선 탐색 1사용 언어: C++ 풀이단순 BFS -> 큐에 넣어서 해당하는 애를 검사할땐 pop하면서 visited = true 해주고 다음 인접한 애를 visit 한 적 없으면 push하고 걔를 검사. 오름차순이므로 그냥 sort.#include #include #include #include using namespace std;vector graph[100001];int visited[100001];int cnt = 1;void bfs(int start){ queue q; q.push(start); visited[start] = cnt++; while (!q.empty()) { int node = q.front(); ..