class 6https://www.acmicpc.net/problem/13334   # 문제  # 필요개념배열에 담아서 정렬하면 편한 문제겠지만 시간이 1초라서 O(n^2) 가 되면 시간초과가 발생한다. 혹시나 해봤지만 역시나이니 시도하지 않아도 된다. 이렇게 일정 간격을 순회해야 할 경우 투포인터를 응용하여 문제를 풀 수 있다. 이 문제는 일정 간격(dis) 안에 집과 회사가 모두 들어있는 루트의 개수를 구해야 하는 문제이다. 푸는 기본적인 로직은 다음과 같다.입력받은 수를 저장할 이차원 배열과 실제 문제풀이에 이용할 리스트를 각각 생성한다.숫자 두개를 입력받되, 작은 것을 집, 큰 것을 회사라고 가정한다. 입력을 받을 때 작은 숫자가 앞에 오지 않는 경우도 있기 때문에 애초에 배열에 저장할 때 min..

class 5+https://www.acmicpc.net/problem/7453   # 문제정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.  # 예제입력 :  첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.6-45 22 42 -16-41 -27 56 30-36 53 -37 77-36 30 -75 -4626 -38 -10 62-32 -54 -6 45  출력5 # 필요개념배열의 개수가 4개로 정해져있지만, 배열의 최대 크기가..

class 5https://www.acmicpc.net/problem/9527   # 문제두 자연수 A, B가 주어졌을 때, A ≤ x ≤ B를 만족하는 모든 x에 대해 x를 이진수로 표현했을 때 1의 개수의 합을 구하는 프로그램을 작성하시오.즉, f(x) = x를 이진수로 표현 했을 때 1의 개수라고 정의하고, 아래 식의 결과를 구하자. # 예제입력 :  첫 줄에 두 자연수 A, B가 주어진다. (1 ≤ A ≤ B ≤ 1016)2 12 출력21 # 필요개념이 문제에서는 입력값의 범위가 int를 넘어가기 때문에, long을 사용해주어야 한다. 이는 숫자가 정말 ! 커진다는 것이다.처음 문제를 풀 때, 비트마스킹을 이용할 생각은 없었고 그냥 dp와 누적합을 이용할 생각이었다.  비트비트(Bit)는 우리가 ..

백준 알고리즘 분류 (그리디 알고리즘) https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net # 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠..