전체 글108 [BOJ] 백준 14938번: 서강그라운드 모든 지점에서 다익스트라를 반복하여 최대값을 찾는 문제 #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; vector v[101]; int dist[101]; int item[101]; int n, m, r; bool visit[101] = { 0, }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m >> r; for (int i = 1; i > item[i]; } for (int i = 0; i < r; i++) { .. 2020. 6. 19. [BOJ] 백준 11779번: 최소비용 구하기 2 #include #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; vector v[1001]; int dist[1001]; int pre[1001]; int n, m; int s, e; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m; memset(pre, -1, sizeof(pre)); for (int i = 1; i > a >> b >> c; v[a].push_back({ b,c }); } cin >> s >> e; priority_.. 2020. 6. 19. [BOJ] 백준 1238번: 파티 주어진 입력을 정방향, 역방향 2개의 벡터로 저장하여 파티가 열리는 노드를 시작으로 다익스트라를 2번 수행하여 오고 가는데 걸린 최단 경로 합의 최대를 출력하는 문제 #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; vector v[10001]; vector v2[10001]; int dist[10001]; int dist2[10001]; int n, m, x; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m >> x; for (int .. 2020. 6. 19. [BOJ]백준 1167번: 트리의 지름 1번 정점을 루트로 가정하고 dp[i]를 i번째 정점을 서브 트리의 루트로 가정했을때 가장 긴 지름을 저장함 #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; int n; vector v[100001]; int dp[100001]; // i 를 루트로 했을때 지름 길이 int recv(int node, int p) { int& ret = dp[node]; if (~ret) return ret; ret = 0; int _max1 = 0, _max2 = 0; for (auto nxt : v[node]) { int _node = nxt.first; int .. 2020. 6. 19. [BOJ] 백준 1016번: 제곱ㄴㄴ수 제곱으로 나누어떨어지지 않는 수를 찾기 위하여 1부터 _max의 제곱근 까지의 소수를 찾아 리스트에 저장한 후 _min과 _max의 범위가 최대 100만 차이임을 이용하여 찾은 소수 제곱에 대한 배수를 채로 걸러 전체 수에서 뺌 #include #include #include #include #include #include using namespace std; typedef pair pii; typedef long long ll; ll _min, _max; bool s[1000001] = { 0, }; bool ans[1000001] = { 0 , }; vector v; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL.. 2020. 6. 19. [BOJ] 백준 16491번: 대피소 찾기 CCW를 이용한 선분 교차 판별 알고리즘을 통해 DFS 탐색하는 문제 #include #include #include #include #include using namespace std; typedef pair pii; int n; int rsy[101] = { 0, }; // 같은 y좌표를 갖는 로봇 int dsy[101] = { 0, }; // 같은 y 좌표를 갖는 대피소 pii pr[101]; pii pd[101]; int tmp[101]; bool visit[101]; int ccw(int x1, int y1, int x2, int y2, int x3, int y3) { int left = x1 * y2 + x2 * y3 + x3 * y1; int right = x1 * y3 + x3 * y2 +.. 2020. 6. 19. [BOJ] 백준 1086번: 박성원 주어진 수 K로 1~100 까지 수를 나눈 나머지를 dp배열에 저장하여 메모이제이션 탐색 종만북에 비슷한 문제가 있음 #include #include #include #include #include #include using namespace std; typedef long long ll; ll n,k; ll mod[16][101]; ll dp[100000][100]; // state에서 나머지 k인 경우 string arr[16]; ll ans =0; ll gcd(ll a,ll b){ ll c= a %b; while(c){ a= b; b= c; c = a%b; } return b; } ll recv(ll state, ll m){ if(state == (1 k ; // j arr[i] mod k = mo.. 2020. 6. 17. [BOJ] 백준 1017번: 소수쌍 소수 = 홀수 + 짝수의 조합으로만 가능한 아이디어를 시작으로 홀수와 짝수를 두 개의 그룹으로 나눠, 시작하는 수의 짝을 고정하여 이분매칭을 반복하는 문제 #include #include #include #include using namespace std; typedef long long ll; bool s[2001] = { 0, }; int arr[1001]; int ma[1001]; int curd; bool visit[1001]; int _lsize, _rsize; vector l, r; bool dfs(int node) { if (visit[node]) return false; visit[node] = true; for (int i = 0; i < _rsize; i++) { if (i != cur.. 2020. 6. 17. [알고스팟] 록 페스티벌 ID: FESTIVAL 문제 링크 이글을 검색하여 들어오신 분들은 알고리즘을 입문하시는 분들이라 생각됩니다. 이 블로그는 매일 푼 문제에 대하여 글을 올리고 있습니다. 주로 종만북과 백준을 이용합니다. 1, 2, 3 ... N 번째 중 i번째 날까지의 누적 합을 psum[i] 에 저장하면 O(1)의 복잡도로 [start: end] 구간 합 계산이 가능합니다. 예를 들어 3~6 번째 날의 구간 합은 psum[6] - psum[3-1] 으로 구할 수 있습니다. 간단한 아이디어지만 PS할 때 많이 사용됩니다. /* 2019-06-22 */ #include #define min(a,b) (a 2019. 6. 22. 이전 1 ··· 9 10 11 12 다음
