[백준][투포인터] 99클럽 코테 스터디 5일차 TIL + 수열

오늘의 학습 키워드

투포인터

나는 투포인터라는 용어 자체를 처음 들어봤는데,

투포인터로 푼다는 걸 딱 듣자마자 바로 풀리네? 넘 신기하다! 😚

 

오늘의 회고

🌱 오늘의 문제

https://www.acmicpc.net/problem/2559

백준 문제는 미리보기가 안 뜨나 보다. 어제도 안 떴는데.. 흠.

 

배열의 길이 n과 간격 k가 주어지고, 온도 값을 담은 배열이 이어서 주어진다.

연속 k간의 온도의 합이 최대가 되는 값을 구하는 문제이다.

 

 

🌱 나의 시도

시도1.

처음에 시도한 방법은 타임 아웃이 떴다.

그 이유는 사실 명확하다. 아래 코드는 아주 간결하고 깔끔해보이지만 매우 비효율적인 코드이다.

1. 우선 반복문을 통해 O(n)번 돌고 있다.

2. 내부에서 sum(tem[i:i+k]) 함수는 O(n^2)으로 동작할 것이며, 반복문 내부에서 돌아가니 최종적으로 O(n^3)이다.

3. 이렇게 구한 값에 대하여 최대값을 구하기 위해 O(n)을 한 번 더 실행한다.

 

입력으로 주어진 배열의 크기가 10만이니, 사실 타임 에러가 나지 않는 것이 이상한 수준이다.

n, k = map(int, input().split())
tem = list(map(int, input().split()))

print(max([sum(tem[i:i+k]) for i in range(n-k+1)]))

 

 

시도2. 

두 번째 시도에서는 이 문제는 매번 합을 새로 구할 필요가 없다는 부분에 집중하였다.

k 길이 만큼의 합을 먼저 구한 다음, 그 이후 부터는 이동하면서 첫 번째 값을 빼고 마지막 값을 더해주면 된다.

그러면 O(n) 이면 해결할 수 있다.

n, k = map(int, input().split())
tem_list = list(map(int, input().split()))

max_tem = sum_tem = sum(tem_list[0:k])

for i in range(1, n-k+1):
    sum_tem = sum_tem - tem_list[i-1] + tem_list[i+k-1]
    max_tem = max(sum_tem, max_tem)

print(max_tem)

 

 

 

 

🌱 새롭게 알게 된 점

이 문제는 나에게 겸손함을 알려주었다.

내가 아직 잘 모르는 접근 방식이 많다는 것을 알려주었고, 잘 안다고 성급하게 풀었다간 크게 틀릴 수 있다는 것을 경고해주었다.

어떤 문제든 겸손하고 진지하게 임해야겠다.

 

 

오늘의 후기

수열 문제 예전에도 시도한 적이 있다. 별로 어려워보이지 않은데도 어떻게 접근해야 할 지 감이 잡히지 않아서 포기했었다.

그런데 오늘 항해99를 통해 "투포인터"로 접근한다는 것을 알게 되었다.

이 접근방식을 알고 문제를 보니 알고리즘을 구현하는 게 전혀 어렵지 않았다.

 

아직은 문제에 적절한 알고리즘이 무엇인지 연상하는 것이 어려운 것 같다.

그래서 다양한 문제를 다양한 시각으로 바라보며, 문제에 익숙해질 수 있도록 훈련 해야겠다.

확실히 배워나가는 것 같아서 재미있고 기분 좋다!