Doby's Lab

https://www.acmicpc.net/problem/12834 12834번: 주간 미팅 첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000) 둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V) 셋째 줄에 팀원 N명의 www.acmicpc.net 간단한 다익스트라 문제다. 갈 수 없는 길이 나올 땐 -1 처리를 해주고, 모든 최단 경로를 더한 값을 출력하면 된다. #include #include #include #include #define MAX 1000 + 1 #define INF 987654321 #define pii pair using namespace std; vec..

https://www.acmicpc.net/problem/2268 2268번: 수들의 합 7 첫째 줄에는 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는 www.acmicpc.net 구간 합을 구하는 문제라 똑같이 세그먼트 트리로 풀었으나 어느 지점에서 '틀렸습니다'가 계속 떴었다. 문제를 다시 읽어보니 (i > j)와 같은 경우도 sum 함수를 돌리는 것을 알 수 있었다. 즉, i > j인 경우에는 swap을 해주고 나서 sum을 돌려야 한다. #include #define MAX 1000000 + 1 using namespace std..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 최솟값은 전 포스팅과 똑같은 문제이고, 최댓값은 세그먼트 트리를 구한 후, 값을 찾는 함수에서 영역을 벗어난 경우 0을 리턴해주는 게 최솟값과 다른 점이다. #include #define MAX 100000 + 1 #define INF 1000000000 + 1 using namespace std; long long minTree[4 * MAX]; long l..

https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 시간적인 측면에서 선형적인 구조로 최솟값을 구하면 안 된다. 세그먼트 트리를 써야 한다. long long minTree[4 * MAX]; long long arr[MAX]; 배열과 배열의 값들을 세그먼트 트리로 표현할 minTree를 선언해주고, 세그먼트 트리를 만드는 함수를 만들어준다. //== Segment Tree INIT == (각 노드에 구간 최솟값)..

https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 일반적으로라면 구간 합을 구하는 영역이 3 ~ 7로 주어졌을 때, 3부터 7까지 for문을 써서 3~7 사이의 합을 구하는 것이 일반적이었다. 하지만, 이 문제에서 그런 방법을 사용한다면 시간 복잡도는 O(N * K)로 시간 초과를 유발한다. 오늘 공부한 세그먼트 트리는 시간 복잡도 O(N * K)에서 K를 logK로 줄여주는 신기한 현상..

https://www.acmicpc.net/problem/14588 14588번: Line Friends (Small) Q개의 줄에 걸쳐 두 선분이 가까운 정도를 출력한다. 만약, 두 선분 사이의 친구 관계가 단절되었다면 -1을 출력한다. www.acmicpc.net 1) 선분 간의 관계가 친구임을 입증할만한 함수가 필요하다. 2) 선분(노드)끼리 친구라면 서로 관계에 대한 가중치를 1로 둔다. 3) 플로이드 와샬을 돌린다. 1) 선분 간의 관계가 친구임을 입증할만한 함수가 필요하다. >> 이 부분이 제일 까다로웠다. 2) 선분(노드)끼리 친구라면 서로 관계에 대한 가중치를 1로 둔다. 선분 구조체를 선언하여 한 노드의 왼쪽 점과 오른쪽 점을 담아주었다. typedef struct { int left, ..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net [벨만 포드 정리] (https://yabmoons.tistory.com/365) 다음 블로그를 통해 정리했다. 1. 모든 간선들을 탐색하면서 간선이 잇는 출발 정점이 '한 번이라도 계산된 정점'이라면 해당 간선이 잇는 정점의 거리를 비교해서 업데이트한다. 2. 1번 과정을 반복한다. [한 번이라도 계산된 정점 == dist의 값이 IN..

https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 자기 자신보다 구슬이 무거운 것이 몇 개 있는지 혹은 가벼운 것이 몇 개 있는지 파악하여 둘 중에 하나가 (n + 2) + 1보다 크거나 같으면 절대 전체의 중간에 있지 않다는 것을 알 수 있다. 그렇다면 어떻게 파악하는가? 플로이드 와샬을 쓰면 된다. 무거운 구슬 가벼운 구슬 순서대로 m개 주어졌을 때 가벼운 구슬에서 무거운 구슬로 가는 경로를 1이라고 설정해주고 나서 플로이드..