알고리즘 인터뷰 준비용

BFS vs DFS
Advantages of BFS:
1. Solution will definitely found out by BFS If there are some solution.
2. BFS will never get trapped in blind alley , means unwanted nodes.
3. If there are more than one solution then it will find solution with minimal steps.
Disadvantages Of BFS :
1. Memory Constraints As it stores all the nodes of present level to go for next level.
2. If solution is far away then it consumes time.

Advantages Of DFS :
1. Memory requirement is Linear WRT Nodes.
2. Less time and space complexity rather than BFS.
3. Solution can be found out by without much more search.
Disadvantage of DFS :
1. Not Guaranteed that it will give you solution.
2. Cut-off depth is smaller so time complexity is more.
3. Determination of depth until the search has proceeds.

Use Examples:
BFS: Finding shortest path
DFS: topological sort (listing vertices following the direction of edges)
(https://jason9319.tistory.com/93)


Dijkstra:
Using Array: https://www.crocus.co.kr/533
Using Priority Queue: https://hsp1116.tistory.com/42

댓글

댓글 쓰기

이 블로그의 인기 게시물

[Django REST Framework] create() vs perform_create()

Django REST Framework의 ModelViewSet과 create() 관련 찾아보고 공부한 내용을 정리해보려고 한다. 기본적으로 ModelViewSet은 GenericAPIView라는 클래스를 상속받기 때문에 .list(), .create()  .list(), .create() 등을 기본으로 내장하고 있다. 따라서 이 중에서 기본 내장되어 있는 메소드 중 동작을 변경하고 싶은 것들만 overriding해서 수정하면 된다. 그리고 ModelViewSet은 GenericAPIView를 상속받고 있기 때문에 최소한 queryset와 serializer_class는 세팅해주어야 한다. from rest_framework import status from rest_framework.response import Response def create(self, request, *args, **kwargs): serializer = self.get_serializer(data=request.data) serializer.is_valid(raise_exception=True) self.perform_create(serializer) headers = self.get_success_headers(serializer.data) return Response(serializer.data, status=status.HTTP_201_CREATED, headers=headers) def perform_create(self, serializer): serializer.save() 위의 코드를 보면 이해가 조금 더 쉬울 것 같다. perform_create()은 create()의 동작 중 일부분을 overriding한다고 생각하면 되는데, serializer.save()가 호출될 때 perform_create()가 호출된다고 생각하면 된다. 위의 경우 명시적으로 perform_create()를 호출했지...
자세한 내용 보기

[웹 보안] CORS란?

원문:  https://dev.to/nicolus/what-you-should-know-about-cors-48d6 CORS는 Cross-Origin Resource Sharing의 줄임말이다.  처음배우는 사람들에게는 CORS가 무엇때문에 사용되는지 헷갈릴때가 많다. 첫째로, CORS는 보안을 강화하기 위한 수단이 아니다. 사실 그의 정반대이다. CORS는 Same Origin Policy(Browser의 정책중 하나로 document나 script가 다른 domain과 교신하는 것을 막는다)를 피하기위함이다. Same Origin Policy는 하나의 도메인에서 다른 도메인으로 요청하는 것을 막는다. 이렇게 하면 악성 웹사이트들이 다른 웹사이트들에게 요청보내는 것을 막을 수 있다. 이 정책은 브라우저에 적용되어 있기때문에 서버에서 보낸 요청이나 다른 HTTP 클라이언트(cURL / POSTman 등)에게는 적용되지 않는다. 서버는 이 요청들을 신뢰할 수 있는 도메인에서 보낸 요청이라고 생각하고 처리할 수 밖에 없다.  SOP(Same Origin Policy)는 공격자가 요청을 보내는 것을 막기 위한 수단이 아니다(공격자들은 브라우저를 사용하지 않을 것이다..). SOP는 단지 정당한 사용자들이 본인도 모르게 보내는 요청들을 걸러주는 역할을 한다. 그래서 CORS는 일반적으로 SOP에 의해 막힐요청을 화이트리스트에 등록해 허용해주는 역할을 한다(예를 들자면 front-end app이 API에 요청을 보내는 것)
자세한 내용 보기

3. GRAPHQL FRAGMENTS

# Why do we need Fragments? Fragments are used to reduce redundancy. You can think of it as something like struct in C. For exmaple, ``` query {   Lift(id: "jazz-cat") {     name     status     capacity     night     elevationGain     trailAccess {       name       difficulty     } }   Trail(id: "river-run"){     name     difficulty     accessedByLifts {       name       status       capacity       night       elevationGain ...
자세한 내용 보기