2024.02.01 (목) Pyalgo100 파이썬 문제풀이

오늘은 계속해서 탐색에 대해서 알고리즘을 공부했다. 오늘 풀 문제들은 LV 0 단계 코딩테스트 문제가 아닌 LV 1 문제들이었다. 그래서 그런지 간단해 보이면서도 복잡했고 사실 전부 풀지 못했다. 하지만 내가 어떻게 생각하고 접근하려 했는지 서술해보려 한다.

 

1. 소수 찾기

문제 설명
주어진 정수 N에 대해, 1부터 N까지의 숫자 중 소수의 개수를 찾는 코드를 작성해주세요. 소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 양의 정수입니다.

제한 사항
주어진 수 N은 2 이상 1,000 이하의 정수입니다.
(hint) 에라토스테네스의 체 알고리즘
속도 측정을 하지 않습니다.

 

입출력 설명
첫 번째 예시에서 1부터 10까지의 소수는 2, 3, 5, 7 이므로 총 4개입니다. 두 번째 예시에서 1부터 5까지의 소수는 2, 3, 5이므로 총 3개입니다.

 

우선 먼저 주어진 정수 N속에서 소수의 개수를 찾아야 했다. 그래서 소수가 어떤것인지 알려주고 뽑아내면은 된다고 생각을 했는데 그것을 코드로 구현하는 것은 정말 쉽지 않았기에 혼자 계속 에러를 마주하다 풀이를 보았다.

def solution(N):
    # 2부터 N까지의 모든 숫자를 포함하는 리스트 생성
    numbers = list(range(2, N + 1))

    # 에라토스테네스의 체 알고리즘 적용
    for i in range(2, int(N**0.5) + 1):
        if i in numbers:
            # i의 배수를 모두 제거
            numbers = [num for num in numbers if (num % i != 0) or (num == i)]

    # 남아있는 숫자는 소수이므로 개수 반환
    return len(numbers)

1. 먼저, 2부터 N까지의 모든 숫자를 포함하는 리스트인 numbers를 생성합니다.
2. 그 다음, 에라토스테네스의 체 알고리즘을 적용합니다. 이 알고리즘은 주어진 범위 내에서의 모든 소수를 찾는 효율적인 방법 중 하나입니다.
3. 에라토스테네스의 체 알고리즘에서는 각 소수의 배수를 제거해 나가는데, 이를 위해 for 루프를 사용하여 2부터 N의 제곱근까지의 숫자를 순회합니다.
4. 만약 현재 순회 중인 숫자 i가 numbers 리스트에 남아 있다면, 이는 아직 제거되지 않은 소수라는 의미입니다.
5. 따라서 i의 배수를 모두 numbers 리스트에서 제거합니다.
6. 마지막으로, 남아 있는 숫자들은 모두 소수이므로 해당 리스트의 길이를 반환하여 소수의 개수를 알려줍니다.

이렇게 풀이를 보고 그렇구나 하면서 지나갔던 것 같다. 하지만 솔직히 아직도 완전히 이해를 하지 못하였다. 에라토스테네스의 체 알고리즘 이라는 걸 앞으로 코딩테스트를 하면서 여러번 마주할 수 있기에 잘 알아두어야 겠다고 생각하면서 저 알고리즘에 대해서 검색을 계속 해봤던 것 같다.

 

2. 최대 합계 배열 찾기

문제 설명
정수로 이루어진 배열과 'k' 길이의 윈도우가 주어집니다. 윈도우를 배열 전체에 슬라이드 시켜가며 얻을 수 있는 최대 합계를 갖는 연속 부분 배열의 합을 찾는 코드를 작성해주세요.

제한 사항
배열의 길이는 최소 k 이상입니다.
배열의 요소는 정수이며, 음수일 수도 있습니다.
k는 1 이상 배열의 길이 이하인 정수입니다.

 

입출력 설명
첫 번째 예시에서 배열 [1, 3, 2, 6, -1, 4, 1, 8, 2]에 대해 길이가 5인 윈도우를 사용하여 얻을 수 있는 최대 합계는 [2, 6, -1, 4, 1, 8] 부분 배열의 합 17입니다. 두 번째 예시에서는 [7, 8, 1] 부분 배열의 합이 16으로 최대 합계입니다.

 

이 문제는 문제부터가 이해가 안갔다.배열과 윈도우가 주어지는데 윈도우를 배열 전체에 슬라이드 시켜가며 얻을 수 있는 최대 합계라는게 무슨 소리인지? 입출력 설명을 보면 있는 예시에 [2, 6, -1, 4, 1, 8] 이것이 왜 나오는지 가 또 합이 20인데 왜 17이라 나오는지 [7, 8, 1] 의 합은 또 16이 맞는데 위의 설명이 오타인건지 뭔지 조차 이해가 가지 않았다. 그래서

chat CPT를 활용하면서 문제를 풀어볼려고 하였는데 아래와 같은 답을 주었다.

def solution(data):
    array, k = data
    # 초기 윈도우 합계 계산
    window_sum = sum(array[:k])
    max_sum = window_sum

    # 윈도우를 슬라이드하면서 최대 합계 찾기
    for i in range(k, len(array)):
        # 윈도우에 새로 추가된 요소 더하고, 이전 윈도우의 첫 번째 요소 빼기
        window_sum = window_sum + array[i] - array[i - k]

        # 최대 합계 업데이트
        max_sum = max(max_sum, window_sum)

    return max_sum

1. 주어진 튜플 data에서 배열과 k를 추출하여 각각 array와 k에 할당합니다.
2. 처음에는 배열의 처음부터 k개의 요소까지의 합을 계산하여 window_sum에 저장합니다.
3. window_sum을 최대값으로 초기화한 후, 이후에 윈도우를 한 칸씩 오른쪽으로 슬라이딩하면서 새로 추가된 요소를 더하고, 이전 윈도우의 첫 번째 요소를 빼는 방식으로 최대 합을 계속 갱신합니다.
4. 최종적으로는 길이가 k인 모든 연속 부분 배열의 합 중에서 최대값인 max_sum을 반환합니다.

사실 오늘 문제들은 LV 1인 만큼 정말 어려웠다. 사실 거의 손도 데지 못했다. 코딩이란 계속해서 꾸준하게 하는 수 밖에 없는 것 같다는걸 너무 체감을 하는 하루였다.