레벨업 일지

문제 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 풀이 현재 위치 i 에서 0..i-1 중에 자신의 실력보다 낮은 개수를 센 다음, 차를 구하는 문제. 분할 정복으로 정렬해서 O(N log N) 풀이하였다. 알고리즘은 다음과 같다. 1. 분할 정복 소트 기법을 사용한다. 2. 두 배열을 병합할때 RIght 배열 원소를 삽입 할때 자기 Left 배열에서 현재숫자보다 낮은 개수를 누적합한다. 3. 자기 자신의 인덱스 - 자신 실력보다 낮은..

문제 https://www.acmicpc.net/problem/15975 15975번: 화살표 그리기 직선위에 $N$개의 점들이 주어지고 각 점은 $N$개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 $N$까지의 수로 표시 하고, 점들의 좌표는 모두 다르다. 각 점 $p$에 대해서, $p$에서 시작하는 직선 www.acmicpc.net 풀이 우선 색깔 별로 정렬을 한다. 같은 색깔이면, 좌표순 오름차순 정렬. 그 다음 O(N)으로 탐색 하면서, 현재 위치 i 에서 left = i-1 , right = i+1 을 꺼내서 비교를 해준다. ArrayList Info = new ArrayList(); // 이런식으로 2차원 리스트를 받는다. Collections.sort(Info, (a,b)->a[1] =..

문제 2212번: 센서 (acmicpc.net) 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 이해를 잘 해야한다. 처음에 센서들의 거리 누적합을 구하는줄 알고 잘못된 접근을 하였다. 센서의 개수 N , 집중국의 개수 K 가 주어진다. 먄약 K == N 이면 각 집중국마다 센서가 있음으로 거리합이 0 이 된다 . 만약 K == 1 이면, 집중국은 센서의 거리 범위 ( i.. j ) 안에 놓기만 하면 j - i 거리합이 된다. K > 1 이면, 이때부터 잘 봐야한다. 1. 센서의..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은..