전체 글97 [백준 C++] 15824번: 너 봄에는 캡사이신이 맛있단다 1. 문제https://www.acmicpc.net/problem/15824 2. 알고리즘 분류수학정렬조합론분할 정복을 이용한 거듭제곱 3. 소스 코드#include #include #define MAX_N 300000using namespace std;typedef long long ll;ll scovile[MAX_N];ll MOD = 1000000007;// binary exponentiation 알고리즘ll binpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % MOD; a = (a * a) % MOD; b >>= 1; } return res;}int main() { ios_base::sync_with_stdio(fa.. 2024. 6. 15. [백준 C++] 13334번: 철로 1. 문제https://www.acmicpc.net/problem/13334 2. 알고리즘 분류자료 구조정렬스위핑우선순위 큐 3. 소스 코드#include #include #include #include using namespace std;int N, d, ret;vector> pos;priority_queue, greater> pq;bool cmp(pair a, pair b) { if (a.second == b.second) { return a.first > N; // 집과 사무실 거리 입력 for (int i = 0; i > h >> o; if (h > o) swap(h, o); pos.push_back({ h, o }); } // d : 철로의 길이 cin >> d; // end 거리 기준으로.. 2024. 6. 9. [백준 C++] 14725번: 개미굴 1. 문제https://www.acmicpc.net/problem/14725 2. 알고리즘 분류자료 구조문자열트리트라이 3. 소스 코드#include #include #include #include #include using namespace std;int N, K;struct Trie { map m; // 트라이 삽입 함수 void insert(vector& v, int idx) { // 삽입할 vector 인덱스 넘었을 경우, Return if (idx == v.size()) return; // 새 트라이 할당 및 추가 if (m.find(v[idx]) == m.end()) { Trie* trie = new Trie.. 2024. 6. 9. [백준 C++] 2533번: 사회망 서비스(SNS) 1. 문제https://www.acmicpc.net/problem/2533 2. 알고리즘 분류다이나믹 프로그래밍트리트리에서의 다이나믹 프로그래밍 3. 소스 코드#include #include #include #define MAX_N 1000006using namespace std;int N;vector graph[MAX_N];int dp[MAX_N][2]; // dp[x][y] = x번 노드가 0(얼리 아답터) 또는 1(일반인) 경우,bool visited[MAX_N];void dfs(int cur){ visited[cur] = true; dp[cur][0] = 1; // 얼리 아답터인 경우 1 // 1. 현재 노드가 0(얼리 아답터)인 경우, dp[현재 노드][얼리 아답터] += min(dp[다.. 2024. 6. 6. [백준 C++] 2098번: 외판원 순회 1. 문제https://www.acmicpc.net/problem/2098 2. 알고리즘 분류다이나믹 프로그래밍비트마스킹비트필드를 이용한 다이나믹 프로그래밍외판원 순회 문제 3. 소스 코드#include #include #include #define MAX_N 16#define INF 987654321using namespace std;int N;int W[MAX_N][MAX_N];int dp[MAX_N][1 > N; for (int i = 0; i > W[i][j]; memset(dp, -1, sizeof(dp)); cout 2024. 5. 15. [백준 C++] 1799번: 비숍 1. 문제https://www.acmicpc.net/problem/1799 2. 알고리즘 분류백트래킹 3. 소스 코드#include #include #define MAX_N 10using namespace std;int n, ans;int map[MAX_N][MAX_N];bool is_visited_upward_right[2 * MAX_N];bool is_visited_downward_right[2 * MAX_N];// DFS 알고리즘void dfs(int diagonal_index, int bishop_cnt) { /* 우상향의 대각선의 index를 모두 탐색했을 경우, * 우상향의 대각선의 갯수 = 2 * (맵의 크기) - 1 * n = 5 => 대각선의 갯수 = 9개 * 1 2 3 4 5 * .. 2024. 5. 15. [백준 C++] 1562번: 계단 수 1. 문제https://www.acmicpc.net/problem/1562 2. 알고리즘 분류다이나믹 프로그래밍비트마스킹비트필드를 이용한 다이나믹 프로그래밍 3. 소스 코드#include #define MOD_NUM 10e8using namespace std;long long dp[1 > N; /* * 다이나믹 프로그래밍 * dp[존재하는 숫자 bit 표시][총 자릿수][마지막 자리의 숫자] = 해당 조건의 경우의 수 * * ex) 존재하는 숫자 bit 표시 * 이진수로 표현했을 때, i번째 자릿 수의 값이 1이라면, (i - 1) 숫자가 존재한다는 의미. * 502이면, 해당 숫자는 0, 2, 5라는 숫자가 있으므로 0000100101(2) 로 표현된다. * * 행 : 마지막 자리의 숫자 / 열 .. 2024. 5. 6. [알고리즘] 다이나믹 프로그래밍(DP, Dynamic Programming) 1. 문제https://www.acmicpc.net/problem/1509 2024. 5. 4. [백준 C++] 1509번: 팰린드롬 분할 1. 문제https://www.acmicpc.net/problem/1509 2. 알고리즘 분류다이나믹 프로그래밍 3. 소스코드#include #include #include #define MAX_LEN 2501#define INF 2134567890using namespace std;bool dp[MAX_LEN][MAX_LEN];string str;int str_len, result[MAX_LEN];// 팰린드롬인지 확인하는 알고리즘bool is_palindrome(int start, int end) { // end 값이 문자열 길이를 넘어갔을 경우, False if (end > str_len) return false; // 시작 문자열과 끝 문자열이 같고, 시작점과 끝점 문자열을 제외했을 때, 그 문.. 2024. 5. 4. [백준 C++] 1208번: 부분수열의 합 2 1. 문제https://www.acmicpc.net/problem/1208 2. 알고리즘 분류이분 탐색중간에서 만나기 3. 소스 코드#include #include #define MAX_N 40using namespace std;int N, S;int arr[MAX_N];map sum2cnt;long long cnt;// 오른쪽 부분수열의 모든 경우의 수 계산void rightSeq(int mid, int sum) { // 수열의 끝까지 도달했을 경우, if (mid == N) { sum2cnt[sum]++; // 부분수열의 합을 저장 return; } rightSeq(mid + 1, sum + arr[mid]); // 해당 index의 수열의 값을 더했을 경우, rightSeq(mid + 1, su.. 2024. 5. 1. 이전 1 2 3 4 ··· 10 다음
