Barbera

필요한 배경지식 세그먼트 트리 Inversion Counting Inversion은 다음과 같이 정의됩니다. 길이가 N인 배열 A[1], A[2], ..., A[N]이 주어질때, $ i A[j] $를 만족할때 $A[i]$와 $A[j]$는 Inversion관계이다. Inversion Counting은 위에서 설명한 Inversion관계의 총 개수를 찾는 문제 입니다. 배열이 정렬이 되어 있을때는 Inversion Counting이 0이 되지만 역순으로 정렬되어 있다면 최대가 됩니다. Inversion쌍을 구하기 위한 방법으로 완전탐색을 생각해보면 \( O(N^{2}) \)의 시간복잡도로 모든 쌍을 비교해 볼 수 있지만 대부분의 문제에서 시간안에 해결할 수 없습니다. 이 문제..

https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 www.acmicpc.net 필요한 배경지식 이분매칭 소수판정 - (에라토스테네스의 체) 문제 해결 방법 이분매칭을 이용하면 됩니다. 우선 두 수를 더한 값이 소수일때 두 수를 연결하는 간선을 추가하여 그래프를 만들어야 합니다. 그 다음 이분매칭을 하여 매칭된 쌍의 개수가 N/2개일때 첫 번째 수와 짝지어진 수를 출력하면 됩니다. 소수를 판정할 때에는 두 수를 더한 값이 최대 ..

https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 필요한 배경지식 1번 풀이 : DFS, BFS 2번 풀이 : BFS, 외판원 문제(TSP) 3번 풀이 : BFS, DP, 비트마스킹 문제 해결 방법 방의 크기가 최대 20*20이므로 최단경로를 구하기 위해 BFS를 한번 수행하는 시간은 크게 문제가 되지 않습니다. 더러운 칸의 개수가 10개이므로 BFS를 최대 11번 수행하여 모든 더러운 칸과 로봇청소기 사이의 거리를 어렵지 않게 구할 수 있습니다. (di..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 필요한 배경지식 DFS, BFS 문제 해결 방법 모든 빈칸에 바이러스가 있게 되는 최소 시간을 구해야 합니다. DFS를 이용하여 활성화할 M개의 바이러스를 고르고, 해당 바이러스들을 시작노드로 BFS를 수행하여 최소 시간을 구해낼 수 있습니다. 바이러스가 총 k개 있고 m개의 바이러스를 활성화 시킬 수 있다면 C(k,m) 만큼 BFS를 수행하여 최소 시간을 구해야 합니다. 최소시간을 구하는 과정에서 바이러..

https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 필요한 배경지식 다이나믹 프로그래밍 문제 해결 방법 3차원 배열을 사용하여 DP로 문제를 해결했습니다. [1,4] 범위의 수가 N만큼 주워질때 배열 dp[n][x][y] = k에 대한 의미는 다음과 같습니다. n의 범위: [0,N] x, y의 범위: [0,4] k: n번째 수까지 입력 받았을때, 두 발의 위치가 x, y인 경우에 사용된 최소의 힘 위와 같이 정의한..

https://www.acmicpc.net/problem/15957 15957번: 음악 추천 입력의 첫째 줄에는 세 정수로, 곡의 수 N(2 ≤ N ≤ 100,000), 추천 알고리즘의 결과 데이터의 수 K(1 ≤ K ≤ 100,000), 목표 점수 J(10 ≤ J ≤ 108)가 주어진다. 각각의 곡은 1번부터 N번까지 번호가 붙어 www.acmicpc.net 필요한 배경지식 병렬 이분 탐색(PBS), 펜윅 트리, 오일러 경로 테크닉 문제 해결 방법 [1,N] 번 노래를 부른 가수의 평균 점수가 J를 넘게 되는 시간을 각각 구하기 위해, 주워지는 쿼리를 이용하여 병렬 이분 탐색을 할 수 있습니다. 특정 노래를 부른 가수의 평균점수가 J점수를 언제 초과하는지 확인하기 위해 쿼리를 매개변수로 이분탐색을 하는..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 이분 그래프의 설명을 이해하기 어려워서 위키백과를 참고했습니다 문제 해결 방법 노드를 탐색할때 1과 0이 번갈아 나타나도록 방문처리를 해주면서 탐색도중 같은 방문값이 연속적으로 나타난다면 NO를 출력하고 그렇지 않으면 YES를 출력하도록 했습니다. 입력되는 데이터 중 연결되지 않은 집합이 존재할 수 있으므로 모든 노드의 방문을 확인해 주어야 합니다. C++ 전체 코드 #include ..

https://www.acmicpc.net/problem/12746 12746번: Traffic (Large) 사람들이 가장 많이 이용하는 구간을 출력하고, 몇 명의 사람들이 그 구간을 거쳤는지 출력한다. a b c 꼴로 출력하면 되는데, 이는 사람들이 가장 많이 이용하는 구간이 a번 역과 b번 역을 연결하 www.acmicpc.net 필요한 배경지식 최소 공통 조상(LCA), 트리에서의 다이나믹 프로그래밍 문제 해결 방법 이전에 포스팅한 농장 관리 문제에서 풀이한 방법과 같은 방법을 이용하여 철로를 지난 사람의 수를 구할 수 있습니다. 농장 관리 문제와 다른점은 업데이트가 모두 이루어진 후 결과값을 출력하기 때문에, 노드에 추가되는 가중치를 배열에 누적하여 저장하고 DP로 문제를 해결할 수 있습니다. ..