2주차엔 28개의 문제가 주어졌다. 1주차 39개의 문제보다 많이 줄었지만 기초 문제가 빠진 것을 감안하면 엄청난 양이다. (사실 처음 문제 갯수를 봤을 땐, 만만하게 생각했었다.)
이번 주부터 정글 들어오기 전에 알고리즘 공부를 안한 내 자신을 매우 후회하기 시작했다.
알고리즘 공부 주제별로 나눠서 풀어본 적 없음 + 파이썬 문법 부족함 = 파멸.
그래도 난 나아가야한다...
WEEK02 : 이분 탐색, 분할 정복, 스택, 큐, 우선순위큐
이번 주차는 주제 하나하나가 고비였고 고난이었다.
off-by-one error가 발생하기 쉬운 이분탐색에서는... 3곳을 이해하는 것이 참 힘들었다.
import sys
input = sys.stdin.readline
N, M = map(int, input().strip().split())
trees = list(map(int, input().strip().split()))
start, end = 0, max(trees)
while (start <= end):
mid = (start + end) // 2
wood_sum = 0
for tree in trees:
if tree > mid:
wood_sum += (tree - mid)
if wood_sum >= M:
start = mid + 1
else:
end = mid - 1
print(end)
- while에서 왜 start <= end 이어야 할까? start < end면 안되나?
- wood_sum >= M 이어야 할까? wood_sum > M 이면 안되나?
- 마지막 출력할 때 왜 mid를 출력해야 할까? start나 mid면 안되나?
총 경우의 수는 2 X 2 X 3 총 12가지였다.
초반에 문제 풀때는 풀이 제출해보고 틀리면 하나 수정해보고 또 하나 수정해보고 또 하나 수정해보는 식으로 얼레벌레 진행했다. 그러다가 나중에 코테에서 하나의 케이스때문에 틀리면 어떡하지? 라는 걱정과, 하나를 알더라도 제대로 알아보자 는 마인드로 12가지를 전부 고려해보았다.
결론 -> 안된다. 이 이유는 게시글을 따로 하나 만들어서 설명하도록 하겠다.
겨우겨우 이분탐색을 지나니 분할정복이 나왔다. 1주차에서 날 무지하게 괴롭히던 재귀함수가 떠오르며 ptsd가 조금 왔다.
저번에 재귀를 풀때 마지막 하나만 더, 마지막 하나만 더 하고 끝냈는데 엉엉엉 이렇게 또 마주칠 일인가. 호기롭게 점화식으로 풀 수 있을 것 같은데 라고 생각했다가 허비한 시간만 24시간 정도가 될 것이다. 봐도봐도 어려운 분할 정복. 그냥 자주 풀어보는게 좋을 듯 하다.
스택과 큐는 몇번 마주한 적이 있어서 수월하게 넘어갈 줄 알았는데.... 알았는데.... 플레티넘 문제가? 띠용? 엥? 아니... 쓰앵님...
그래도 당당히 성공했다. 아 물론, 블로그와 함께 ^^ 하루내 고민하다가 이상태면 이번주차 끝까지 못간다 생각해서 블로그로 달려갔다. 접근 방법은 맞았는데... 접근 방법을 구현 못했다. 애초에 스택이라고 안알려줬으면 접근조차 못했을지도?
역시 난이도가 높아서 그런가 코드를 올린 블로그가 한개뿐이었다. 다른 풀이로도 접근해보고 싶었지만 나에겐 아직 문제 산이 남아있었기에... 미련만 남기고 떠났다.
큐에는 뱀 잡는 문제가 있었는데 이 뱀은 살모사였다. 그래서 못잡았다. 거의다 왔는데, 자꾸 틀리더라. 왜그런가 디버깅해봤더니 애초에 내 접근 방법으로는 통과될 수 없었던 거였다. 엉엉..
우선순위 큐... 덕분에 힙 공부 야무지게 하고 갑니다~
학교 자료구조 수업과 알고리즘 수업에서 공부했던 것이 많이 나왔던 2주차였다. 자료구조랑 알고리즘 열심히 좀 들어둘걸... 이번주차도 후회 만땅 하고 갑니다.
항상 스스로에게 새기는 말. 후회는 짧게!!!!!
후회 짧게 하고, 제 스스로에게 피드백 반영해서 다시 열심히 3주차 살러 가봅니다. 화이팅!
