BaaaaaaaarkingDog
코딩, 해킹
GUESTBOOK
방명록을 남겨 보세요!
  • 비밀댓글입니다
  • 무지무지
    혹시 블로그 테마 어떤거 쓰시는지 알 수 있을까요??
  • 맨날 질문만 남기는거 같아서 조금 부끄럽네요 ㅋㅋ;

    백트래킹은 시간복잡도 계산이 불가능하다고 보면 되나요?
    맨날 백트래킹은 그냥 가지치기 잘 했겠지 하면서 기도하면서 제출하게 되더라구요 ㅠㅠ
    • ㅋㅋㅋㅋㅋㅋㅋ 질문 남겨주시면 좋죠.

      케이스 바이 케이스이긴 한데 대부분의 경우 시간복잡도 계산이 힘든 것 같아요. 그래서 자기가 알아서 최대로 시간이 많이 걸릴 입력이 어떤것일지 생각해보고 그 입력을 넣었을 때 소요되는 시간을 한 번 보는게 좋아요
    • 알린이
      감사합니당~
  • 연습생
    안녕하세요 킹독님.
    항상 알고리즘 강의 잘 보고 있습니다.
    제가 기업 코딩 테스트 때문에 얼마전부터 ps에 입문하여 공부하고 있습니다. 구현은 뒤로 두더라도 문제를 보면 무슨 알고리즘으로 풀어야겠다는 아이디어가 바로 나오려면 결국 짬이나 직관력 인가요? 아니면 다른 노하우가 있는건가요?
    • 안녕하세요, 각자 생각이 다를 수는 있겠지만 제 생각에는 이전에 수많은 문제를 풀어보았기 때문에 해당 문제를 보자마자 구현 방향이 나오게되는 것 같습니다.

      잘하는 사람의 경우 뛰어난 수학적 직관력을 바탕으로 처음보는 유형의 경우에도 발상을 해내는 경우가 있긴 하지만 저는 그정도 능력은 되지 못하고 처음보는 유형을 겪으면 아주 긴 시간 헤매다가 간신히 풀어내거나 그냥 풀이를 참고해서 지식을 습득하거나 해요. 빨리 풀리는 문제의 대부분은 DP든 그리디든 백트래킹이든 그 유형에 충분히 숙달이 되어있어서 막힘없이 코드를 짜내려가는 것 같아요.

      그래서 뻔한 얘기지만 양질의 문제를 많이 풀어보는 방법 외에는 왕도가 없는 것 같습니다.
  • 알린이
    킹독님 혹시 DP랑 Greedy랑 구별하는 노하우가 있을까요?

    다른것들은 이제 눈에 좀 들어오는데
    DP랑 Greedy는 문제를 보고 이게 DP인지 Greedy인지 구별이 안되는경우가 많아요
    특히 이 두개를 헷갈리는경우가 잦구요,

    큰 문제들을 작은 문제로 해결 할 수 있어보이는군
    -> DP인줄 알았는데 Greedy

    오 이건 딱봐도 Greedy네
    > 응 아니야
    • 문제를 보고 어떤 알고리즘으로 풀어야하는지 아는게 쉬운건 아니지만

      일단 DP가 아닌가 의심을 해보고, 식은 대충 나오지만 아무리 머리를 굴려도 시간복잡도가 이상할 때(ex : N은 10만인데 O(N^2)밖에 안보인다던지) 그리디를 의심해보게 돼요.
    • 알린이
      헷갈릴때눈 시간 복잡도를 보고 때려맞추면 되겠네용.

      감사합니다.
  • 이 글(http://www.secmem.org/blog/2019/11/15/2D-segment-tree/
    ) 작성자의 아이디와 깃헙 아이디가 같으셔서 연락드립니다! 다른 사람이라면 넘겨주세요.
    Bottom Up 방식의 세그트리 클래스 코드에서 if(r&1) ret += a[r--]; 이부분이 r--가 아닌 --r이어야 할 것 같은데 확인 바랍니다.
  • 알린이
    혹시 푼 문제를 다시 푸는것에 대해서는 어떻게 생각 하시나요?
    • 풀면서 아리까리했던 문제는 다시 푸는게 분명 도움이 될텐데 저는 이상하게 한 번 푼 문제는 또 풀기가 싫더라구요ㅜ
    • 알린이
      엥 왜 비밀글로 해놨었지..

      저두 마찬가지에요 ㅠ
      그래도 혼자힘으로 해결하지 못하고, 해답이랑 힌트를 보고 풀어낸거는 나중에 시간 간극을 두고 다시 풀어보는게 좋겠죠?

      (ex. 그리딘인줄 모르고 있었는데 문제 유형보고 그리디인것을 확인하고, 접근해서 풀이)

      (ex. 맞왜틀 시전하다가, 답보고 이해하고 풀이)

      (ex. 도저히 노답일때 답보고 이해하고 풀이)
    • ㅋㅋㅋㅋ 답보고 푼거면 ㄹㅇ 잊을때쯤 다시푸는거 되게 좋을거에요
    • 알린이
      일단 킹독님은 풀었던 문제(답을 봤던 || 안봤던)는 다시 안 푸셨던것으로 알겠슴니당.

      고민좀 해봤는데 저는 답본것들은 북마크 해두고 일주일 뒤쯤 다시 풀어보려구요.

      좋은밤 보내세용
    • 넵넵 저는 그냥 다시 풀기가 싫어서 안풀었는데, 다시 푸는게 더 좋을 것 같긴 해요. 새벽까지 고생하셨슴다
  • 비밀댓글입니다
  • 비밀댓글입니다
  • 비밀댓글입니다