2023.04.08 TIL

알고리즘 문제를 쭈~욱 풀어보며 공부했다. 백준 9020-골드바흐의 추 측 문제를 풀면서 시간 초과를 만났고, 내 코드에 적용하여 시간복잡도를 개선할 수 있었던 방법 두가지를 메모하려 한다. 추후 코딩 테스트에도 쓰일 수 있는 내용이라고 하니 기억해두면 좋을 듯 😄

에라토스테네스의 체

에라토스테네스의 체란?

• 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾을 수 있는 효과적인 방법

• 어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2는 소수
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

def isPrime(num):
    if num == 1: return False
    if num == 2: return True
    if num % 2 == 0: return False

    for i in range(3, int(num**0.5)+1, 2):
        if num % i == 0:
            return False

    return True

많은 양의 소수를 구할 필요가 있을 경우에는 에라토스테네스의 체를 사용하자! 시간복잡도 면에서 큰 개선 가능

투 포인터 알고리즘

투 포인터 알고리즘이란?

• 리스트에 순차적으로 접근할 때 두 포인터의 위치를 조작해가며 원하는 값을 구하는 알고리즘. 시간복잡도가 O(n)으로 좋다.

• 필요에 따라 단방향, 양방향 다양하게 활용할 수 있다.

• 일반적으로 단방향의 경우는 인접해 있는 두 인자의 부분합을 구하는데 사용할 수 있다.

• 양방향의 경우에는 정렬된 배열의 각각의 인자들의 합을 구할 때 사용할 수 있다. 원하는 값 이상, 이하의 출력이 나오는 경우를 효과적으로 소거하며 진행할 수 있다.

• 내가 문제를 풀며 구현했던 투 포인터 알고리즘의 일종
  이번 경우 검사할 리스트가 중복값을 지니지 않았기에 이를 검사하는 부분은 주석처리하였다.

    matchs = []
    matchCount = 0
    startPoint = 0 
    endPoint = len(primesUnderEven)-1
    
    while 1:
        currentSum = primesUnderEven[startPoint] + primesUnderEven[endPoint]
        if endPoint < startPoint:
            break

        if currentSum < even:
            startPoint +=1
        elif currentSum > even:
            endPoint -= 1
        else:
            matchs.append([primesUnderEven[startPoint] , primesUnderEven[endPoint]])
            matchCount += 1
            endPoint -= 1
            # 중복된 인자가 붙어있을경우 ex) 2, 2, 3, 5, 6 ... 일때 중복되는 만큼 포인터를 움직여주고, 그에 따른 결과값이 몇개가 나오는지 계산하여 카운트에 더해 준다.
            # 이번 경우에는 소수를 담아놓은 primesUnderEven 리스트가 중복되는 인자를 가지지 않기에 스킵 가능!
            # currentPosition = [primesUnderEven[startPoint], primesUnderEven[endPoint]]
            # countStartDup = 0
            # countEndDup = 0
            # while primesUnderEven[startPoint] == currentPosition[0]:
            #     countStartDup += 1
            #     startPoint += 1
            # while primesUnderEven[endPoint] == currentPosition[1]:
            #     countEndDup += 1
            #     endPoint -=1
            # matchCount += countStartDup * countEndDup

배열의 연속된 부분합을 구하거나, 각 인자들의 합 중 목표와 일치하는 값을 찾아야 하는 경우, 완전탐색이 아닌 투 포인터 알고리즘을 사용한다면 시간복잡도를 개선할 수 있다.