✍️오늘 공부한 내용

• 오늘은 어제 개념정리했던 자료구조에 해당되는 백준문제들을 풀었다.
  백준에서 자료구조 이진탐색(binary search), queue & stack과 관련된 문제를 풀었다
  • 문제 (풀이는 추후정리해 올릴 예정)
    • 이진탐색
      • [2110] 공유기 설치
    • 큐
      • [18258] 큐
    • 스택
      • [9012] 괄호
      • [10773] 제로
      • [10828] 스택
      • [17608] 막대기

📋새로 배우게 된 내용

• 파이썬에서 range()함수는 인덱스를 iterable item이 있을때 인덱스로 어떤 범위를 가져올 때 자주 썼었다. ft.for문
  • range(a, b, c)식으로 인자를 3개 받는 경우는 생소했는데, a는 시작, b는 끝, c는 커지는 단위(default==1)이었다. range함수에 대해서
• 항상 input()이 여러줄인 경우 for문을 돌려서 list()에 넣는 식으로 했는데, 조금 다른 방식으로 쓸 수 있는 방법을 찾다가 list(map(for 문)) 식으로도 쓸 수 있는 방법도 있다는 걸 찾았다. 한줄이라 좀 더 단축된 느낌!

stack = list(map(int, (sys.stdin.readline() for _ in range(N))))

🫥오해했던 점

• break와 continue의 사용이 헷갈렸는데 , 이 김에 간단히 정리하자면
  • continue는 if문이 참일 경우 다시 for문으로 돌아간다.
    
  • break는 for문으로 돌아가는게 아니라 바로 함수를 종료한다.
    

🤯어려웠던 점

1. 18258번 queue문제를 푸는데 시간초과에러가 있었다.
2. 9012번 for문 안에 작동방식에 대해 다시한번 봐야할 거 같다. for문 안에 if문 조건을 건너뛰고(true인데도) 다음 줄의 코드를 실행해서 출력이 중복되었다.

😸어려움을 해결한 방법

1. 처음은 어디서 시간이 초과될 지 분석해봤다.

• 🤔 input()이 상대적으로 sys.stdin.readline보다 시간이 오래걸린다고 해서 이 부분을 수정했다.여전히 시간초과
• 🤔 input값들을 받을 떄 list에 한번 넣어주고 queue를 구현할때 다시 여기 값들을 사용하는데, o(2n)이 될 수 있을 거 같아서 pypy3로도 바꿔서 채점 해봤는데 여전히 시간초과
• 😮 구글링 결과, queue.pop(0)이 O(n)이 pop한 나머지들을 한자리씩 앞당겨주는데 소비된다.
• 따라서 queue의 인덱스를 파악해서 해당 index를 print해줬다.

🤔아쉬웠던 점

• 9012번 for문 관련 이슈는 아직 진행 중이다. 문제풀이 복습을 하면서 원인을 찾아볼 예정이다.

😝느낀점

• 저번에는 개념공부를 하기 전에 문제를 한번 풀었었는데, 이진탐색 문제를 풀었을떄는 문제풀이 전에 개념 공부를 했다.
• 오히려 문제가 접근하기 좀 더 나은 느낌이어서 앞으로도 개념공부 후 문제풀이를 하도록 해야겠다.
• 이진탐색 문제는 결국 첫값(left)와 끝값(right)을 잘 찾아서 반씩 추려가면서 탐색하는 문제인게 와닿았다. 아직 많은 문제를 풀지 않아서 규칙을 빨리 찾지는 못하지만, 재귀함수 공부했을 떄처럼 조금은 더 보이는 느낌이라 좋다.

👊다짐

• 한번 본 코드도 다시 보고, 남들이 작성한 코드도 보자. 아직 이중탐색에서 어떤 값을 left와 right으로 둬야하는 지 익숙하지 않으니, 이중탐색 관련 문제도 추가적으로 풀어서 익히자.

🚀오늘의 한줄평

• 내가 모르는 것도 이중분할 O(logN) 하고 싶다.