이것저것 공부 기록하기

문제링크 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제풀이 주어진 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제이므로 투포인터로 풀이가 가능한 문제이다. 수열의 길이 N과 타겟으로 봐야할 S의 범위는 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000) 이므로 시간초과에 유의해야한다. 처음에는 아무 생각 없이 주어진 수열 arr의 길이를..

문제링크 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제는 일정 범위 내의 연속된 소수의 합을 찾아야하므로 에라토스테네스의 체로 소수의 리스트를 구하고, 구한 소수 리스트에서 투포인터로 그 합을 구하는 것이 포인트이다. 이 부분을 인지해서 풀이했지만, 처음에는 시간초과가 났고 투포인터 부분에서 시간복잡도 문제가 있다고 생각했다. val = sum(tmp[left:right])에서 (O(right-left) 만큼의 공간을 만드는 시간) + (sum 함수 시간복잡도)가 소요된다. (이 부분은 감으로 고치고 풀이 통과 후에 이왜맞과 맞왜틀을 동시에 시전하며 질문해..

둘 다 완전탐색 시 시간초과가 날 때 유용하게 사용될 수 있다. 투포인터 문제 풀다가 차이가 궁금해서 정리해봤다. 투포인터 vs 이분탐색 투포인터 : left, right 두 개의 포인터를 한 칸씩 이동하면서 알맞은 값을 찾음 이분탐색 : mid를 활용해 매 연산마다 탐색하는 범위를 절반으로 좁혀나감 투포인터(Two Pointer) 이분탐색(이진탐색, Binary Search) 시간복잡도 O(N) O(log N) 가정 특별히 없으나, 일반적으로 배열이 정렬되어있을 때 좀 더 유용 데이터가 정렬되어있어야 함 방식 양 끝단에서 한 칸씩 이동하면서 알맞은 값을 찾음 mid를 활용해서 매 연산마다 탐색하는 범위를 절반으로 좁혀나감 참고 파이썬 알고리즘 인터뷰 https://skesswswkk.tistory.co..