2024.02.02 (금) Pyalgo100 파이썬 문제풀이

오늘은 탐색이라는 알고리즘을 풀어보았다. 어제 푼 문제들과 비슷하지만 아직까지 나에게는 너무 어려운 개념이라는 걸 또 한번 느꼈다. 문제를 읽으면서도 감이 잘 안왔지만 코드를 작성하는데 있어서 많이 어려웠다. 그래서 어제 자료들과 chat GPT의 도움들의 여러번 거쳐서 정답을 풀어나갔다.

 

1.작은 길이 부분 배열 찾기

문제 설명
정수 배열과 타겟 합 S가 주어집니다. 배열 내 연속된 부분 배열 중에서 그 합이 S 이상이 되는 가장 작은 길이의 부분 배열을 찾아, 그 길이를 반환하는 코드를 작성해주세요. 만약 그러한 부분 배열이 존재하지 않으면 0을 반환합니다.

제한 사항
배열의 각 요소는 양의 정수입니다.
배열의 길이는 최소 1에서 최대 100까지입니다.
타겟 합 S는 양의 정수입니다.

 

입출력 설명
첫 번째 예시에서 배열 [2, 1, 5, 2, 3, 2] 내에서 합이 7 이상이 되는 가장 작은 길이의 부분 배열은 [5, 2]로 길이가 2입니다. 두 번째 예시에서는 합이 11 이상이 되는 부분 배열이 존재하지 않으므로 0을 반환합니다.

 

이 문제는 배열이 나와있는데 그것 말고도 배열 내 연속된 부분의 합이 s로 나타나있다. 그래서 목표는 합이 s 이상이 되는 가장 작은 길이의 부분 배열의 찾는 것인데 나에게 정말 정말 어려웠다. 그래도 풀면서 정수 배열 nums와 목표 합 target_sum이 주어졌을 때, 배열 내에서 연속된 부분 배열 중에서 그 합이 target_sum 이상이 되는 가장 작은 길이의 부분 배열의 길이를 찾고자 하였는데 구글링을 하다보니 슬라이딩 윈도우 라는 알고리즘이름으로 배열 내에서 특정 범위를 움직여가며 원하는 조건을 만족시키는 방법을 찾게 되었다.

def solution(data):
    nums, target_sum = data
    min_length = float('inf')  # 최소 길이를 저장하는 변수를 무한대로 초기화

    current_sum = 0
    start = 0

    for end in range(len(nums)):
        current_sum += nums[end]

        while current_sum >= target_sum:
            min_length = min(min_length, end - start + 1)
            current_sum -= nums[start]
            start += 1

    if min_length == float('inf'):
        return 0
    else:
        return min_length

1. current_sum: 현재 부분 배열의 합을 저장하는 변수입니다. 초기에는 0으로 설정합니다.
2. start: 현재 부분 배열의 시작 인덱스를 나타내는 변수입니다. 초기에는 0으로 설정합니다.
3. min_length: 찾은 가장 작은 길이의 부분 배열의 길이를 저장하는 변수입니다. 초기에는 무한대로 설정하여 나중에 비교할 때 사용합니다.
4. for end in range(len(nums)):: 배열을 순회하면서 각 요소를 current_sum에 더해가며 부분 배열을 만듭니다.
5. while current_sum >= target_sum:: 현재 부분 배열의 합이 목표 합 이상이면, 시작 인덱스를 증가시키면서 가장 작은 길이를 찾습니다.
6. min_length = min(min_length, end - start + 1): 찾은 부분 배열의 길이가 현재까지의 최소 길이보다 작으면 업데이트합니다.
7. current_sum -= nums[start]: 시작 인덱스를 증가시키면서 해당 요소를 현재 부분 배열의 합에서 빼줍니다.
8. start += 1: 시작 인덱스를 증가시킵니다.
9. 최종적으로 함수는 찾은 가장 작은 길이의 부분 배열의 길이를 반환합니다. 만약 그러한 부분 배열이 없다면 0을 반환합니다.

2. 가장 가까운 합 찾기

입출력 설명
첫 번째 예시에서 배열 [2, 1, 5, 2, 3, 2] 내에서 합이 7 이상이 되는 가장 작은 길이의 부분 배열은 [5, 2]로 길이가 2입니다. 두 번째 예시에서는 합이 11 이상이 되는 부분 배열이 존재하지 않으므로 0을 반환합니다.

제한 사항
배열은 오름차순으로 정렬되어 있습니다.
배열의 길이는 2 이상 100 이하입니다.
배열의 요소와 타겟 값은 정수입니다.

 

입출력 설명
첫 번째 예시에서 배열 [1, 2, 3, 4, 5] 내에서 합이 타겟 값 10에 가장 가까운 조합은 4와 5의 합인 9입니다. 두 번째 예시에서는 2와 8의 합인 10이 타겟 값 11에 가장 가깝습니다.

 

문제를 풀면서 정렬된 정수 배열(nums)과 목표 값(target)이 주어졌을 때, 배열 내의 두 요소를 선택하여 그 합이 목표 값과 가능한 가까워지도록 하는 두 요소의 합을 찾기 위해서 노력하였다. 그 중 구글링을 통해 투 포인터 라는 정렬된 배열에서 두 개의 포인터를 사용하여 원하는 조건을 찾는 방법을 찾고 사용해보려 했다.

def solution(data):
    nums, target = data
    closest_sum = float('inf')  # 가장 가까운 합을 무한대로 초기화
    left, right = 0, len(nums) - 1

    while left < right:
        current_sum = nums[left] + nums[right]
        diff = abs(current_sum - target)

        if diff < abs(closest_sum - target):
            closest_sum = current_sum

        if current_sum < target:
            left += 1
        elif current_sum > target:
            right -= 1
        else:
            return target  # 합이 타겟 값과 같으면 결과 반환

    return closest_sum

1. closest_sum: 가장 가까운 합을 저장하는 변수로, 초기에는 무한대로 설정합니다.
2. left, right: 배열의 가장 왼쪽과 가장 오른쪽을 가리키는 두 포인터입니다.
3. while left < right:: 왼쪽 포인터가 오른쪽 포인터보다 작을 때까지 반복합니다.
4. current_sum = nums[left] + nums[right]: 현재 왼쪽과 오른쪽 포인터가 가리키는 요소의 합을 계산합니다.
5. diff = abs(current_sum - target): 현재 합과 목표 값과의 차이를 구합니다.
6. if diff < abs(closest_sum - target):: 현재 합이 더 목표 값과 가까우면, closest_sum을 현재 합으로 업데이트합니다.
7. if current_sum < target: left += 1: 현재 합이 목표 값보다 작으면 왼쪽 포인터를 오른쪽으로 이동시킵니다.
8. elif current_sum > target: right -= 1: 현재 합이 목표 값보다 크면 오른쪽 포인터를 왼쪽으로 이동시킵니다.
9. else: return target: 합이 목표 값과 같으면 함수는 결과로 목표 값 자체를 반환하고 종료합니다.
10. 최종적으로 함수는 찾은 가장 가까운 합을 반환합니다.

하면 할수록 코딩이란 새로운 것이 계속해서 나오는 것 같다. 빨리 속도에 맞추어 열심히 익혀나가지 않는다면 메리트 있는 개발자가 되기 어렵겠다는 생각이 확 들었다.