29940번: Sum (acmicpc.net) 배열이 서로 다른 원소들로 이루어져있고 정렬되어 있을때, 여기서 고른 서로 다른 두 수의 합이 s가 되는 경우의 수를 구하는 문제 투 포인터로 어떻게 해결할 수 있을까 보통 투 포인터하면 i = 0, j = 0으로 같은 방향에서 시작해서 j를 1씩 계속 증가시키다가, 특정 조건에서 멈추고 다시 i를 1 증가시키고 다시 j를 계속 증가시키고... 같은 방향으로 움직이지만 두 수 A[i] + A[j] = s가 될려면 i = 0으로 고정되어 있을 때 A[j] = s - A[0]로 확정적으로 구할 수 있다. 그러면 배열 A가 서로 다른 수로 이루어져 있고 정렬되어 있으므로 모든 i = 0,1,2,..,n-1는 작은 수부터 시작하므로 반대편 A[j] = s - A[..
D - Intersecting Intervals (atcoder.jp) D - Intersecting IntervalsAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 50만개의 구간 [l,r]이 주어질때, 이들 중 서로 겹치는 구간 쌍의 개수가 몇개인지 구하는 문제 모든 구간 쌍에 대해 서로 겹치는지 조사할려면 $O(N^{2})$인데, 당연히 N이 최대 50만이므로 시간제한에 맞지 않는다 전체 구간 쌍의 개수는 n개중 2개를 선택하는 경우의 수이므로, nC2 = n(n-1)/2 만약 서로 겹치치 않는 구간 쌍의 개수를 구..
1. 문제 22862번: 가장 긴 짝수 연속한 부분 수열 (large) (acmicpc.net) 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 2. 풀이 투 포인터로는 원소를 포함시키면서 가장 긴 수열을 찾아가는 건데 어떻게 해야 최대 K번 원소를 삭제하면서 가장 긴 짝수만 포함된 연속 부분 수열을 찾을 수 있을까? 생각보다 간단하다 투 포인터 i,j로 범위를 확장해나가는데, j번 원소가 홀수라면, K값을 감소시키고 길이를 증가시키지 않는다. K가 홀수를 포함시킬 수 있는 최대 기회라고 생각한다면, 원소를 실제로 삭제하지 않고도 마치 삭제한..
1. 문제 2018번: 수들의 합 5 (acmicpc.net) 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 2. 풀이 이전에 풀이한 방식대로, 포인터 i,j를 잡고 구간 [i,j]의 합이 N이 되는지 아닌지를 검사하면 된다 자연수 N이 연속된 자연수의 합으로 나타낼려면 결국 N보다 작거나 같은 자연수의 합으로 나타낼 수밖에 없다 그러므로 1부터 n까지 natural이라는 배열을 만들었고 (정렬은 왜 한건지 모르겠지만..) 포인터 i,j를 잡은 다음, 초기값 natural[0]로 잡는다..
1. 문제 14246번: K보다 큰 구간 (acmicpc.net) 14246번: K보다 큰 구간n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 [i,j](i≤j)의 합이 k보다 큰 모든 쌍 i,j의 개수를 출력하시오.www.acmicpc.net 2. 풀이 첫번째 핵심두개의 포인터 i,j를 두고 i~j까지의 합이 k보다 작다면, 끝 포인터 j를 1칸 늘린다. 모든 수가 자연수이기 때문에 끝 포인터 j를 1칸 늘리면 구간 합이 증가하게 된다 ------------------------------------------------------------------------------------------------------------ 두번째 핵심반대로 i~j까지의 합이 k보다 크다면, 그 순간 j부터 ..
1. 개요 이미 정렬되어 있는 2개의 리스트의 모든 원소를 합쳐서 정렬한 결과를 계산하라한다면 어떻게 해야할까 2. 알고리즘 2-1) 정렬된 리스트 A와 B를 입력받는다 2-2) 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리킨다 2-3) 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리킨다 2-4) A[i]와 B[j]중 더 작은 원소를 결과 리스트에 담는다 만약 A[i]가 더 작다면 i를 1 증가시킨다 B[j]가 더 작다면 j를 1 증가시킨다 2-5) 만약 i나 j가 가리키는 리스트의 길이를 넘어서는 경우, 남아있는 리스트의 원소를 모두 차례대로 담으면 된다 병합정렬이랑 똑같잖아? 3. 예시를 통해 이해하는 알고리즘 A = [1,3,5]이고 B=[2,4,6,8]일때, ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
