투포인터2

• 

  투 포인터 알고리즘: 리스트에서 특정한 합이나 패턴 찾기 투 포인터 알고리즘이란? 주로 배열이나 리스트에서 두 개의 포인터를 사용하여 문제를 해결하는 기법 이 알고리즘을 사용하면 선형 시간 복잡도 O(N)으로 동작하며, 정렬된 배열 또는 리스트에서 특정한 합이나 패턴을 찾는 문제에 효과적으로 사용된다 예시? 예시는 이전에 백준 알고리즘 1644번: 소수의 연속합 문제에 사용되었던 투 포인터 알고리즘을 사용한 풀이에서 예시를 들어 설명하도록 하겠다 문제에 대한 설명은 아래 참고 링크에 올라온 글을 참고하면 좋을 것 같다 이 문제의 경우, 소수들의 연속적인 합이 몇개가 있는지 출력하는 문제이다 target number가 41인 경우를 예를 들어 설명하자면, 먼저 에라토스테네스의 체 알고리즘을 사용하여 41까지의 소수를 primes 배열에 저장할 것이다 그 후 현재.. 알고리즘/개념 2023. 7. 2.

• 백준 알고리즘 1644번: 소수의 연속합 문제 정보 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 핵심 일반 풀이와 투 포인터를 활용한 풀이가 두가지가 있다 무조건 에라토스테네스의 체 알고리즘을 활용하여 문제를 풀이하여야 하며 해당 개념은 이전에 올렸던 글에서 참고할 수 있다 (아래 참고 링크 확인) 위 두가지 풀이 모두 파이썬 기준 백준 제출시 통과되지만, 효율성은 투 포인터가 훨씬 좋다 풀이 일반 풀이 import sys N = int(sys.stdin.readline()) prime = [True for _ in range(N+1)] prime[0], prime[1] = False, False for i in range(2, int(N**0.5) + 1): if.. 알고리즘/Python 2023. 7. 2.