https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 모든 물고기를 한 칸 이동하는 함수(FishMove()), 상어가 가장 많이 물고기를 없앨 수 있도록 하는 이동 방법을 찾는 함수(SharkMoveFind(vector move)), 찾은 방법으로 상어를 움직이는 함수(SharkMove()), 냄새의 수명을 줄이는 함수(SmellCheck()), 물고기를 복제하는 함수(FishCopy())로 주요 로직을 나눠 문제..

https://www.acmicpc.net/problem/2336 2336번: 굉장한 학생 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 세 개의 줄에는 각 시험에서 1등인 학생부터 N등인 학생이 순서대로 주어진다. 학생의 번호는 1부터 N까지 매겨져 있다. www.acmicpc.net 세그먼트 트리를 이용하여 세 가지 성적(성적 1, 성적 2, 성적 3)을 비교하는 방법으로 문제를 해결했다. 이때 세그먼트 트리는 세그먼트 트리의 [성적 2 등수를 나타내는 위치] = (성적 3의 등수)를 저장해서 활용했다. 각각의 학생마다 세 가지 성적의 등수를 저장하고, 성적 1 등수를 기준으로 정렬하면 확인하는 학생보다 앞에 있는 학생들은 해당 학생보다 성적 1이 좋다는 뜻이므로 앞에 있는 학생들 중..

https://www.acmicpc.net/problem/2454 2454번: 트리 분할 첫째 줄에는 도시의 수 N과 K-경로 분할을 위한 수 K가 빈칸을 사이에 두고 입력된다. N은 2 이상 300,000이하이다. K는 1이상 N-1이하인 정수이다. 다음 N-1개의 각 줄에 도로의 양 끝 도시를 나타내 www.acmicpc.net 주어진 트리를 1번 정점이 루트인 트리로 만들고, 리프 노드부터 루트 노드까지 올라가면서 확인하는 노드와 해당 노드의 자식 노드 그룹이 같은 그룹으로 합쳐질 수 있는지 확인하는 방법으로 문제를 해결했다. 확인하는 정점의 자식 노드를 자식 노드가 루트인 서브 트리(자식 노드 그룹)의 크기 순으로 정렬한 뒤, 작은 것부터 확인하는 정점과 합쳐질 수 있는지를 확인하여 합쳐질 수 있..

https://www.acmicpc.net/problem/15955 15955번: 부스터 첫 번째 줄에 체크포인트의 수 N, 질의의 수 Q가 주어진다. (1 ≤ N, Q ≤ 250,000) 이후 N개의 줄에 체크포인트의 좌표를 나타내는 두 정수 Xi, Yi가 주어진다. (Xi, Yi) 위치에 i번 체크포인트가 있음을 www.acmicpc.net 체크포인트(정점)간의 HP와 부스터를 효과적으로 사용하는 이동은 x축 또는 y축으로 HP를 사용하여 이동한 뒤, 부스터를 사용하는 것이라는 점을 이용한다. x좌표를 기준으로 정렬한 vector와, y좌표를 기준으로 정렬한 vector를 이용해서 x좌표 기준으로 거리가 가까운 점들 사이의 간선을 만들고 y좌표를 기준으로 거리가 가까운 점들 사이의 간선을 만들어서 간..

https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 구간 업데이트의 효율을 위해 느리게 갱신되는 세그먼트 트리를 이용해 문제를 해결했다. 코드 #include #include #include using namespace std; //구간 업데이트의 효율을 위해 느리게 갱신되는 세그먼트 트리 이용 int n, m, k; vector inputs; vector sgmtt(4000000,..

https://www.acmicpc.net/problem/19649 19649번: 미담 전하기 1번 사람에게 미담을 전파하면 전파 과정은 1→2→3→1→2→4→5→6→7→8→7로, 인해 생기는 '간접 미담 전파자'는 {2, 3, 4, 5, 6, 7, 8}로 7명이다. www.acmicpc.net 강한 연결 요소(SCC)를 이용해 SCC를 만들고 SCC사이의 그래프를 만든 뒤, 위상 정렬을 통해 k가 속한 SCC까지 탐색하였다. 탐색과정에서 간접 미담 전파자를 최대로 만들 수 있는 경우를 찾고 경로를 만들었으며, 이동경로를 vector come_from(10001, 0)을 통해 저장하여 최대 간접 미담 전파자 수와 이때의 직접 미담 전파자를 찾았다. 코드 #include #include #include #..