항해 99 5기 TIL_44

▶ Today I Learned

 

<알고리즘>

 

 

[DFS, BFS]

 

그래프 탐색 알고리즘

-> 하나의 점으로부터 시작해 모든 점을 한번씩 방문하는 것

ex) 특정도시에서 다른 도시로 갈 수 있는지 없는 지

 

깊이 우선 탐색 (Depth-First Search)

 

- 하나의 노드에서 시작해 다음 분기로 넘어가기 전 까지 해당 분기를 완벽히 탐색하는 방법,

넓게 탐색하기 보다는 깊게 탐색

 

ex) 미로에서 길을 찾을 때 우선 하나의 길로 가서 갈 수 있는 곳까지 감 -> 막다른 길이라면 가장 가까운 갈림길로 되돌아와

이곳으로부터 다시 다른 방향으로 탐색을 진행하는 방법과 유사

 

모든 노드를 방문하고자 할 때 사용하는 것이 적절

간단함: 깊이 우선 탐색 > 너비 우선 탐색

단순 검색 속도: 깊이 우선 탐색 < 너비 우선 탐색

 

 

넓이 우선 탐색 (Breadth-First Search)

 

- 하나의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법,

깊게 탐색하기 보다는 넓게 탐색, 가까운 점부터 방문하여 멀리 떨어진 점은 나중에 방문순회하는 방법

 

- 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
Ex) A의 모든 친구 관계를 그래프로 표현한 후 A와 B 사이에 존재하는 경로를 찾는 경우
깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름
너비 우선 탐색의 경우 - A와 가까운 관계부터 탐색
=> 너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.

바로 깊이 들어가기 보단 인접한 노드를 먼저 모두 탐색하므로 다시 되돌아올 필요가 없다

-> 재귀적으로 동작하지 않는다.

-> 또한 어떤 노드를 방문했었는지를 반드시 검사해야 한다. 무한루프에 빠지지 않기 위해서다.

 

이러한 특성 때문에 방문한 노드들을 차례대로 꺼낼 수 있는 자료구조인 큐(queue)를 사용한다.

선입선출(FIFO) 원칙으로 탐색한다는 뜻 First In, First Out

 

시간복잡도: (두 방법 모두) 노드 수*간선 수

 

cf) 시간복잡도: 문제 해결에 걸리는 시간과 입력 함수간의 관계

 

 

출처: 

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

https://velog.io/@sangbooom/JS-BFS-DFS

 

 

[클론코딩]

 

[axios.patch]

 

클라이언트에서 서버로 요청을 보낼 때 JQuery 기반의 ajax, fetch, axios를 사용한다고 알고 있다.

그 중 이번 협업에서는 리액트 분들이 axios를 사용하고 계신데, 어제와 오늘 문제가 생겼다.

 

// 로그인 인증 미들웨어
const jwt = require('jsonwebtoken');
const User = require('../schemas/user');
require('dotenv').config();
const { JWT_SECRET_KEY } = process.env


module.exports = (req, res, next) => {
  
  const {authorization} = req.headers; 
  
  const [tokenType, tokenValue] = authorization.split(' ');
  console.log(tokenType)
  console.log(tokenValue)

  if (tokenType !== 'Bearer') {
    res.status(401).send({
      errorMessage: '로그인 후 사용하세요.',
    });
    
    return;
  }

  try {
    const { email } = jwt.verify(tokenValue, JWT_SECRET_KEY);
    User.findOne({ email })
      .exec()
      .then((user) => {
        res.locals.user = user;
        next();
      });
  } catch (error) {
    res.status(401).send({
      errorMessage: '로그인 후 사용하세요.',
    });
    return;
  }
};

로그인 되어있는 사람만이 후원할 수 있도록 위의 로그인 인증 미들웨어를 거치는데 프론트의 axios 요청이 여기까지 닿지를 않는 것 같았다.

원인이 불분명하여 위 코드에도 곳곳에 console.log를 설치하였고 그 결과 authorization이 undefined 상태이여 req.headers가 아닌 req.body에 담겨있다는 사실을 알았다.

 

그렇게 팀원들 모두가 원인을 찾기 위해 고군분투하다가 발견한 것은 axios.patch의 양식을 제대로 지키지 못했다는 것이다.

axios.post의 형태는 아래와 같다.

axios.patch(url[, data[, config]])  // PATCH

여기서 우리는 data부분에 headers를 넣은 것이다..!

하지만 사실 저 data부분에 들어가는 것이 req.body에 들어가는 부분이었으며 headers처럼 그 외 보내줄 것들은 config 부분처럼 따로 보내주어야 했던 것이다.

 

그래서 프론트의 코드는 아래와 같은 형태가 되었다.

   axios
      .patch(
        `http://우리가 지정한 url/api/article/${articleId}/donation`,
        {},
        {
          headers: {
            Authorization: `Bearer ${localStorage.getItem("login-token")}`,
          },
        }
      )

다음에 axios 요청이 협업에 쓰일 때는 axios 요청 방식을 한번 더 점검하고 문제가 없도록 해야겠다.

이렇게 또 하나 배워간다 :)

 

▶ 느낀 점

 

자주 출제되는 유형 중 하나인 탐색에 대해 공부해보았다.

기본적인 개념은 이해가 되지만 막상 제대로 적용해본 적이 없기에 아직은 추상적이다.

알고리즘 스터디에서 하나씩 사용해보도록 하자.

+

백엔드에서 필요한 기본적인 기능들은 모두 구현이 되었으니 추가적인 기능에 도전해보면 좋을 듯 하다.

마침 오늘 다른 팀원 분 께서 소셜로그인 (카카오톡)을 추가해보자는 의견을 제안해주셨다.

내일 한번 도전해보아야지! 화이팅팅!

 

▶ 공부 시 참고 링크들

 

 

https://velog.io/@jamie/MongoDB-insert-data

MongoDB에 여러 데이터를 넣어보자(Insert & Import)

 

https://gmlwjd9405.github.io/2019/04/22/javascript-hoisting.html

[JavaScript] 호이스팅(Hoisting)이란 - Heee's Development Blog