코딩스토리

https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 문제 요약 - 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. - 모든 직원은 민식이의 직접 또는 간접적인 부하이다. (루트 = 민식) - 1분에 한 사람씩에게만 뉴스를 전파할 수 있음 - 모든 직원이 뉴스를 접하게 되는 최소 시간을 구하라 해결 처음에는 자식 노드가 많은 직원부터 소식을 전파하면 되지 않을까 생각해봤는데 조금만 더 고민해보면 당연히 그렇지 않다는 것을..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 풀이 Min, Max Segment Tree를 사용한 문제이다. Min, Max Segment Tree란 각 범위의 최소값과 최대값을 가지고 있는 세그먼트 트리를 말한다. 두 개의 세그먼트 트리를 만들 수도 있지만 코드가 길어질 것 같아서 pair를 사용해 하나의 트리로 만들었다. 구현은 일반적인 세그트리와 비슷하다. 세그트리 자체를 이해했다면 이 코드 역시 ..

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 카드게임의 규칙은 아래와 같다 1. N개의 서로 다른 빨간색 카드 중 M개를 고른다 2. N개의 서로 다른 파란색 카드 중 빨간색 카드의 번호와 같은 카드 M개를 고른다 3. 철수는 빨간색 카드, 민수는 파란색 카드를 가짐 4. 둘은 각각 카드를 한 장씩 내고 번호가 큰 사람이 이김 이 동작을 k번 실행하며 더 많이 이긴 사람이 승리 + ..

https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 문제 분석 문제 내용 자체는 간단하다. A의 등수는 A보다 앞에 있는 사람 중 A보다 달리기 평소 실력이 낮은 친구가 몇 명인지를 알아야 구할 수 있다. 가장 간단한 방법은 당연히 브루트포스이다. 각 인원마다 자신보다 앞에 있는 사람들의 평소 실력을 비교해보면 된다. 이때 문제의 N제한이 50만이기 때문에 당연히 1+2+3+...+50만 = O(50만*50만+1/2) = O(천억...?) 이..

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 일반적인 Prefix Sum으로 구하면 query로 인해 시간 초과가 발생한다. 따라서 Binary Index Tree(펜윅 트리)를 사용하여 구해야 하는 문제이다. 아래는 BIT에 대한 설명이다. https://kimtaehyun98.tistory.com/112 Binary Index Tree(BIT, Fenwick Tree) # 아래 ..