2024.01.31 (수) Pyalgo100 파이썬 문제풀이

오늘은 탐색이라는 알고리즘 문제를 풀어보려고 한다. 어제 푼 문제들과 비슷한 유형의 문제들이 었지만 조금 더 활용과 심화과정이라는 느낌이 들었다. 단순 탐색이 되는 문제이었기에 그렇게 어렵지 않은 느낌도 있었지만 쉽지 않은 부분이 훨씬 많았다.

1. 2차원 배열 탐색

문제 설명
2차원 배열과 타겟 숫자가 주어집니다. 주어진 2차원 배열에서 타겟 숫자가 존재하는지 확인하고, 존재하는 경우 True를, 존재하지 않는 경우 False를 반환하는 코드를 작성해주세요.

제한 사항
2차원 배열은 m x n 크기이며, 각 요소는 정수입니다.
배열의 각 행은 오름차순으로 정렬되어 있습니다.
m과 n은 각각 최소 1에서 최대 100까지입니다.

 

입출력 설명
주어진 2차원 배열에서 타겟 숫자를 찾아, 존재하는 경우 True를, 존재하지 않는 경우 False를 반환합니다. 첫 번째 예시에서는 타겟 숫자 7이 배열에 존재하므로 True를, 두 번째 예시에서는 타겟 숫자 13이 배열에 존재하지 않으므로 False를 반환합니다.

 

이 문제는 어제 푼 문자열 문제와 매우 흡사했다. 2차원 배열이 주어진 상황에서 그 안에 target 숫자가 존재하는지 여부를 판단하는 거였기에 어제와 같은 방식으로 풀었다.

def solution(data):
    matrix, target = data
    for row in matrix:
        if target in row:
            return True
    return False

data를 언패킹 해주고 target 이 row안에 있다면 True 없다면 Fasle 를 출력하도록 하여 간단하게 코드를 완성하였다.

 

다른 방식으로도 풀 수 있었는데 바로 아래와 같다. 

def solution(data):
    matrix, target = data
    return any([target in row for row in matrix])

data를 언패킹 해주고 any를 활용하여 리스트 컴프리헨션을 사용했는데 target 이 row안에 있느냐를 물어보고 matrix안에서 row가 순회를 하게 하면 된다.

 

또 다른 방식으로는 data를 평탄화 해주는 방법이 있다. 

def solution(data):
    matrix, target = data
    return target in sum(matrix, [])

 

원래는 그냥 matrix 라면 sum을 리스트이기에 사용할 수 없지만 matrix를 sum해주기 위해 초기값을 [] 빈 리스트로 설정해준다면 sum을 사용할 수 있다. 

 

2. 연속 수열의 최대합

문제 설명
정수로 이루어진 배열이 주어집니다. 이 배열에서 연속된 부분 수열의 합 중 최대값을 찾는 코드를 작성해주세요.

제한 사항
배열의 길이는 최소 1에서 최대 100까지입니다.
배열의 각 요소는 -100 이상 100 이하의 정수입니다.
연속된다는 것은 배열안에 인덱스가 연속된다는 의미입니다.

 

입출력 설명
첫 번째 예시에서 가장 큰 부분 수열 합은 [3, 4, -1, 2, 1]으로, 합계는 9입니다. 두 번째 예시에서는 [4, -1, -2, 1, 5]의 부분 수열 합이 최대이며, 합계는 7입니다.

 

이 문제를 보았을 때는 아 리스트안의 각 간격을 알아내고 그거를 결과값으로 출력하면 되겠구나라고 머리 속으로 생각을 하였다. 그래서 예전에 비슷하게 최소 거리를 구했던 문제를 살펴보면서 풀어볼려고 했는데 잘 되지를 않아서 계속 시도하다가 풀이를 보았다....

 

 

 

data들을 차례대로 비교해보면서 최대값을 찾아보고 비교할 때 그 전의 값의 합산을 계속 데려서 끌고가자. 그러면서 차례대로 값들을 더하면서 찾아보는 원리를 이용한 것 같다.

def solution(data):
    if not data:
        return 0
    max_sum = current_sum = data[0]
    
    for num in data[1:]:
        print(current_sum, num, current_sum + num)
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

max_sum 이라는 변수에 0 번째 data를 할당을 해주고 data[1:]: 를 활용하여 1번부터 슬라이싱해서 순회를 하면서 current_sum으로 들어간다. 그 때 max 를 활용해 최대값을 찾아서 넣어준다. 

 

마지막 2번째 문제 같은 경우는 사실 너무 어려웠다. 풀이를 보았지만 푸는 방식이 너무 낯설고 익숙하지 않았다. 이번 문제는 비슷한 문제를 만들어 다시 풀어보고 여러번 반복해야 할 것 같다.