개요

  • 삼성 sw역량 테스트로 b형(pro)를 보러감2

코테 후기

  • 이번에는 서울로 가는게 아닌, 대전에서 봤다!
  • 매번 서울가서 시간 신경쓰고 돈도 많이 들었느데 좋았다!
  • 이번 문제는?
    • 10만*10만 정도크기의 테이블에서 우선순위같은것을 확인해야하는 문제였다.
    • 전체 테이블 각 칸마다 hash나 그런 우선순위를 지정하는 형태로 만들면 무조건 메모리, 시간 초과가 난다.
      • init부터 터짐
    • 열심히 배운 treeset을 넣으려 했지만, 시간 초과가 발생 이부분을 해결하고 싶었지만 해결을 못함
    • 필요한 연산
      • 각 사각형마다 추가하는 순서대로 우선순위를 관리
      • 각 사각형이 있는 블럭마다의 어떤 사각형이 겹쳐있는지 파악
      • 그런 사각형의 우선순위를 관리(추가, 수정, 삭제)되는 자료구조
    • 이러한 연산들이 빠르게 되는 구조가 필요했는데 이를 제대로 제시하지 못해 시간초과!
  • 누군가는 세그먼트 트리로 풀었거나, 압축기법을 사용했다고 한다.
  • 압축 기법은 올림피아드에서나 사용하는 그런 기술로 웰논 문제라고 한다.
    • 어케알아…

후기

  • 이번엔 1차 이후로 칼을 갈았지만, 프로젝트를 수행하면서 집중을 잘 못했다.
  • 컨디션도 가까운 지역이라 좋았지만 좀더 집중을 했어야 했다.. 너무 어려워
  • 최대한 설계에 집중했지만, 아이디어가 안나와 아쉬웠다….
  • 끝나고 지갑까지 잊어버리고 힘들었다.
  • 무조건 3차때 해야지